灯
序号:#125 难度:有挑战 时间限制:1000ms 内存限制:32M
描述
一个屋子有 n 个开关控制着 n 盏灯,但奇怪的是,每个开关对应的不是一盏灯,而是 n-1 盏灯,每次按下这个开关,其对应的 n-1 盏灯就会由亮变灭,或者由灭变亮。保证不会有两个开关控制同样的 n-1 盏灯。
现在刘同学想把灯全部开好,但是这些灯一开始的状态非常乱,刘同学想知道最少需要按多少次开关才能使所有灯全部亮起。
输入
单组数据输入,每组数据一行,两个数 n,l 分别代表灯的数量、最开始时亮着的灯的数量(1<l<n<10000000000)。
输出
每组数据输出一个数,即能使所有灯全部亮起的最少的按开关的次数,如果无法做到灯全部亮起,输出“Impossible”
输入样例
4 2
复制样例
输出样例
2
题意:中文题不解释;
题解:
首先看到数据量很大,想到有公式,或者有规律,然后想到可能跟n,l的奇偶性有关。然后举最简单的例子试一下就知道结论了。
当时做的时候想到奇偶性了,没认真讨论一下看看,后来看到别人这样写的才知道了,还是自己太菜了~~~
先说结论:
n l
奇数 奇数 min(n-l,l)
偶数 偶数 n-l
偶数 奇数 l
奇数 偶数 Impossible
下面举例子:
z代表亮 x代表灭
奇数 奇数: 5 3 是 2 zzzxx->xxxzx->zzzzz 9 3 是 3: zzzxxxxxx->zxxzzzzzz->xxzxxxxxx->zzzzzzzzz
偶数 偶数: 6 2 是 4 zzxxxx->xxzzzx->zzxxzz->zxxxxx->zzzzzz
偶数 奇数: 4 3 是 3 zzzx->zxxz->xzxx->zzzz
奇数 偶数: 3 2 是 Impossible zzx->xxx->xzz->zxz->xzz->zxz->xxx->zzx->........->死循环,不可能全亮
以上就是最少按开关的次数,如果发现更少的,欢迎各位大佬评论~~~
上代码:
#include <iostream>
using namespace std;
typedef long long ll;//注意取值范围!!
int main(){
ll n,l;
cin >> n >> l;
if((n&1)&&(l&1)) cout << min(n-l,l) << endl;//奇数 奇数
else if(!(n&1)&&!(l&1)) cout << n-l << endl;//偶数 偶数
else if(!(n&1)&&(l&1)) cout << l << endl;//偶数 奇数
else cout << "Impossible" << endl;//奇数 偶数
return 0;
}