SRM481 Easy: ChickenOracle

keyword

集合　C++

概要

卵が先か鶏が先かという質問にOracleが答える。n人に答えてそのうちlie人に嘘を答える。n人の内liar人は教えられたものと反対のことを言う。n人のうちegg人が答を卵と答えた。答えは卵か、鶏か、どちらの可能性もあるか、どちらの可能性もないかを答える問題。
lieとliarの積集合をi人として探索すれば良い。このときlieとliarの和集合がn人を越えないように注意する(これに気づかずに本番で落ちた)。

class ChickenOracle {
public:
string theTruth(int n, int egg, int lie, int liar) {
    int chicken = n - egg;
    bool isEgg = false, isChicken = false;
    isEgg = checkEgg(n, egg, chicken, lie, liar);
    isChicken = checkChicken(n, egg, chicken, lie, liar);
    if(isEgg){
        return isChicken?"Ambiguous":"The egg";
    }
    else
        return isChicken?"The chicken":"The oracle is a lie";
}

bool checkEgg(int n, int egg, int chicken, int lie, int liar){
    int i;
    for(i=0;i<=min(lie,liar); i++)
        if((lie+liar-i)<=n && (lie - i) + (liar - i) == chicken) return true;
    return false;
}

bool checkChicken(int n, int egg, int chicken, int lie, int liar){
    int i;
    for(i=0;i<=min(lie,liar); i++)
        if((lie+liar-i)<=n && (lie - i) + (liar - i) == egg) return true;
    return false;
}
};