Problem S. 76. (December 2012)
S. 76. Model railway packages can be purchased from the Random Railway Toy Factory (RRTF) containing some connectable tracks, a locomotive and some railroad cars. Different packages may contain a different number of tracks, but RRTF aims to put them into a package in such a way that if each piece is used, then one can construct a railway which can be traversed by the train completely, finally returning to its starting position. In other words, the train can go on forever - or at least until the locomotive has enough power.
However, RRTF does not include any assembling instructions in the game package, so it is not surprising that some customers and their children are unable to construct the above ideal railway. So RRTF promised that if it was impossible to create an ideal railway by using elements of one's package, one would get a second package for free. Due to the challenges of assembling the track and the tempting offer of RRTF, some customers are asking for our help. After they have provided us with a description of the railway elements of their package, they would like to be given the assembling instructions of an ideal track, or, if it is impossible, they would like to have some information why it is not realizable.
A package contains the following types of elements having tracks on their both sides: a straight element of length two, a quarter-circular arc of radius one, and a perpendicular crossing of length two in both directions with intersection in the middle.
The arced element can be used in both left and right turns. On the ideal track, both ends of both directions of the perpendicular crossing element should be joined to other elements. Elements can be joined to each other only through their connecting parts. Each package contains at least 25, but at most 35 elements, and there are at most 4 crossings.
Your program should read the only line of the standard input, specifying the number of crossings, straight elements and the number of arcs, respectively, then, if an ideal track can be assembled, the program should write an ideal path to the standard output, starting from an arbitrary point and making a complete round. Elements are encoded as follows: X denotes a crossing, E denotes a straight element, a left turn is B, while a right turn is abbreviated by J. If it is impossible to create an ideal track from the given elements, then the first line of the output should be the sentence ``No ideal track can be assembled.'', and the next line should contain a short explanation -- if we can do it.
The table contains two examples. ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output. In the second case, the output reads as ``No ideal track can be assembled. The number of arced elements is odd, hence the sum of total rotations is not an integer multiple of 360 degrees.''
The source code (s76.pas, s76.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s76.txt, s76.pdf, ...) - also describing which developer environment to use for compiling, further a brief description of your solution - should be submitted in a compressed file s76.zip.
(10 pont)
Deadline expired on January 10, 2013.
Sorry, the solution is available only in Hungarian. Google translation
A feladat megoldását döntően Jákli Aida Karolina 10. osztályos zalaegerszegi diák és Kalló Kristóf 11. évfolyamos budapesti versenyző dokumentációja alapján készült: s76mo.pdf .
Mintaprogramként Vályi András 10. osztályos debreceni diák programját közöljük: s76va.cpp.
Statistics:
7 students sent a solution. 9 points: Jákli Aida Karolina, Vályi András. 8 points: 2 students. 7 points: 1 student. 5 points: 1 student. 3 points: 1 student.
Problems in Information Technology of KöMaL, December 2012