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

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

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 72  Solved: 48

[Submit][Status][Discuss]

## Description

贝茜和约翰在玩一个数字游戏．贝茜需要你帮助她．

游戏一共进行了G(1≤G≤100)场．第i场游戏开始于一个正整数Ni(l≤Ni≤1,000,000)．游

比如，一场游戏开始于13.贝茜将13减去3变成10．约翰只能将10减去1变成9．贝茜再将9减去9变成0．最后贝茜赢．

## Input

第1行输入一个整数G，之后G行一行输入一个Ni．

## Output

对于每一场游戏，若贝茜能赢，则输出一行“YES”，否则输幽一行“NO”

2 9 10

YES NO

## HINT

For the first game, Bessie simply takes the number 9 and wins.

For the second game, Bessie must take 1 (since she cannot take 0), and then

FJ can win by taking 9.

## Source

Silver

PS：不过虽然AC了，但是2800ms+，时限为3s，这个速度比较滚粗，于是本人打算明天再来一发优化题解么么哒！！！

1 /**************************************************************
2     Problem: 3404
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:2804 ms
7     Memory:9992 kb
8 ****************************************************************/
9
10 var
11    i,j,k,l,m,n,t:longint;
12    a:array[0..1000005,1..2] of boolean;
13    b:array[0..1000005,1..2] of longint;
14 function max(x,y:longint):longint;
15          begin
16               if x>y then max:=x else max:=y;
17          end;
18 function min(x,y:longint):longint;
19          begin
20               if x<y then min:=x else min:=y;
21          end;
22 begin
23      a[0,1]:=false;a[0,2]:=true;
24      for i:=1 to 1000000 do
25          begin
26               j:=i;k:=1;t:=9;
27               while j>0 do
28                     begin
29                          k:=max(k,j mod 10);
30                          if (j mod 10)>0 then t:=min(t,j mod 10);
31                          j:=j div 10;
32                     end;
33               a[i,1]:=false;
34               if a[i-t,2] then a[i,1]:=true;
35               if a[i-k,2] then a[i,1]:=true;
36               a[i,2]:=true;
37               if not(a[i-t,1]) then a[i,2]:=false;
38               if not(a[i-k,1]) then a[i,2]:=false;
39          end;
41      for i:=1 to n do
42          begin
44               if a[m,1] then writeln('YES') else writeln('NO');
45          end;
47  end.

0 条评论

## 相关文章

2316

### （原创）详解KMP算法

KMP算法应该是每一本《数据结构》书都会讲的，算是知名度最高的算法之一了，但很可惜，我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的...

2667

3042

### Scala简介：面向对象和函数式编程的组合

Scala简介 “Scala是一门现代的多范式编程语言，志在以简练、优雅及类型安全的方式来表达常用编程模式。它平滑地集成了面向对象和函数语言的特性。” Sc...

2796

### 2017"百度之星"程序设计大赛 - 复赛1001&&HDU 6144 Arithmetic of Bomb【java大模拟】

Arithmetic of Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

3277

### React极简教程: Hello,World!React简史React安装Hello,World

A programming paradigm is a fundamental style of computer programming. There are...

901

3517

1312

### 4. 高等数学——元素和极限

假设我们知道了整数的定义，像-3，1，17这些都属于整数Z。然后有理数则是两个整数相除q/p ，q，p属于Z，则是有理数Q。

942

### [LeetCode]String主题系列{第5,6题}

1.内容介绍 本篇文章记录在leetcode中String主题下面的题目和自己的思考以及优化过程，具体内容层次按照{题目，分析，初解，初解结果，优化解，优化解结...

3507