GCJ 2016 Qualification Round D: Fractiles

解法

2世代目のパネルには、1枚を見るだけで1世代目のパネルの1枚目と2枚目を同時に調べられるパネルがある。同様に、3世代目には1世代目のパネルを3枚同時に調べられるパネルがある。このように考えると、Cが大きければ大きいほど、少ないパネル数でGの有無を調べることが出来る。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

set<ll> solve(int K, int C) {
  set<ll> ans;
  ll orig_pos = 0;
  while (orig_pos < K) {
    ll real_pos = orig_pos;
    for (ll i = 1; i < C; ++i) {
      ll pos_in_block = real_pos % K;
      real_pos=real_pos*K+pos_in_block;
      if (orig_pos < K - 1) {
        orig_pos++;
        real_pos++;
      }
    }
    ans.insert(real_pos);
    orig_pos++;
  }
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int testcase = 1; testcase <= T; ++testcase) {
    int K, C, S;
    cin >> K >> C >> S;
    set<ll> ans = solve(K, C);
    cout << "Case #" << testcase << ":";
    if (ans.size() > S) {
      cout << " IMPOSSIBLE";
    } else {
      for (ll a : ans) cout << " " << (a + 1);
    }
    cout << endl;
  }
}