ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4317: Bitwise Formula

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计Web Board

题目描述

B. Bitwise Formula
Bob最近读到了计算机中使用的位运算:AND, OR和XOR。他研究了它们的性质，发明了一种新的游戏。
最初，Bob选择整数m，游戏的位深度，这意味着游戏中的所有数字将由m位组成。然后他让彼得选择一个m位数。之后，Bob计算n个变量的值。每个变量都被赋予一个固定的m位数或按位运算的结果。操作的操作数可以是之前定义的变量，也可以是Peter选择的数字。在此之后，Peter的分数等于所有变量值的和。
鲍勃想知道，彼得需要选择哪个数字才能得到可能的最低分数，他需要选择哪个数字才能得到可能的最高分数。在这两种情况下，如果有几种方法可以得到相同的分数，找出他可以选择的最小数量。
输入
第一行包含两个整数n和m，分别是变量数和位深(1≤n≤5000;1≤≤1000)。
下面n行包含变量的描述。每一行只描述一个变量。描述格式如下:新变量名，空格，符号":="，空格，后面跟着其中之一:
正好是m位的二进制数。
第一个操作数，空格，位操作("AND"， "OR"或"XOR")，空格，第二个操作数。每个操作数要么是前面定义的变量名，要么是符号'?，表示彼得选择的数字。
变量名是由小写拉丁字母组成的字符串，长度不超过10。所有变量名都是不同的。
输出
在第一行中输出Peter应该选择的最小值，使所有变量值的和尽可能小;在第二行中输出Peter应该选择的最小值，使所有变量值的和尽可能大。这两个数字都应该打印为m位二进制数。
例子以上翻译结果来自有道神经网络翻译（YNMT）· 通用领域


time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Bob recently read about bitwise operations used in computers: AND, OR and XOR. He have studied their properties and invented a new game.
Initially, Bob chooses integer m, bit depth of the game, which means that all numbers in the game will consist of m bits. Then he asks Peter to choose some m-bit number. After that, Bob computes the values of n variables. Each variable is assigned either a constant m-bit number or result of bitwise operation. Operands of the operation may be either variables defined before, or the number, chosen by Peter. After that, Peter's score equals to the sum of all variable values.
Bob wants to know, what number Peter needs to choose to get the minimum possible score, and what number he needs to choose to get the maximum possible score. In both cases, if there are several ways to get the same score, find the minimum number, which he can choose.
Input
The first line contains two integers n and m, the number of variables and bit depth, respectively (1≤n≤5000; 1≤m≤1000).
The following n lines contain descriptions of the variables. Each line describes exactly one variable. Description has the following format: name of a new variable, space, sign ":=", space, followed by one of:
  1. Binary number of exactly m bits.
  2. The first operand, space, bitwise operation ("AND", "OR" or "XOR"), space, the second operand. Each operand is either the name of variable defined before or symbol '?', indicating the number chosen by Peter.
Variable names are strings consisting of lowercase Latin letters with length at most 10. All variable names are different.
Output
In the first line output the minimum number that should be chosen by Peter, to make the sum of all variable values minimum possible, in the second line output the minimum number that should be chosen by Peter, to make the sum of all variable values maximum possible. Both numbers should be printed as m-bit binary numbers.
Examples
Input 
3 3
a := 101
b := 011
c := ? XOR b
Output 
011
100
Input 
5 1
a := 1
bb := 0
cx := ? OR a
d := ? XOR ?
e := d AND bb
Output 
0
0
Note
In the first sample if Peter chooses a number 0112, then a=1012,b=0112,c=0002, the sum of their values is 8. If he chooses the number 1002, then a=1012,b=0112,c=1112, the sum of their values is 15.
For the second test, the minimum and maximum sum of variables a, bb, cx, d and e is 2, and this sum doesn't depend on the number chosen by Peter, so the minimum Peter can choose is 0.

翻译
通用领域
医学
计算机
金融经济

Bob最近读到了计算机中使用的位运算:AND, OR和XOR。他研究了它们的性质，发明了一种新的游戏。

最初，Bob选择整数m，游戏的位深度，这意味着游戏中的所有数字将由m位组成。然后他让彼得选择一个m位数。之后，Bob计算n个变量的值。每个变量都被赋予一个固定的m位数或按位运算的结果。操作的操作数可以是之前定义的变量，也可以是Peter选择的数字。在此之后，Peter的分数等于所有变量值的和。

鲍勃想知道，彼得需要选择哪个数字才能得到可能的最低分数，他需要选择哪个数字才能得到可能的最高分数。在这两种情况下，如果有几种方法可以得到相同的分数，找出他可以选择的最小数量。

输入

第一行包含两个整数n和m，分别是变量数和位深(1≤n≤5000;1≤≤1000)。

下面n行包含变量的描述。每一行只描述一个变量。描述格式如下:新变量名，空格，符号":="，空格，后面跟着其中之一:

正好是m位的二进制数。

第一个操作数，空格，位操作("AND"， "OR"或"XOR")，空格，第二个操作数。每个操作数要么是前面定义的变量名，要么是符号'?，表示彼得选择的数字。

变量名是由小写拉丁字母组成的字符串，长度不超过10。所有变量名都是不同的。

输出

在第一行中输出Peter应该选择的最小值，使所有变量值的和尽可能小;在第二行中输出Peter应该选择的最小值，使所有变量值的和尽可能大。这两个数字都应该打印为m位二进制数。

例子

输入

输入样例 复制

输出样例 复制

分类标签