2011 TCO Algorithm Qualification Round 1 easy
問題概要
ある人たちに少なくとも何人この中に嘘つきがいるか聞く。
嘘つきな人は、絶対実際より多い数をいう。
正直な人は、実際以下の人数をいう。
考えられる最低の嘘つきの人数を答えよ。
解法
考えられる人数の人数を全部試す。
嘘つきの人数を決めると、ある人について必ず、
嘘つきが嘘つきでないかが確定する。
嘘つきの人数が、想定した人数と矛盾しなければ、その人数が最小の人数となる。
ソース
#include<algorithm> #include<vector> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) #define ALL(C) (C).begin(),(C).end() using namespace std; class MinimumLiars{ public: int getMinimum(vector <int> claim){ sort(ALL(claim)); rep(i, claim.size()+1){ int l = 0, t = 0, base = i; rep(j, claim.size()){ if(claim[j] <= base)t++; else l++; } if(l == i)return i; } return -1; } };