SPOJ-NGM : A Game with Numbers
問題概要
二人であるゲームをする。今数xがあって、各プレイヤーは交互にxに含まれる数字(10進数表記の下)で0でないものを選び、xから引く。xを0にしたプレイヤーの勝ちとなる。両者が最善を尽くしたとき勝つのがどちらか判定する問題。先手が勝つ場合は初手に何を引くべきかも出力する。
解法
テストコードは簡単にかけて、小さいところで試すと10の倍数以外は先手勝ちになっていることが分かる。実際その予想は正しく、10の倍数からはかならずそうでない状態にしか行けず、そうでない状態からは%10の値を引けば10の倍数を作ることができる。
acceptされたコード
計算量O(1)。
#include <cstdio> using namespace std; int main(){ int x; scanf("%d", &x); if(x % 10 == 0){ puts("2"); } else{ puts("1"); printf("%d\n", x%10); } return 0; }