Search on the blog

2016年7月3日日曜日

SRM 653 Div2 250 CountryGroup

問題概要
椅子にn人の人が座っている。同じ国から来た人は必ず隣に座っているらしい。
左から順に、あなたの国からは何人の人がここにいますか?と聞いていく。
これに対する回答がn個与えられるので、矛盾しないかどうかと矛盾しない場合は何カ国の人がここにいるかを求めよ。

解法
stackを使うと綺麗に書ける。
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

class CountryGroup {
  public:
  int solve(vector<int> a) {
    int r = 0;
    while (a.size()) {
      int x = a.back();
      REP (i, x) {
        if (a.empty() || a.back() != x)
          return -1;
        a.pop_back();
      }
      ++r;
    }
    return r;
  }
};

0 件のコメント:

コメントを投稿