http://codeforces.com/contest/911/problem/C
3つの電灯がある。
電灯は時間x, x+k, x+2k, x+3k, ... で点灯する。
3つの電灯のkの値だけ分かっている。
各電灯のxの値を適切に決めることで全ての時間で最低1つは点灯している状態に出来るか判定せよ。
解法
http://codeforces.com/contest/911/submission/33719726
k1,k2,k3の3つの電灯について、xの大きさの大小を全探索して考えよう。
つまり、xの大きさ順に[k1,k2,k3],[k1,k3,k2],[k2,k1,k3],[k2,k3,k1].[k3,k1,k2],[k3,k2,k1]を全て確かめていく。
確かめる作業では貪欲にやっていけば良い。
どの時間までチェックすればよいかだが、自分は適当に10^6くらいまでの時間チェックしてみて、全点灯しているかを確認した。
#define LIM 1010101 //--------------------------------------------------------------------------------------------------- void _main() { vector<int> ks; rep(i, 0, 3) { int x; cin >> x; ks.push_back(x); } sort(ks.begin(), ks.end()); do { vector<int> v(LIM, 0); int k = 0; rep(i, 1, LIM) if (!v[i]) { for (int j = i; j < LIM; j += ks[k]) v[j] = 1; k++; if (k == 3) break; } int ok = 1; rep(i, 1, LIM) if (!v[i]) ok = 0; if (ok) { printf("YES\n"); return; } } while (next_permutation(ks.begin(), ks.end())); printf("NO\n"); }