编程介的小学生 2019-06-26 12:50 采纳率: 20.5%
浏览 127

最小的需要设置的开关,怎么用C语言程序编程的过程实现出来的程序来计算数量

Problem Description
An antique machine with C(n , 3) switches capable of processing integers in the range 0...2N-1 has just been discovered. Each switch is associated to a distinct integer in 0...2N-1 with exactly three ones in its binary representation. By setting switches associated with number X0,X1...XM-1 to on, any integer Y passing through the machine will render a result of Y⊕X0⊕X1⊕...⊕XM-1(here “⊕” stands for bitwise-XOR).
Further inspections reveal that contrary to what we assumed in problem B, some of the switches on the machine are damaged due to their old age. We are interested in whether a configuration transforming integer S into T still exists, and if so, the minimum number of switches that have to be set to on to make it possible.
WARNING: a naive algorithm might not be sufficient to solve this problem.

Input
There are multiple test cases in the input file.
Each test case starts with two integers, N and M ( 1 ≤ N ≤ 20), representing the number of bits and the number of functioning switches, respectively. Two integers, S and T ( 0 ≤ S,T < 2N), come in the next line, followed by another M lines, the ith one describing the value Vi associated to the ith switch ( 0 ≤ Vi < 2N).
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

Output
For each test case, please print a single integer, the minimum number of
operations, or “Impossible” (without quotes) if no feasible sequence exists.

Sample Input
6 7
55 21
11
22
25
56
41
49
28
5 2
0 21
22
28
0 0

Sample Output
Case #1: 2
Case #2: Impossible

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿
    • ¥100 关于使用MATLAB中copularnd函数的问题