【题意】
给定一个汉诺塔的局面,问最少多少步可以将它们并到一个柱子上
【输入】
第一行n,表示n个盘子
接下来一行3个数字m[i],表示柱子上分别有几个盘子
随后的三行每行m[i]个数字,表示在该柱子上的盘子的编号
【输出】
第一行输出一个数字表示集中到哪个柱子上
第二行输出一个数字表示最小步数模1000000
汉诺塔的过程是可逆的,所以反过来考虑n个盘子都在一根柱子上最少需要移动多少步才能到达当前局面
既然倒过来了,那最底层的盘子就不要动了,所以最初的n个的盘子堆在n所在的柱子
然后从盘子编号从大到小考虑,假设当前i不在要到达局面的柱子上,那么就要将它所有上面的盘子移动到与它无关的柱子上,然后再将盘子i移到指定位置
program poj1920; const maxn=1000000; var ans,n,i,j,k,now:longint; two:array [0..100001] of longint; m:array [1..3] of longint; belong:array [0..100001] of longint; begin two[0]:=1; for i:=1 to 100000 do two[i]:=two[i-1]*2 mod maxn; read(n); for i:=1 to 3 do read(m[i]); for i:=1 to 3 do for j:=1 to m[i] do begin read(k); belong[k]:=i; end; writeln(belong[n]); ans:=0; now:=belong[n]; for i:=n downto 1 do if now<>belong[i] then begin ans:=(ans+two[i-1]) mod maxn; now:=6-belong[i]-now; end; writeln(ans); end.