SRM481 Div2 500

問題

卵が先か鶏が先か。予言者がn人に「卵」か「鶏」と言った。eggC人が卵と答えた。ただし予言者はlieC人には嘘をついた。んで、liarC人は聞いたことと逆の答えを答えた。「卵」か「鶏」か「曖昧」か「予言者が嘘ついてる」で答える。

考え方

嘘をついた人のうち何人が卵(または鶏)と答えたかわからないのでループをまわす。

まず、oracleが言ったのが「鶏」かどうか確認する。
嘘をついた人の中で鶏と答えた人がi人の場合、卵だと思っている人の人数は( ( eC-(liarC-i) ) + i)人となる。
卵だと思っている人数とoracleが嘘をついた人数lieC人が等しければ「鶏」と言った可能性がある。
ただし、左にはみ出す場合(liarC-i)>eCまたは右にはみ出す場合i>cCの時はちゃんと除外する。

「卵」の場合も同様にして計算できる。

bool isChicken(int n, int eC, int lieC, int liarC){
  for(int i=0;i<=liarC; i++){
    if(liarC-i>eC) continue; //これ重要
    if(i>n-eC) continue; //まじ重要
    if(eC-(liarC-i)+i==lieC) return true;
  }
  return false;
}
bool isEgg(int n, int cC, int lieC, int liarC){
  return isChicken(n, cC, lieC, liarC);
}

class ChickenOracle {
  public:
  string theTruth(int n, int eggCount, int lieCount, int liarCount) {
    bool cc = isChicken(n, eggCount, lieCount, liarCount);
    bool ee = isEgg(n, n-eggCount, lieCount, liarCount);
    if(cc==true && ee==true) return "Ambiguous";
    if(cc==true && ee==false) return "The chicken";
    if(cc==false && ee==true) return "The egg";
    return "The oracle is a lie";
  }
};

• 反省

ちゃんと理解してなかった。そんな簡単な問題なわけがなかった。