mayoko’s diary

プロコンとかいろいろ。

SRM 690 div1 easy: WolfCardGame

問題

1, 2, ..., 100 が書かれたカードを使って A 君と B 君がゲームをする(カードはそれぞれ 1 枚ずつ)。

ある数 N, K が与えられて, A 君は K 枚のカードにかかれている数を足し引きして合計を N にしたい。
B 君はカードを上手く選ぶことによって A 君がどう頑張っても 和を N に出来ないようにしたい。出来ないようにできたら B 君の勝ちで, 出来る足し引きが存在するなら A 君の勝ちである。

B 君が勝つようなカードの選び方は存在するか。存在するならその一例を示せ。

解法

(a の倍数) + (a の倍数) = (a の倍数) となることを利用します。

a = 2, 3, 4, 5 については, 「N が a の倍数でなかったら a, 2*a, ..., K*a を選択」という戦略を取れば必ず B 君は勝てます。

これを使うと, N = 60 以外では必ず勝ちます。また, K < 15 の時は, 7, 14, ..., 7*K を選択すれば 100 を超えた数字を使うことなく B 君は勝ちます。

後は K = 15 の時ですが, 7, 14, ..., 98 と 1 を追加すると勝てます。もとのカードでは 7 の倍数しか表現できませんが, ここから ±1 やったところで 60 にならないからです。
これじゃ不安, という場合は適当にチェック関数書けば良いでしょう(2^K か 100*K*K で出来る)。

for 文使えばよかったねコード↓

class WolfCardGame {
public:
    vector <int> createAnswer(int N, int K) {
        vector<int> ans;
        if (N%2) {
            for (int i = 1; i <= K; i++) ans.push_back(2*i);
            return ans;
        }
        if (N%3) {
            for (int i = 1; i <= K; i++) ans.push_back(3*i);
            return ans;
        }
        if (N%4) {
            for (int i = 1; i <= K; i++) ans.push_back(4*i);
            return ans;
        }
        if (N%5) {
            for (int i = 1; i <= K; i++) ans.push_back(5*i);
            return ans;
        }
        for (int i = 1; i <= K; i++) ans.push_back(7*i);
        if (K==15) {
            ans.pop_back();
            ans.push_back(1);
        }
        return ans;
    }
};