LOGIC - Logic

no tags 

Consider a 10x10 grid. Cells in this grid can contain one of five logic operations (AND, OR, NOT, Input, Output). These can be joined together to form a logic circuit. Given a description of a circuit and a set of boolean values, build the logic circuit and execute the input stream against it.

Input

The first line of the input contains a single integer n, which specifies the number of circuits to be processed. There will then be n groups of circuit descriptions and test values.

A circuit is made up of a number of operations. Each line describing an operation begins with three characters: the co-ordinates for a cell, 0-9 on the X-axis then 0-9 on the Y-axis, followed by a single character to represent the operation of that cell (`&' for AND, `|' for OR, `!' for NOT, `i' for Input and `o' for Output). Optionally following each triple is a set of co-ordinate pairs which represent the x and y co-ordinates of cells that take the output of this cells operation as an input for theirs. This (possibly empty) output list is terminated by `..'. The list of operations is terminated by a line containing the word `end'.

Next, for each circuit, comes the set of test values. The first line contains an integer t which gives the number of test cases your program must run. Next, there are t lines, each line containing a sequence of `0' and `1' characters symbolising the input values for one test case. The number of inputs will always correspond to the number of inputs defined by the circuit description. The input values are to be applied to the inputs in the order in which the input operations were defined in the circuit description.

The next circuit description, if any, will then follow.

Output

For each circuit, your program should output one line for each test case given in the input. The line should contain one `0' or `1' character for each output defined by the circuit description in the order in which the outputs were defined.

Your program should output a blank line after each set of test cases.

Example

Input:

1
00i 11 13 ..
02i 11 13 ..
11& 21 ..
21o ..
13| 23 ..
23o ..
end
4
00
01
10
11

Output:

00
01
01
11

Notes:

  • i, o and ! operations will always have exactly one input.
  • & and | operations will always have exactly two inputs.
  • Even if an operation can feed others, it does not have to.
  • No recursive circuits.
  • o can also be an input for another gate

Hint: Sample input specifies a circuit consiting of an `AND' and an `OR' operation in parallel both fed from the same two inputs:

               +---------\
3              |          |OR #----------OUT(2)
               |     +---/
               |     |
2     IN(2)----+     |
               |     |
               +---------\
1                    |    |AND#----------OUT(1)
                     +---/
                     |
0      IN(1)---------+

         0                 1              2

In grid terms this is two inputs at 0,0 and 1,0. The first input feeds the AND operation at 1,1 and the OR operation at 1,3. The second input operation feeds the second input for the same AND and OR operations. The AND operation then feeds an output operation at 2,1. The OR operation also feeds an output operation, this one at 2,3.


hide comments
Ahmad: 2015-01-01 13:09:32

Any hints to look for in this problem ? .. I am getting TLE!

Adrian Kuegel: 2010-04-26 10:07:39

Ok, it seems when I wrote that comment I forgot about that one test case. What I can confirm is: there is at least one defined input gate.

:D: 2010-04-22 20:16:41

I assumed this was still valid: http://www.spoj.pl/forum/viewtopic.php?f=3&t=3250&p=3841 (last post)

Last edit: 2010-04-22 20:18:33
Adrian Kuegel: 2010-04-16 08:52:38

You made the assumption that there must always be a defined output gate. This is not specified in the problem.

:D: 2010-04-10 12:04:45

OK! I'm almost certain (95%) that there are some trash characters in the test data. My almost 40 submission test would suggest that You must ignore characters after ".." and "end" tokens until the end of line. After them there probably is some bogus data that results in WA rather that program crash. If I'm mistaken than sorry, but I literary spent hours checking this.

Adrian Kuegel: 2010-02-24 14:53:15

I think the mistake in your code was that your strings had length 100, but they need length 101 to store the terminating 0 byte.

Last edit: 2010-02-24 14:58:26
[Rampage] Blue.Mary: 2010-01-07 04:56:29

I can't understand what's wrong with "scanf("%s")"... I MUST use scanf("%c") (i.e. getchar()) in order to get Accepted...


Added by:Adrian Kuegel
Date:2005-07-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:ACM Northwestern European Regional Contest 1993