#P3404. [Usaco2009 Open]Cow Digit Game又见数字游戏

    ID: 2595 传统题 1000ms 512MiB 尝试: 231 已通过: 143 难度: 3 上传者: 标签>难度分类普及-博弈论必胜/必败状态递推动态规划线性 DPCF1200Silver

[Usaco2009 Open]Cow Digit Game又见数字游戏

[USACO 2009 Open] Cow Digit Game 又见数字游戏

题目描述

贝茜和约翰玩 GG 场数字游戏,每场从一个正整数 NiN_i 开始。贝茜先手,随后两人交替操作。每次可以从当前整数中减去它在十进制下的最大数码,或减去它的最小非零数码。例如,面对 3 0143\,014,可以减去 11 得到 3 0133\,013,也可以减去 44 得到 3 0103\,010。

把数变成 00 的一方获胜。假设双方总是选择最有利的走法,请判断每场游戏贝茜能否获胜。

例如,从 1313 开始时,贝茜可以减去 33 得到 1010,此时约翰只能减去 11,留下 99。贝茜再减去 99 即可获胜。

输入格式

从标准输入读入。第一行是一个整数 GG。接下来 GG 行,第 ii 行是一个整数 NiN_i。

输出格式

向标准输出输出 GG 行。第 ii 行在贝茜能赢第 ii 场时输出 YES,否则输出 NO。

2
9
10
YES
NO

样例解释

第一场中,贝茜直接减去 99。第二场中,贝茜只能减去 11,随后约翰减去 99 获胜。

数据范围与约定

1≤G≤1001\le G\le100,1≤Ni≤1061\le N_i\le10^6。