Description
一群非常聪明的人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其它人帽子的颜色,却看不到自己的。主持人先让大家 看看别人头上戴的是什幺帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然 鸦雀无声。一直到第n次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子,多少人戴着白帽子?
Input
多组测试数据。每组输入2个整数k和n,分别表示总人数和第几次关灯时有声音
Output
每组一行,输出2个整数表示戴黑帽子的人数和戴白帽子的人数
Sample Input
2 1
3 1
Sample Output
1 1
1 2
情况分析:
问题的关键就在于何时才能确认自己是否真正为黑色!
所有的问题都把自己当做黑帽子的人考虑
一:两个人的情况
①1白1黑
只要睁眼,黑色帽子的人的眼中必然只有白色帽子,所以会打自己耳光!
二:三个人的情况
①2白1黑
只要黑色帽子的人睁眼,必然会打自己耳光。
②1白2黑
第一次闭眼:没有声音,假设自己是黑帽子,那么,在闭眼中,之所以不打自己耳光,是因为自己的眼中有1黑1白,所以此时无法确认自己是否是黑帽子。
此时,情况分为两种,假设晚上的时候那个头戴黑帽子的人没有发出声音,那么,他的眼中很显然是有黑帽子的,排除了那个白色帽子的人选,剩下的,必然自己是黑帽子。
所以
第二次的时候会有声音。
三:四个人的情况
同理分析即可。
3白1黑:一次
2白2黑:两次
1白3黑:三次
第一次:我的眼中有两个黑,晚上没声音,说明另外两个人眼中也有黑色,其中一者的眼中必然有另一者的黑色帽子。
此时,无法确认自己是否是黑帽子,除非第二天晚上没有发出声音,这个时候才能够确定,在“其他黑帽子人”的眼中,有两顶黑帽子。
所以,第二天晚上也没有声音
在第三天晚上,已经知道别人眼中有两个黑帽子了,排除了白帽子的,那么剩下的,自己肯定就是黑帽子
综上所述,黑帽子的人要确认自己是否是黑帽子,就一定要花费n-1次来确认。
如果还没明白的,自己可以分析一下四个人的情况
代码还是很简单的,就是逻辑关系而已
//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n") int main(){
int a, b;
while(scanf("%d%d", &a, &b) != EOF){
printf("%d %d\n", b, a-b); }
return ;
}