新規
編集
添付
時間制限:3000ミリ秒
メモリ制限:16000KB
ケース別時間制限:1000ミリ秒
ハノイの塔
問題 
ハノイの塔を知っているかもしれない: 互いに異なる大きさの木製の円盤が3つのペグに積まれている。同じペグにある円盤は、大きい円盤が小さいほうにあるようにソートされている。目的は、大きい円盤を小さい円盤に乗せないようにしながら、1回に1つの円盤をペグからペグに動かしていき、1つのペグに円盤全体を移動させることである。
昔の神話によると、チベットの古僧は47個の円盤をもつ特別に大きなハノイの塔を、何千年もかけて解いていると伝えられている。この問題は最低でも247-1回の操作が必要なのにもかかわらず、僧は戦略なしに解きはじめてしまったので、ルールを守りながらも状況をめちゃくちゃにしてしまった。今、彼らはできるだけ少ない手数で、どれかのペグ上に円盤をきれいに積みなおしたい。しかし彼らはルールに背いた操作をしないことを誓ってしまっている。彼らは、最短手数で積みなおすには、何手でどのペグに積めばいいかを知りたい。
この僧のために問題を解くプログラムを作りなさい。プログラムは0<N<=100000なるいかなる個数の円盤にも対応しなければならない。計算途中の数値ははてしなく大きくなる。そのため、僧は手数の1000000での剰余にのみ興味がある。
例
以下の例は4手で解ける。
入力
入力の最初の行は円盤の数N(N <= 100000)からなる。次の行はそれぞれのペグに積まれている円盤の数をあらわす3つの整数s1,s2,s3(0 <= s1,s2,s3 <= Nかつs1+s2+s3=N)が書かれている。続く3行はそれぞれのペグに積まれている円盤の大きさを含む。より正確には、入力の(i+2)行目はsi個の整数mi,1 ・・・mi,si(ただし1<=mi,j<=Nであり、i番目のペグに積まれている円盤の大きさを意味する)が書かれている。円盤は下から上に順に与えられる。つまりmi,1 > mi,2 > . . . > mi,siである。
何も積まれていないペグは空行として与えられることに注意すること。N個の円盤は相異なる大きさをもつ。全ての数は1つの空白文字によって区切られる。
出力
出力の最初の行は最短手数で円盤を積みあげることのできるペグの番号をあらわす{1,2,3}のうちどれかの整数を出力せよ。次の行には最短手数を1000000で割った余りを出力せよ。
入力例
7 2 1 4 2 1 3 7 6 5 4
出力例
3 4
出典
CEOI 2003
