PKU 2856 Medals

http://poj.org/problem?id=2856

それぞれの国が取得した金メダル、銀メダル、銅メダルの個数が与えられる。
全てのメダルの個数の合計をnとしたときに、
(1/(n^i),1/(n^j),1/(n^k))というベクトルとメダルの個数ベクトルの内積が一番大きい国をトップにしたい。
i,j,kを適当に設定してカナダをトップにできるかどうかを答えろというような問題。

それぞれの係数の重みを適当に全探索すればよい。

int n;
string name[20];
int arr[20][3];

void solve(){
  int sum=0;
  rep(i,n){
    cin>>name[i]>>arr[i][0]>>arr[i][1]>>arr[i][2];
    rep(j,3) sum+=arr[i][j];
  }

  int kei[]={1,sum,sum,sum,sum*sum};
  do{
    int maxs=0;
    rep(i,n)
      maxs=max(maxs,
               arr[i][0]*kei[0]+arr[i][1]*kei[1]+arr[i][2]*kei[2]);
    rep(i,n)
      if(name[i]=="Canada" &&
         maxs==arr[i][0]*kei[0]+arr[i][1]*kei[1]+arr[i][2]*kei[2]){
        cout<<"Canada wins!"<<endl;
        return;
      }
  }while(next_permutation(kei,kei+5));
  
  cout<<"Canada cannot win."<<endl;
}

main(){
  while(cin>>n,n)
    solve();
}