Codeforces 42 C. Safe cracking
問題
4つの整数が円周上に並んでいる。
この数に対して次の操作を1000回以下行い、
全ての数を1にすることができるか。
- 隣合う二数に1を足す
- 隣合う偶数を2で割る
できるならその操作の内容をどれか一つ具体的に出力し、(最短手順でなくともよい)
できないなら-1を出力せよ。
制約条件
1≦四つの整数≦10^9
方針
実は必ず1 1 1 1を作ることができるみたい。未証明。
以下を繰り返したら通った。
- 隣合う偶数があったら2で割る
- 隣合う奇数があったら1を足して2で割る
- 奇数-偶数-奇数の並びがあったら、奇数-偶数に1を足し、偶数-奇数に1を足し、最初の2数を2で割る
ソースコード
int a[4]; void run() { rep(i,4)cin>>a[i]; for(;;){ bool ok=1; rep(i,4)if(a[i]!=1)ok=0; if(ok)break; rep(i,4)if(a[i]%2==0&&a[(i+1)%4]%2==0){ cout<<"/"<<i+1<<endl; a[i]/=2; a[(i+1)%4]/=2; goto NEXT; } rep(i,4)if(a[i]%2==1&&a[(i+1)%4]%2==1&&(a[i]!=1||a[(i+1)%4]!=1)){ cout<<"+"<<i+1<<endl; cout<<"/"<<i+1<<endl; a[i]=(a[i]+1)/2; a[(i+1)%4]=(a[(i+1)%4]+1)/2; goto NEXT; } rep(i,4)if(a[i]%2==0){ cout<<"+"<<(i+3)%4+1<<endl; cout<<"+"<<i+1<<endl; cout<<"/"<<(i+3)%4+1<<endl; a[(i+3)%4]=(a[(i+3)%4]+1)/2; a[i]=(a[i]+2)/2; a[(i+1)%4]++; goto NEXT; } NEXT:; } }