天秤測りを３回だけ使って、重さの違う玉を見つける手順

http://anond.hatelabo.jp/20160629132908

９つの玉があります。

ひとつだけ重さの違う玉があります。

天秤測りを３回だけ使って、重さの違う玉を見つける手順を示しなさい。

うっかり寝る前に見たら考え始めてしまった。面白かったので起き出して解いた。
睡眠時間が減ってしまった。反省。

#include <iostream>
#include <vector> 
using namespace std; 

int right_hand_is_greater(int a, int b){
	if(a>b) return -1;
	if(a<b) return 1;
	return 0;
}

int solve(vector<int> v){
	int firstone=right_hand_is_greater(v[0]+v[1]+v[2],v[3]+v[4]+v[5]);
	
	if(firstone==0){
		// answer is 6 or 7 or 8
		if(v[6]!=v[7]){
			// answer is 6 or 7
			if(v[6]!=v[8]) return 6;
			else return 7;
		} else {
			return 8;
		}
	} else {
		// answer is between 0 to 5
		
		int secondone=right_hand_is_greater(v[0]+v[1]+v[2],v[6]+v[7]+v[8]);
		if(secondone==0){
			// answer is between 3 to 5
			int thirdone=right_hand_is_greater(v[3],v[4]);
			if(thirdone==0){
				return 5;
			} else {
				// answer is 3 or 4
				if(firstone>0){// false ball is heavy
					if(thirdone>0) return 4;
					else return 3;
				} else {
					if(thirdone>0) return 3;
					else return 4;
				}
			}
		} else {
			// answer is between 0 to 2
			int thirdone=right_hand_is_greater(v[0],v[1]);
			if(thirdone==0){
				return 2;
			} else {
				// answer is 0 or 1
				if(firstone>0){// false ball is light
					if(thirdone>0) return 0;
					else return 1;
				} else {
					if(thirdone>0) return 1;
					else return 0;
				}
			}
		}
	}
	return -1;
}


int main(void){
	int ret=0;
	// heavy ball test
	for(int i=0; i<9; ++i){
		vector<int> v(9,100);
		v[i]=101;
		int ans=solve(v);
		cout<<"ground_truth="<<i<<", your_answer="<<ans<<endl;
		if(i!=ans) ++ret;
	}
	// light ball test
	for(int i=0; i<9; ++i){
		vector<int> v(9,100);
		v[i]=99;
		int ans=solve(v);
		cout<<"ground_truth="<<i<<", your_answer="<<ans<<endl;
		if(i!=ans) ++ret;
	}
	cout<<endl;
	if(ret==0) cout<<"All answers were correct!!"<<endl;
	else cout<<ret<<(ret==1?" answer":" answers")<<" were wrong!!"<<endl;
	return 0;
}

追記：お、回答みたら同じ解き方だったっぽい。

追記2：ちなみに10個に増えた場合は

			return 8;

のかわりに

			// answer is 8 or 9
			if(v[6]!=v[8]) return 8;
			else return 9;

でよい。

追記3：ブコメみたら13個までいけるのか！そこまではとても考えられないわ・・・