注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

The Bloom of Youth

本博客已搬家至http://kuangqi.me

 
 
 

日志

 
 

POJ 3210 Coins题解  

2009-11-04 23:02:07|  分类: 真回收站 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

Description

Snoopy has three coins. One day he tossed them on a table then and tried to flip some of them so that they had either all heads or all tails facing up. After several attempts, he found that regardless of the initial configuration of the coins, he could always achieve the goal by doing exactly two flippings, under the condition that only one coin could be flipped each time and a coin could be flipped more than once. He also noticed that he could never succeed with less than two flippings.

Snoopy then wondered, if he had n coins, was there a minimum number x such that he could do exactly x flippings to satisfy his requirements?

 

Input

The input contains multiple test cases. Each test case consists of a single positive integer n (n < 10,000) on a separate line. A zero indicates the end of input and should not be processed.

 

Output

For each test case output a single line containing your answer without leading or trailing spaces. If the answer does not exist, output “<code>No Solution!”

 

Sample Input

2

3

0

 

Sample Output

No Solution!

2

题意:桌子上有N枚硬币,翻转X次(必须是N次,不能多也不能少)。同一硬币可以翻多次。使得不论原始状态如何,翻完后硬币是同一面朝上。

解法:当N为偶数时无解,当N为奇数时结果为N-1.由于解法简单,就不贴代码了~

分析:

1.       若N为偶数。两种硬币的组合可能是(奇数+奇数)或者(偶数+偶数)。当正面硬币数目和反面硬币数目均为偶数时,想要同一面朝上,翻转次数必为偶数。若正面硬币和反面硬币都是奇数,则翻转次数必为奇数。两者矛盾。所以在N为偶数时无解。

2.       若N为奇数。两种硬币的组合可以是(奇数+偶数)。若所有的硬币开始就是同一面朝上,则翻转次数必为偶数。若不是同一面朝上,由于翻转次数为偶数,故必须将数目为偶数的那部分硬币反过来。当只有一枚硬币与其他硬币不同时,出现的是可能的最大数目即为N-1.故N为奇数时,翻转次数为N-1.

  评论这张
 
阅读(1154)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018