GCJ2012 Round1B C. Equal Sums

2012-05-06

14:37 |

いくつかの整数が与えられる。和が同じになる異なる部分集合を２つ見つける問題

small は部分集合とその和を全通り計算する

large は乱択らしい解説待ち。

void pr(ll i, VI& w, int N) {
	int first=1;
	REP(j, N) {
		if((i>>j)&1) {
			if(!first) cout<<" ";
			cout<<w[j];
			first=0;
		}
	}
	cout<<endl;
}

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N;
		cin>>N;
		VI w(N);
		REP(i, N) cin>>w[i];
		map<ll, ll> ma;
		int sum = accumulate(ALL(w), 0);
		int ok=0;
		REP(i, ((ll)1)<<N) {
			int A = 0;
			REP(j, N) {
				if((i>>j)&1) A += w[j];
			}
			if(ma.count(A)) {
				cout<<"Case #"<<ttt+1<<":"<<endl;
				pr(ma[A], w, N);
				pr(i, w, N);
				ok=1;
				break;
			}
			ma[A] = i;
		}
		
		if(!ok) cout<<"Case #"<<ttt+1<<": Impossible"<<endl;
	}
	return 0;
}