PKU 2466 Pairsumonious Numbers
http://poj.org/problem?id=2466
N個の数字から二つの要素を取り出して足しあわせた数の集合が与えられる。
もとの数字を復元しろというような問題。
一番小さいやつと、二番目に小さい数字の和が、一番小さくなり、
一番小さい奴と、三番目に小さい数字の和が、二番目に小さくなるということを利用して、
二番目に小さい奴と三番目に小さい数字の和が何番目に小さいかを全探索しました。
bool check(const vector<int>&ans,const vector<int>&sum){ vector<int> asum; FOR(it,ans)FOR(it2,ans){ if(it==it2)break; asum.pb(*it+*it2); } sort(ALL(asum)); return asum==sum; } main(){ int n; while(cin>>n){ vector<int> in; rep(i,n*(n-1)/2){ int t; cin>>t; in.pb(t); } sort(ALL(in)); bool ok=false; rep(i,SZ(in)){ vector<int> tin(in); vector<int> ans; ans.pb((tin[0]+tin[1]-tin[i])/2); while(!tin.empty()){ ans.pb(tin[0]-ans[0]); bool end=true; for(int j=0;j<SZ(ans)-1;++j){ FOR(it,tin){ if(*it==ans[j]+ans.back()){ tin.erase(it); end=false; break; } } } if(end)break; } if(check(ans,in)){ FOR(it,ans)cout<<*it<<' ';cout<<endl; ok=true; break; } } if(!ok)cout<<"Impossible"<<endl; } }