| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1289 人关注过本帖
标题:一道ACM的题,请教各位?
只看楼主 加入收藏
ConZhang
Rank: 1
来 自:北京
等 级:新手上路
帖 子:282
专家分:0
注 册:2007-8-7
收藏
 问题点数:0 回复次数:18 
一道ACM的题,请教各位?

Tom and Jack are on the train. The journey is too dull so much so that both of them are eager to find a way to fritter away the time. Tom is a student of mathematics department. He proposes a funny game to play with Jack. First pile up N chips where 1<N<100000, then Jack takes away at most P=N-1 chips from the pile. After that, Tom takes away at most(or equals) Q=2*P chips from the pile. Then it turns to Jack again, he takes away at most(or equals) P=2*Q. Each time both of them have to take away at least 1 chip. In the same way, the process continues and who takes away the last chip wins the game. Jack knows there must be something tricky in the game, so he's decided to write a program to check whether there exists a win-strategy(no matter how many chips Tom takes away each time, Jack will win) for himself for a specific N. You know Jack is very good at programming, so solving this problem doesn't take him too much time. Do you know how he does?

Input Specification

The input consists of several lines, each of which consists of an integer N. The last line of the input is 0, which you shouldn't process.

Output Specification

For each N, you should output either YES or NO. If there exists a win-strategy for Jack, output YES. Otherwise output NO.

Sample Input

2
3
4
5
1000
0

Sample Output

NO
NO
YES
NO
YES
搜索更多相关主题的帖子: ACM pile chips Jack away 
2007-08-14 10:28
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
英文的大意是什么

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2007-08-14 10:38
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
第一次最多取n-1个,下一次最多取走上一次取走的两倍
取走最后一个的那个人赢

[此贴子已经被作者于2007-8-14 10:42:19编辑过]

2007-08-14 10:41
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
收藏
得分:0 
LZ``鸟语```厉害啊```

女施主``我给你``送茶来了```师太``你就从了老衲吧``
代码本天成~~~妙头偶得之```
2007-08-14 13:58
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
收藏
得分:0 
又按错``是LS```

女施主``我给你``送茶来了```师太``你就从了老衲吧``
代码本天成~~~妙头偶得之```
2007-08-14 13:59
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 

说错了,当我没说过。

[此贴子已经被作者于2007-8-14 17:05:20编辑过]

2007-08-14 14:23
totohack
Rank: 1
等 级:新手上路
帖 子:133
专家分:0
注 册:2007-7-15
收藏
得分:0 
大意是不是

Tom 和 Jack玩游戏,一堆东西有N个 (1<N<100000),Jack先取,最多取P=N-1个,然后是Tom取,最多取Q=2*P个,再Jack取,最多取P=2*Q个,继续取下去,直到取完最后一个,取到最后一个的人胜利,每个人最少取一个。

输入:
N(N不为0)
0 退出?

输出:(猜的)
如果Jack必胜,输出 YES
否则,输出 NO

2007-08-14 16:30
totohack
Rank: 1
等 级:新手上路
帖 子:133
专家分:0
注 册:2007-7-15
收藏
得分:0 
看到这个题目,就知道外国人很闲,经常没什么事做,老是找一些东西玩

2007-08-14 16:33
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
以下是引用totohack在2007-8-14 16:33:34的发言:
看到这个题目,就知道外国人很闲,经常没什么事做,老是找一些东西玩

。。。。。。。。。。。。。。。。。

-,-

2007-08-14 16:40
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
以下是引用totohack在2007-8-14 16:30:56的发言:
大意是不是

Tom 和 Jack玩游戏,一堆东西有N个 (1<N<100000),Jack先取,最多取P=N-1个,然后是Tom取,最多取Q=2*P个,再Jack取,最多取P=2*Q个,继续取下去,直到取完最后一个,取到最后一个的人胜利,每个人最少取一个。

输入:
N(N不为0)
0 退出?

输出:(猜的)
如果Jack必胜,输出 YES
否则,输出 NO

谢谢你的翻译

1 No
2 No
3 No
4 Yes
5 No
6 Yes
7 No
8 Yes
9 No

自己推了几个小数据(不保证100%准确,但应该没有问题)
推论:在N>2后 if(N mod 2 = 0) then print "Yes" else print "NO"


My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2007-08-14 17:45
快速回复:一道ACM的题,请教各位?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016790 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved