网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
XOR门
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 09:15 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 09:15 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 09:15 |
输入文件 | xor.in | 输出文件 | xor.out |
一个XOR门包含两个输入和一个输出,它的工作可以用下表描述:
input 1 input 2 output 0 0 0 0 1 1 1 0 1 1 1 0
如果一个XOR门系统有n个输入和1个输出,且满足以下条件,则称这个XOR门系统为XOR网络。
- 系统的每一个输入都至少与一个XOR门的输入端相连;
- 系统中每个门的输入必须与系统的一个输入或另一个门的输出连接;
- 有且只有有一个门的输出与系统的输出相连;
- 每个门的输出要与另外至少一个门的输入或系统的输出相连;
- 这些XOR门存在一种编号方式,使得每个门的输入都与系统的输入或具有较小编号的门的输出相连。
例子:
图中有一个由6个XOR门组成的XOR系统。它有5个输入和1个输出,它满足以上的5个条件,所以它是一个XOR网络。注意:图中给出的编号方式不满足条件5,但可以找到一种满足条件的编号方式。
网络的输入标号为1到5,一种输入状态可以用一个长度为n的字符串表示,每一位是0或1,我们假设第I个数字表示第I个输入的状态。每一个 输入都是一个自然数的二进制编码,所以我们可以按输入状态表示的数值的大小将它们排序。我们要测试一个电路门网络,通过向它发送一个范围以内的输入,计算 使输出是1的输入个数。
任务:
- 从文本文件xor.in中读入电路网的的描述。描述包括输入的个数n,XOR门的个数m,以及XOR门连接的情况。
- 从文件中读入两个长度为n的二进制串,表示输入的上限和下限。
- 计算给定范围内有多少种输入可以使输出为1。
- 将结果写入文件xor.out。
我们假设3 < n < 100, 3 < m < 3000,而且网络中的门是用1到m之间的数任 意编号的。
输入格式: 文件第一行包含三个整数,分别表示输入的个数,门的个数,连接到输出的门的编号。以下的m行描述网络中的连接情况。第I行表示第I个门的两个输入,两个输 入为范围[-n,m]之间的一个整数。如果输入是网络的第k个输入,则连接的描述是一个整数-k,如果输入是第j个门,则连接的描述是一个整数j。以下两 行各有一个n位二进制串,表示输入的上限和下限。我们假设给定范围内最多100000种输入。
输出格式: 输出文件包含一个整数,表示给定范围内有多少种输入可以使输出为1。
样例:
输入文件xor.in:
5 6 5 -1 -2 1 3 1 -2 2 -3 4 6 -4 -5 00111 01110
输出文件xor.out
5