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