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