PKU : 1013 - Counterfeit Dollar

実装問題

問題概要

http://poj.org/problem?id=1013
日本語訳：http://wikiwiki.jp/pku/?1013%20Counterfeit%20Dollar

アルゴリズム

同じ重さのコインがなるべく先にわかっていた方がいいと思ったので, evenから順番に考えた. 条件を列挙して考えればいい.

  • evenのとき
    • 左右のコインはすべて同じコイン（重くも軽くもないコイン）
  • downのとき
    • 左側のコインの内, 通常のコイン以外において, 軽いという確率が上がる
    • 右側のコインの内, 通常のコイン以外において, 重いという確率が上がる
    • もし, 軽い確率が出ていたのに重い確率も出てしまうようなコインが発生したら, これは通常のコインになる
  • upのとき
    • downの反対の作業を行えばいい

あとは, 重いor軽い確率が一番高いコインを選べばよい.

A B down
A C down
D E even

↑みたいのだと, 「Aは軽い」「Bは重い」「Cは重い」という可能性が出てくるが, Aが二回upしていることから, 「Aは軽い」という確率が強くなり, これが答えとなる.

プログラム

無駄に長いプログラム

class P{
public:
  string left,right,state;
  P(){}
  bool operator<(const P &p)const{
    if(state == "even") return true;
    if(p.state == "even") return false;
    return state < p.state;
  }
};

int main(){
  int T;
  cin>>T;

  while(T--){
    P t[3];
    for(int i=0;i<3;i++){
      cin>>t[i].left>>t[i].right>>t[i].state;
    }
    sort(t,t+3);

    int same[128],heavy[128],light[128];
    memset(same,0,sizeof(same));
    memset(heavy,0,sizeof(heavy));
    memset(light,0,sizeof(light));

    for(int i=0;i<3;i++){
      string left = t[i].left;
      string right = t[i].right;
      string state = t[i].state;

      if(state == "even"){
        rep(j,left.size()){
          same[left[j]] = same[right[j]] = 1;
          heavy[left[j]] = heavy[right[j]] = light[left[j]] = light[right[j]]= 0;
        }
      }

      else if(state == "down"){
        rep(j,left.size()){
          if(!same[left[j]]){
            light[left[j]]++;
            if(heavy[left[j]]){
              light[left[j]] = heavy[left[j]] = 0;
              same[left[j]] = 1;
            }
          }
          if(!same[right[j]]){
            heavy[right[j]]++;
            if(light[right[j]]){
              light[right[j]] = heavy[right[j]] = 0;
              same[right[j]] = 1;
            }
          }
        }
      }

      else{
        rep(j,left.size()){
          if(!same[left[j]]){
            heavy[left[j]]++;
            if(light[left[j]]){
              light[left[j]] = heavy[left[j]] = 0;
              same[left[j]] = 1;
            }
          }
          if(!same[right[j]]){
            light[right[j]]++;
            if(heavy[right[j]]){
              light[right[j]] = heavy[right[j]] = 0;
              same[right[j]] = 1;
            }
          }
        }
      }
    }

    int maxCnt = -1;
    char alpha = ' ';
    bool heavyFlg = false; //false:light, true:heavy
    for(int i='A';i<='L';i++){
      if(same[i]) continue;
      if(maxCnt < heavy[i] || maxCnt < light[i]){
        alpha = i;
        if(heavy[i] > 0){
          maxCnt = heavy[i];
          heavyFlg = true;
        }
        else{
          maxCnt = light[i];
          heavyFlg = false;
        }
      }
    }

    cout<<alpha<<" is the counterfeit coin and it is "<<(heavyFlg ? "heavy" : "light")<<".\n";
  }
}