TLE '17 Contest 5 P6 - Circuits

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
A generic circuit.

There is a circuit with input gates, and MOOSE gates.

A MOOSE gate computes the negation of the AND of the inputs. That is, it outputs if both inputs are , otherwise it outputs .

The gates are numbered starting with the input gates. Gate number is the output gate.

Each MOOSE gate's input is from two gates with smaller IDs.

At the moment all inputs have the same value , which is unknown, but can either have the value or .

You want to change as many of the inputs to fixed values ( or ) instead of as possible so that the output of the circuit (the value of gate ) is the same as the output before fixing any inputs. That is, if is produced when and is produced when , then the fixed circuit should still produce when and when . Output one such optimal choice of hard-wiring.

1 10
2 30

Input Specification

The first line of input will contain two space-separated integers, and .

The next line of input will contain space-separated integers. The and integers specify the inputs to gate . These integers are guaranteed to be positive and less than .

Output Specification

Output a single line with characters, denoting an optimal assignment. The character can either be 0 (set to false), 1 (set to true), or x (set to ). If there are multiple solutions, output any of them.

Sample Input 1

2 1
1 2

Sample Output 1

x1

Sample Input 2

3 6
1 3 1 2 4 5 4 5 7 6 8 8

Sample Output 2

10x

Sample Input 3

4 18
1 1 2 2 5 6 1 2 7 8 9 9 3 3 4 4 11 12 3 4 13 14 15 15 10 10 16 16 17 18 10 16 19 20 21 21

Sample Output 3

0000