Hanoi tornyai
Bizonyára hallottál a Hanoi-tornyai problémáról: Különbözö méretü korongok vannak három rúdon, kezdetben ugyanazon a rúdon vannak rendezetten, azaz felfele csökkenö sorrendben. A játék célja az összes korong átrakása egy másik rúdra úgy, hogy közben soha nem rakhatsz nagyobb korongot kisebbre.
47 korongból álló torony átrakása több ezer évig tartana, mivel legalább 247-1 mozgatás kellene. 
A játéknak egy olyan változatát tekintjük, amelyben kezdetben mindegyik rúdon lehetnek korongok rendezetten. A játék célja meghatározni, hogy melyik rúdra lehet legkevesebb mozgatással átrakni az összes korongot és, hogy minimálisan hány mozgatással lehet ezt elérni. Azonban ez is túl nagy szám lehet, ezért a mozgatások számának 1000000-val való osztási maradékát kell megadni.
Példa
Az alábbi példa megoldható 4 mozgatással:
Bemenet
A hanoi.in állomány elsö sorában a korongok N száma van (0<N<=100000). A második sor az s1, s2, s3 három egész számot tartalmazza (0<=s1, s2, s3<=N, s1+s2+s3=N), az egyes rudakon levö korongok számát. A következö három sor az elsö, a második és a harmadik rúdon levö korongok méretét tartalmazza méret szerint csökkenö sorrendben. Természetesen minden 1 és N közötti méret pontosan egyszer fordul elö.
Kimenet
A hanoi.out állomány elsö sorába annak a rúdnak a sorszámát (1, 2 vagy 3) kell irni, amelyikre a legkevesebb mozgatással lehet a korongokat rakni. A második sorba pedig a minimális mozgatásszámot kell irni, modulo 1000000 (1 millió).
Példa
hanoi.in	hanoi.out	
7
4 1 2
7 6 5 4
3
2 1	1
4	

Tesztadatok
Programodat 20 különbözö tesztállománnyal értékelik.
Teszt 	1	2	3	4	5	6	7	8	9	10	11	12	
N	5	10	15	20	50	100	150	200	1000	2000	3000	4000	

Teszt	13	14	15	16	17	18	19	20	
N	30000	40000	50000	60000	70000	80000	90000	100000