KUPC 2014 G - Darkroom

対話的アルゴリズム

問題

正整数n, dが与えられる。
長さnの0, 1からなる文字列を好きに出力することができる。


A, Bの二人が、この文字列のi番目, j番目に配置される。
ただし|i - j| = dとなるように置かれる。


A, Bに対して

  • Aを左に1つ動かす
  • Aを右に1つ動かす
  • Bを左に1つ動かす
  • Bを右に1つ動かす

のどれかの動きをさせることができる。（一度の指示では一人しか動かせない）


動きを行う前に、二人がいる場所の文字がそれぞれ与えられる。
質問を4回まで行って、i < jであるか、i > jであるかを確定せよ。

制約条件

n, d≦10^5
二人は両端から十分に離れた場所にいるので、動かして文字列の外に出ることはない。
二人の位置が途中で入れ替わることもない。

方針

dが3k+1, 3k+2と書けるのであれば、
100100100100...という文字列を最初に出力しておけば、
二人が右に一歩ずつ動けば、二人の座標がmod 3でわかる。


したがって、i + 1≡j (mod 3)であるか、i - 1≡j (mod 3)のどちらが成り立っているかわかり、i < j, i > jがわかる。


dが3の倍数の場合は、
00000/11111/10101/....というパターンを出力すればよい。
このパターンは、どこにいても右に1歩動けば、0000のエリア、1111のエリア、1010のエリア
かがわかる。


d = 3^p(3k + l)と書けるとき、
各パターンの長さを3^pにすれば、必ず二人は違うエリアに入るので、3の倍数と同じ原理でi < j, i > jのどちらかがわかる。

ソースコード

int get(const string &s){
	if(s == "000" || s == "001" || s == "011") return 0;
	if(s == "111" || s == "110") return 1;
	return 2;
}

int main(){
	int n, d;
	cin >> n >> d;
	string s(n, '0');
	
	if(d % 3){
		
		rep(i, n) if(i % 3 == 0) s[i] = '1';
		cout << s << endl;
		
		int a = -1, b = -1;
		rep(i, 3){
			string x, y;
			cin >> x >> y;
			if(x == "1") a = i;
			if(y == "1") b = i;
			if(i < 2){
				cout << "Move(A,-1)" << endl;
				cin >> x >> y;
				cout << "Move(B,-1)" << endl;
			}
		}
		if((a + d) % 3 == b % 3) cout << "i<j" << endl;
		else cout << "i>j" << endl;
		
		return 0;
	}
	
	int t = 1;
	while(d % 3 == 0) d /= 3, t *= 3;
	for(int i = 0; i < n; ){
		rep(j, t) if(i < n) s[i++] = '0';
		rep(j, t) if(i < n) s[i++] = '1';
		rep(j, t) if(i < n) s[i++] = '1' - j % 2;
	}
	cout << s << endl;
	
	string a, b;
	rep(i, 3){
		string x, y;
		cin >> x >> y;
		a += x; b += y;
		if(i < 2){
			cout << "Move(A,1)" << endl;
			cin >> x >> y;
			cout << "Move(B,1)" << endl;
		}
	}
	int ia = get(a), ib = get(b);
	if((ia + d) % 3 == ib % 3) cout << "i<j" << endl;
	else cout << "i>j" << endl;
	
	return 0;
}