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;
  }
};