Bit Combinations

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type

Let X represent a non-negative integer strictly less than 2^{60}.

You are given a list of N constraints on X.

Each constraint is a bitwise operator followed by two numbers: the second input and the output of the bitwise operation.

Any of the following bitwise operators may appear in a given constraint: AND, OR, NAND, NOR.

For example, a constraint could be AND 7 3, meaning that X \land 7 = 3.

How many solutions for X satisfy all N constraints?

Input Specification

The first line contains an integer N (1 \le N \le 100).

The next N lines each contain the name of the bitwise operator followed by two integers Y and Z (0 \le Y, Z < 2^{60}).

Output Specification

Output the number of solutions for X that satisfy all N constraints.

Sample Input 1

AND 0 1

Sample Output 1


Sample Input 2

AND 1 1
OR 12287 16383
NAND 6 1152921504606846975
NOR 1152921504606844927 0

Sample Output 2



There are no comments at the moment.