HZNUOJ 1813 黑帽子和白帽子

Time Limit: 1 s Memory Limit: 32 MB

Description

也许你们听说过“黑帽子和白帽子”问题，这是一个非常经典的问题，大概是这样子表述的：
一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
现在我们希望你来帮忙求解这类问题，假设给定舞会的人数n和关灯次数m，求戴黑帽子的人数。

Input

有多组输入，每组占一行，包含两个正整数n和m (0<m<n<=100) 。

Output

对于每组输入，输出戴黑帽子的人数，每组输出占一行。

这道题其实有一个隐藏前提就是每个人都玩过且很会玩这个游戏（即绝顶聪明）。我们可以将自己代入情景模拟一遍找到规律，然后就会发现这其实是一道简单的输入输出的问题，即每组都读入n、m，然后原封不动地将m输出即可。

下面我们来模拟一遍。

首先因为题目中写道是一群人且0<m<n<=100（n、m都是正整数），所以n>=2，n>m>=1。
两个人时(n=2)，不用讨论，因为m必为1。

三个人时(n=3)，若你看到两顶白帽，很容易就能知道自己是那个带黑帽子的人（m>=1），在第一次关灯就会打自己。①

若看到一黑一白，你此时无法确认自己是什么颜色，当第一次关灯时，若听到巴掌声，那你的帽子就是白色的（同①理）；若没有听到巴掌声，就说明有一个人看到的情况是跟你一样的他也不能确定自己的颜色，且没有人看到两顶白帽，所以由此得出，你自己戴的是黑帽，在第二次关灯时会打自己，且此时场上有两顶黑帽。②

四个人时(n=4)，若第一次关灯就有人打自己，即有人看到了三顶白帽子然后推测自己是黑帽，所以在场有一顶黑帽。③

若你一开始看到的是一黑二白，且第一次关灯没有巴掌声，你马上就能知道自己是那另一个戴黑帽的，在第二次关灯时就会打自己，即此时在场有两顶黑帽。④

若你一开始看到的是两黑一白，且第一次关灯没有巴掌声，此时你并不知道你是否为情况④里其中一个白帽子，还是说在场有三顶黑帽而你是其中一个。所以你需要听第二次关灯有无巴掌声。若有，同④；若没有，你可以知道那俩个黑帽看到的是跟你一样的情形，所以你是黑帽，在第三次关灯时就会打自己，即此时在场有三顶黑帽。
……………………
………………

后面的情况不再赘述。 若继续模拟下去，会发现无论在场多少人，你的判断方法都是这样的。即白帽数量的增减并不会影响关灯次数与黑帽个数的对应关系，所以无论n为多少，只需要知道在第几次关灯时响起巴掌声，在场就有几个黑帽子。

得出了以上这个结论以后，代码实现即可。
需要注意的点就是未限定组数的多组输入。

#include<stdio.h>
int main()
{int n,m;while(~scanf("%d %d",&n,&m)){printf("%d\n",m);	}return 0;
} 

（要是我讲的不够清晰的话，希望大家可以去找找其他人对这个问题的解释，尽力去理解一下）