NézetNyomtat

Bolgár szoliter (Megoldás)
Címkék > Feladat

Bolgár szoliter

Adott néhány kupac, bennük néhány kavics. Egy lépésben mindegyik kupacból leveszünk egy kavicsot, és ezekből a levett kavicsokból egy új kupacot képezünk. Ezt a lépést ismételgetjük, amíg meg nem unjuk.
Mivel véges sok állapot van, előbb vagy utóbb ciklikussá válik a "játék". Kérdés, hogy mikor kezdődik az ismétlődő rész, milyen állapotok ismétlődnek, és mi a ciklus hossza.

Feladat

Írj programot, ami beolvassa a kavicsok számát, majd minden lehetséges módon szétosztja őket kupacokba, és minden szétosztásra vizsgálja a következőket:
  1. Melyik állapotok ismétlődnek?
  2. Milyen hosszú a ciklus?

"Tesztadatok"

Ha a kavicsok száma "háromszögszám" (1,3,6,10,15,...), akkor a kezdeti partíciótól függetlenül az egyelemű {1,2,3,...,n} ciklusba érkezik meg a játék.