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

 

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 1\leN\le25), 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 16 February 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

Fájl neve eredmény
t0.txt 5 4
t1.txt 74 1
t2.txt 42 9
t3.txt 56 8
t4.txt 90 1
t5.txt 8 1

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.

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