Problem I. 202. (January 2009)

I. 202. We are given some heaps of stones. In every step, we remove one stone from each heap and form a new heap out of these stones. The order of heaps is irrelevant.

The number of steps can be arbitrary. Since the number of stones is finite, sooner or later the distribution of stones in heaps becomes cyclic.

Write your program to compute the number of step in which repetition begins and determine the cycle length. The command line argument of your program is the name of the input file. The input file contains the initial distribution of stones in heaps: the first line of the input file contains the number of heaps N (being an integer with 1N25), the following N lines then contain the number of stones in the corresponding heaps. (The total number of stones, however, is no more than 50.)

In the example (``Példa''), the input is ``Bemenet'', and the output is ``Kimenet''.

The output of your program on the screen is two positive integers: the first gives the number of step in which a new cycle starts, while the second describes the length of a cycle.

The source code of your program (i202.pas, i202.cpp,...) together with a short documentation (i202.txt, i202.pdf,...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use for compiling.

(10 pont)

Deadline expired on February 16, 2009.

Sorry, the solution is available only in Hungarian. Google translation

A feladat Bolgár soliter néven ismert játék.

Megoldásokról:

Viszonylag kevés tökéletes megoldás érkezett. Többen nem olvasták el precízen a feladatot és nem vették figyelembe, hogy a kupacok sorrendje nem számít. Minden lépés után érdemes a kupacokat, illetve a kavicsok számát csökkenően rendezni. Ezzel könnyebbé válik az eddig eltárolt elrendezések között visszafelé megkeresni az egyezőt. Az első egyezés esetén feljegyezzük a lépést, hiszen ekkor kezdődik új ciklus.

Érdekes, ha a kavicsok száma "háromszögszám" (1,3,6,10,15,...), akkor a kezdeti elrendezéstől függetlenül egy hosszúságú ciklusba érkezik a játék.

Mintamegoldásként Barta János 9. osztályos tanuló (Salgótarján, Madách Imre Gimnázium) megoldását közöljük: i202.dpr

A feladat értékeléséhez használt tesztállományok: teszt.zip

Statistics:

14 students sent a solution.
10 points:	Barta 111 János, Englert Péter, Kővágó Zoltán.
9 points:	Nagy 111 Miklós.
8 points:	1 student.
7 points:	3 students.
5 points:	1 student.
3 points:	2 students.
2 points:	3 students.

Problems in Information Technology of KöMaL, January 2009