CSAcademy Round #16 : D. Fake Coins

Interactive連発は疲れるね。これは本番解けず。
https://csacademy.com/contest/round-16/#task/fake-coins

問題

1～Nの番号を振られたN枚のコインがある。
コインの重さは１枚が10g、１枚が30g、残り(N-2)枚が20gである。
コインの２つのサブセットを指定すると、どちらの総和が重いか返す秤がある。
この秤を25回まで使えるとき、10gおよび30gのコインがどれか答えよ。

解法

Nが偶数のときを考える。
適当に乱択シャッフルしながらコインを半々に分けて秤を使うと、10gと30gのコインは約半分の確立で別々のグループに入る。
あとは両グループ内で秤を使い二分探索や三分探索で１枚だけ異なる子院を探せばよい。

Nが奇数の場合、３枚の重さを３回秤を使って比べれば１枚は20gのコインがわかるので、それを取り除いで上記処理を行えばよい。

int N;
int P10,P30;

int ask(vector<int> A,vector<int> B) {
	int x;
	cout<<"Q "<<A.size()<<" "<<B.size();
	FORR(r,A) cout<<" "<<(r+1);
	FORR(r,B) cout<<" "<<(r+1);
	cout<<endl;
	cin>>x;
	return x;
	
}

pair<pair<vector<int>,vector<int>>,int> split(vector<int> A) {
	vector<int> B,C;
	int R,i;
	
	if(A.size()%2==1) {
		R=A.back();
		A.pop_back();
	}
	FOR(i,A.size()) {
		if(i%2) B.push_back(A[i]);
		else C.push_back(A[i]);
	}
	return {{B,C},R};
}


void getless(vector<int> A) {
	if(A.size()==1) {
		P10=A[0];
		return;
	}
	auto v=split(A);
	auto a=v.first.first;
	auto b=v.first.second;
	int x=ask(a,b);
	if(x==-1) getless(a);
	else if(x==1) getless(b);
	else P10=v.second;
}

void getmore(vector<int> A) {
	if(A.size()==1) {
		P30=A[0];
		return;
	}
	auto v=split(A);
	auto a=v.first.first;
	auto b=v.first.second;
	int x=ask(a,b);
	if(x==-1) getmore(b);
	else if(x==1) getmore(a);
	else P30=v.second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int del=-1;
	if(N%2==1) {
		i = ask({0},{1});
		j = ask({0},{2});
		k = ask({1},{2});
		if(i==0 || j==0) del=0;
		else if(k==0) del=1;
		else if(i==-1&&j==-1) del=(k==-1)?1:2;
		else if(i==1&&j==1) del=(k==1)?1:2;
		else del=0;
	}
	vector<int> A;
	FOR(i,N) if(i!=del) A.push_back(i);
	
	while(1) {
		random_shuffle(ALL(A));
		auto D=split(A);
		x = ask(D.first.first,D.first.second);
		if(x==0) continue;
		
		if(x==-1) {
			getless(D.first.first);
			getmore(D.first.second);
		}
		else {
			getmore(D.first.first);
			getless(D.first.second);
		}
		break;
	}
	
	cout<<"A "<<(P10+1)<<" "<<(P30+1)<<endl;
	
}

まとめ

乱択は思いつかなかった…。
変わったコインは２枚しかないから、乱択すればすぐ別のグループに分かれるのね。