Three Garlands [Educational Codeforces Round 35 C]

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