Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題「Cup」
https://onlinejudge.u-aizu.ac.jp/problems/0503
大きさが異なる n 個のコップと 3 つのトレイ(お盆)A,B,C があり,それらのコップは 3 つのトレイの上にそれぞれ何個かずつ一山に重ねて置かれている.
ただし,どのトレイにおいても,そのトレイの中で一番小さいコップが一番下に, 2 番目に小さいコップがその上に, 3 番目に小さいコップがその上にと,小さい順に伏せて重ねてある.
例えば,n = 5 個のコップがトレイ A,B,C にそれぞれ 2 個,0 個,3 個重ねて置かれている.
このように,コップの初期状態が与えられたとき,次の規則 1 〜 3 を守りながら,すべてのコップを A または C のどちらかのトレイに移動させるには何回移動を行えばよいかを求めたい.
(規則 1) 1 回に 1 つのコップだけを移動させることができる.
それは,そのトレイにあるコップの中で一番上のコップ(つまり,一番大きいコップ)である.
(規則 2)大きいコップの上に小さいコップを重ねてはいけない.
(規則 3)コップ 1 個の直接移動は,トレイ A から B,B から A,B から C,C から B のみが許され, A から C への直接移動や C から A への直接移動は許されない.
n 個のコップの初期状態と整数 m が与えられたとき, m 回以内の移動で, A または C のどちらかのトレイにすべてのコップをまとめて重ねることができるかどうかを判定し,可能な場合には移動回数の最小値を,不可能な場合には -1 を出力するプログラムを作成しなさい.
入力ファイルの 1 行目には, n と m がこの順に空白を区切り文字として書いてある.
1 ≦ n ≦ 15 であり, 1 ≦ m ≦ 15000000 である.
2 行目,3 行目,4 行目には, 1 から n までの整数を何個かずつ 3 つのグループに分けて,それぞれのグループ内で小さい順(昇順)に並べたものが書いてある.
ただし,各行の先頭(それらの整数の前)には,それらの個数が書いてある.
2 行目に書かれている整数(先頭の 1 つを除く)はトレイ A の上に重ねられている各コップの大きさを表す.
同様に, 3 行目に書かれている整数(先頭の 1 つを除く)はトレイ B の上に重ねられている各コップの大きさを表し, 4 行目に書かれている整数(先頭の1つを除く)はトレイ C の上に重ねられている各コップの大きさを表す.
・入力される値
入力は複数のデータセットからなる.n, m がともに 0 のとき入力が終了する.
データセットの数は 5 を超えない.
・期待する出力
データセットごとに、移動回数または -1 を1行に出力する.
僕が作成、提出したコードは、以下のとおりです。
/* Volume5-0503 Cup http://judge.u-aizu.ac.jp/ 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int bit(int a,int b,int c){ if(!a & !b){ return 0; } if(c & 1){ return (bit(a>>1,b>>1,c>>1)); } if(b & 1){ return (bit(c>>1,b>>1,a>>1)+bit((a|b|c)>>1,0,0)+1); } if(a & 1){ return (bit(a>>1,b>>1,c>>1)+2*bit((a|b|c)>>1,0,0)+2); } } int main(void){ int n,m,data[3]; while(1){ cin>>n>>m; if(n==0 && m==0){ return 0; } for(int i=0;i<3;i++){ int k; cin>>k; data[i]^=data[i]; for(int j=0;j<k;j++){ int num; cin>>num; data[i]|=1 << --num; } } int ans=min(bit(data[0],data[1],data[2]),bit(data[2],data[1],data[0])); if(ans<=m){ cout<<ans<<endl; }else{ cout<<-1<<endl; } } }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
Volume5-0503 Cup
上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。