Closer's Space

梦河之上, 一叶扁舟

小米编程01月常规赛 灯


描述

一个屋子有 n 个开关控制着 n 盏灯,但奇怪的是,每个开关对应的不是一盏灯,而是 n-1 盏灯,每次按下这个开关,其对应的 n-1 盏灯就会由亮变灭,或者由灭变亮。保证不会有两个开关控制同样的 n-1 盏灯。

现在刘同学想把灯全部开好,但是这些灯一开始的状态非常乱,刘同学想知道最少需要按多少次开关才能使所有灯全部亮起。

输入

单组数据输入,每组数据一行,两个数 n,l 分别代表灯的数量、最开始时亮着的灯的数量(1<l<n<10000000000)。

输出

每组数据输出一个数,即能使所有灯全部亮起的最少的按开关的次数,如果无法做到灯全部亮起,输出“Impossible”

输入样例

4 2

输出样例

2

题解

  1. 初始状态任意亮灯位置排列答案相同
  2. 用01向量表示n个开关, 设向量组为$s=(a_1,a_2,a_3...a_n), a_i第i个分量是0,其它全1$ 则$R(s)=n-1(n为奇数), R(s) = n(n为偶数)$ 则n为偶数的时候, 异或方程式的解唯一, 且设 $b_i为第i个分量为1,其它全0的向量,则b_i=(a_1 \ or \ a_2... \ or \ a_n) \ or \ a_i$ $其中向量A \ or \ B 的结果是各分量异或后的向量$ 很容易表示出所需的向量

n为奇数的时候, n个向量异或结果为零向量, 在求出一个所需解, 解向量取1最少即可 此时n-l为奇数时无解

代码

#include <bits/stdc++.h>  
using namespace std;  
typedef long long LL;  

int main() {  
    LL n, l;  
    cin >> n >> l;  
    LL cur = n - l;  
    if(n & 1){  
        if(cur & 1) cout << "Impossible" << endl;  
        else cout << min(l, cur) << endl;  
    }else{  
        cout << (cur % 2 == 0 ? cur : l) << endl;  
    }  
    return 0;  
}

博文最后更新时间:


评论

  • 暂无评论

发表评论

来访统计

访问量:27

评论总数:0