KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem S. 13. (December 2005)

S. 13. Two players alternately move a piece on the vertices of a directed graph. One loses if he or she cannot move because the current vertex has no outward edge. If the piece is placed for the third time onto the same vertex, the game is a draw. Write a program that determines for each vertex the best possible result of the first player starting from that position.

The program will be run from the command line with two parameters containing the names of the input and output files. The input file contains the graph. The output file should contain whether any given vertex is a winning or a losing one.

The first line of the input file will contain the number of vertices and edges (n,m). The vertices are numbered from 1 to n. The next m lines will contain the origin and endpoint of each directed edge. The output file should have n lines, with the i^\mathrm{th} line containing W, D or L, depending on whether the first player starting from the i^\mathrm{th} vertex has a winning strategy, both players have a strategy to force a draw, or the second player has a winning strategy, respectively.

The graph can be assumed to have at most 1 000 000 vertices and at most 50 000 000 edges.

Example: the program is run with s13 graph.txt result.txt parameters.

graf.txtresult.txt
5 7
1 1
1 2
2 3
2 4
3 1
4 3
4 5
D
D
D
W
L

The source code of the program (s13.pas, s13.cpp, ...) should be submitted.

(10 pont)

Deadline expired on 16 January 2006.


Statistics:

7 students sent a solution.
10 points:Homolya Miklós, Nikházy László.
4 points:2 students.
2 points:2 students.
1 point:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley