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