Az I. 202. feladat (2009. január)

I. 202. Adott néhány kupac kavics. Minden lépésben az összes kupacból elveszünk egy kavicsot és ezekből egy új kupacot képzünk. A kupacok sorrendje nem számít.

Például:

A lépéseket addig ismételgetjük, amíg meg nem unjuk. Mivel véges a kavicsok száma, így előbb-utóbb a kavicsok eloszlása a kupacokban ciklikussá válik.

Írjunk programot, amely a bemeneti adatállományban megadott kupacok kavicsszáma alapján megadja, hogy hányadik lépésben kezdődik az ismétlődés és mi a ciklus hossza. Az összes kavics száma nem lehet több mint 50.

A program parancssori argumentuma legyen a kupacokat leíró adatállomány neve. A fájl első sorában egy egész szám áll, amely a kupacok N számát (1N25) adja meg. Az ezt követő N db sor mindegyikében egy érték szerepel, amely a kupacok kavicsszámát adja meg.

A program kimenete a képernyőre két pozitív egész szám, amely közül az első azt adja meg, hogy hányadik lépésben kezdődik egy új ciklus és a másik, hogy egy ciklus hány lépésből áll.

Beküldendő a program forráskódja (i202.pas, i202.cpp, ...), valamint a program rövid dokumentációja (i202.txt, i202.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2009. február 16-án LEJÁRT.

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

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Barta 111 János, Englert Péter, Kővágó Zoltán.
9 pontot kapott:	Nagy 111 Miklós.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	3 versenyző.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	3 versenyző.

A KöMaL 2009. januári informatika feladatai