2018年12月24日,小米同学们用1008台小米Play搭建了7.9米高的圣诞树,挑战成功了1005块手机动态拼图的吉尼斯世界纪录。整个过程需要同步控制开关1000多部手机,操作十分复杂。
题目描述
现在,共有n个控制开关控制着n台小米Play,按下一个控制开关的同时,就会有n-1台小米Play的屏幕随着点亮或熄灭。不同的两个控制开关所对应控制的n-1台小米Play一定不同。
为了挑战吉尼斯世界纪录,现在需要将这n台小米Play的屏幕全部点亮,但是它们目前的状态十分混乱,雷总想要知道至少按多少次开关可以使它们全部点亮。
输入
两个用空格隔开数n和x,分别为控制开关的数量即手机的数量n和最开始时屏幕点亮的手机的数量x。
输出
使所有手机屏幕点亮的最少操作开关的次数,若无法全部点亮,则输出’’Impossible’’。
样例输入
4 2
样例输出
2
提示
数据范围:0<x<n<1e10 x,n∈Z
题解:
为了简便起见,题中的“屏幕”以“灯”来代替。
每个开关对应的是n-1盏灯,按下一个开关的时候这n-1盏灯便会由暗变亮或由亮变暗。所以可以等价地理解为按下一个开关时将所有的灯的状态反转,然后改变一盏灯的状态。
接着我们发现,若按照这个规律在原始状态下按下两次任意开关,则第一次是全部反转后改变一个灯的状态,第二次也是同样,所以共进行了两次反转所有灯和两次改变一盏灯的状态的操作,反转所有灯两次就相当于没有反转,所以按两下开关就相当于在原始状态下改变了两盏灯的状态。
通过合理外推,我们可以很轻松地得到:操作奇数次时,相当于反转所有灯后改变与操作次数相等数量的灯的状态;操作偶数次时相当于改变与操作次数相等数量的灯的状态。
这就是本题的核心思路了:
- 不反转灯,按偶数次开关使所有灯亮起;
- 所有灯反转一次,按奇数次开关使所有灯亮起。
剩下的判断条件,就应该很简单了吧。