http://noi.openjudge.cn/——4.2算法之数论——2419:Coins
题目
总时间限制: 1000ms 内存限制: 131072kB
描述
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?
输入
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.
输出
For each test case output a single line containing your answer without leading or trailing spaces. If the answer does not exist, output “No Solution!”
样例输入
2
3
0
样例输出
No Solution!
2
翻译
描述：
史努比有三枚硬币。
有一天，他把它们扔在桌子上，然后试图翻转其中的一些，这样它们要么全头朝上，要么全尾朝上。
经过几次尝试，他发现，无论硬币的初始配置如何，只要每次只能翻转一枚硬币，
并且一枚硬币可以多次翻转，他总是可以通过两次翻转来实现目标。
他还注意到，不到两个鳍，他永远不会成功。
史努比想知道，如果他有n个硬币，是否有一个最小数字x，这样他就可以做x次翻转来满足他的要求？
输入：
输入包含多个测试用例。每个测试用例由单独一行上的单个正整数n（n<10000）组成。
零表示输入结束，不应进行处理。
输出：
对于每个测试用例输出，一行包含您的答案，没有前导或尾随空格。
如果答案不存在，则输出“无解决方案！”
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
//freopen(“data.cpp”,“r”,stdin);
int n;
while(cin>>n&&n){
if(n%2)cout<<n-1<<endl;//奇数个硬币有最低翻转次数n-1
else cout<<“No Solution!\n”;//偶数没有
}
return 0;
}
举例
奇数有最低翻转次数：
3个硬币，最低翻转次数3-1=2
情况1都是反000，把第一枚翻过去100再返回来000，翻了两次，全反。
情况2有1正100，把后两个翻过去111，两次
5个硬币，最低次数5-1=4
全反00000，随便翻偶数次，能还原
1正10000，翻四个，全正
2正11000，翻两正为反，再随便选一个翻过去翻回来。
偶数没有最低翻转次数：
2个正00，一个翻过去翻回来，2次
1个正10，一个翻过去，11，1次
4个正0000，过去回来，2次
1个正1000，一个翻过去，过去回来得偶数次2，共3
网上讲解
设硬币总数为N，初始时正面朝上的硬币数为N(+)，反面朝上的硬币数为N(-)。
将翻转操作分“翻转每枚硬币最多一次使它们全部正面向上或全部反面向上”和“多余翻转”两部分考虑。
显然前者的翻转操作次数为为N(+)或N(-),而后者的翻转操作次数相应为N-N(+)或N-N(-)。
X满足题意的关键是“多余翻转”的次数必须是非负偶数，也即对于任意N(+)和N(-)的组合情况总有“X-N(+)为非负偶数或者
X-N(-)为非负偶数”。
若N为偶数，则当N(+)与N(-)都为偶数时X必须为偶数，当N(+)与N(-)都为奇数时X必须为奇数，综上两种情况，X不可能存在。
若N为奇数，令N1和N2分别为N(+)和N(-)中的奇数和偶数，那么X可以是不小于N1的奇数（最小值即N）也可以是不小于N2的偶数（最
小值即N-1）。
综上两种情况，X应取N-1。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/nanchengbian/article/details/9077869