SRM690 Div1 Easy "WolfCardGame"
問題
リンク無し!
訳
狼のSotheと猫のSnukeがカードゲームで遊んでいる。このゲームはちょうど100枚のカードを使う。カードには1から100の数字が書かれている。ゲームの遊び方については以下の通り。
1. 初めに、猫のSnukeが1から100の中から数字のNを選び、これをゴールとする。 2. それから、狼のSotheが100枚のカードからちょうどK枚選び、Snukeに渡す。 3. 次に、猫のSnukeが渡されたK枚のカードから何枚かカードを捨てる。 彼は渡されたカードの任意のサブセットを捨てるカードとして選ぶことができ、 それはカードをまったく捨てなくてもよいし、全てのカードを捨ててもよい。 4. 最後に、猫のSnukeは、彼がまだ持っているカードのうち、 任意のサブセットのカードを選び、そこにマイナスの記号を書く。 例えば彼が{1, 3, 4, 7}のカードを持っていたとしたら、 {-1, 3, 4, -7}などとなる。
このゲームの終わりでは、Snukeが持っているカードに書かれている数字の合計を計算する(この時、追加されたマイナスの記号を考慮する)。それがゴールであるNと等しいならば、Snukeの勝ちである。そうでなければSotheの勝ちである。
あなたには狼のSotheがゲームに勝つための手助けをしてもらいたい。今、ゲームはStep2の局面である。あなたには、Snukeが決めたint Nと、Snukeに渡すカードの枚数であるint Kが与えられる。Snukeがゲームに勝つ事ができないように、K枚のカードを選んでほしい。もし複数の答えがあるのであれば、どれを返してもよい。答えがないのであれば、空のリストを返すこと。
解法
dの倍数の数字同士で、それらを足し引きすると必ずdの倍数となる。
この性質を踏まえると、Nがdの倍数でないときは、{d * 1, d * 2, ... , d * K}のカードを選べばよいことになる。
ただし、N = 60の時だけは2, 3, 4, 5, 6の何れも倍数となり、7がdとなる。
7 * 15 = 105であり、N = 60, K = 15のときにまずいので、リストには105の代わりに1などを追加してあげる必要がある。
ソースコード
bool P[101]; class WolfCardGame { public: vector<int> createAnswer(int N, int K) { if (N == 60 && K == 15) { int data[] = {7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 1}; vector<int> ans(data, data + K); return ans; } int d = 0; for (int i = 2; i <= 7; i++) { if (N % i != 0) { d = i; break; } } vector<int> ans; for (int i = 1; i <= K; i++) { ans.push_back(d * i); } return ans; } };