SRM481 Div1 Easy(250), Div2 Medium(500) ChickenOracle
lieCount人とliarCount人の答えを逆にして全員の答えを卵もしくは鶏にすると考える。答えを逆にできるのは、|lieCount-liarCount|以上、lieCount+liarCountおよびn-(lieCount+liarCount-n)以下、偶奇がlieCount-liarCountと一致する人数。
n-(lieCount+liarCount-n)以下も偶奇が一致することも気付かなかった。O(n)で間に合うのだからO(n)で確実に書くべきだった。
#include <string> #include <algorithm> using namespace std; class ChickenOracle{public: string theTruth( int n, int eggCount, int lieCount, int liarCount ) { int mn = abs( lieCount-liarCount ); int mx = min( lieCount+liarCount, n-(lieCount+liarCount-n) ); bool e = mn<=(n-eggCount) && (n-eggCount)<=mx && (n-eggCount)%2==mn%2; bool c = mn<=eggCount && eggCount <=mx && eggCount %2==mn%2; if ( e && !c ) return "The egg"; if ( !e && c ) return "The chicken"; if ( e && c ) return "Ambiguous"; return "The oracle is a lie"; } };