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:;
	}
}