eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Электрические схемы

Электрические схемы

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Рассмотрим цифровую электрическую схему, работающую с двоичными сигналами в дискретном времени. Она содержит входные сигналы, провода, соединения и логические элементы. Мы будем использовать шесть видов логических элементов: NOT, AND, NAND, OR, NOR, DFF. Каждый из них возвращает один выходной сигнал. Количество входных сигналов и информация о возвращаемом значении приведены в следующей таблице.

  • NOT, 1 вход. Противоположное значение входного сигнала;

  • AND, 1 или более вход. Конъюнкция значений входных сигналов;

  • NAND, 1 или более вход. Отрицание конъюнкции значений входных сигналов;

  • OR, 1 или более вход. Дизъюнкция значений входных сигналов;

  • NOR, 1 или более вход. Отрицание дизъюнкции значений входных сигналов;

  • DFF, 1 вход. Такое же значение как и входной сигнал. Возвращается с задержкой одного тика дискретного времени;

Схема работает следующим образом. Перед первым тиком дискретного времени каждый элемент DFF инициализируется нулевым значением. Затем в течении нескольких тиков на некоторые соединения (входные контакты) будут поданы входные значения. Вы должны написать программу, которая будет вычислять двоичные значения на определенном наборе узлов (выходных соединений).

Программе будет дано описание логической схемы, набор переходов, в которых мы заинтересованы, и входные значения для каждого последовательного тика дискретного времени.

Вхідні дані

Состоит из двух блоков. Первый блок содержит несколько строк. Если первый символ строки диез (#), то строка содержит комментарий. Игнорируйте ее. Также игнорируйте пустые строки. Строка описывающая входные сигналы выглядит как INPUT(junction), где junction - имя соединения. Строка описывающая интересующие нас соединения, выглядит как OUTPUT(junction), где junction - имя соединения. Имя соединения состоит из прописных и заглавных латинских букв, цифр и символа подчеркивания ( _ ). Длина имени менее 64 символов.

Все остальные строки первого блока содержат описание новых соединений. Такая строка выглядит как j1 = op(j2), где j1 и j2 - имена соединений, а op либо NOT либо DFF. Она также может выглядеть как j1 = op(j2[, j3...]), где j-ки - имена соединений, а op равно AND, NAND, OR или NOR. Существует не более 5000 соединений.

Второй входной блок начинается со строки INPUT VALUES. Каждая из следующих строк содержит последовательность нулей и единиц. Количество цифр равно количеству входных сигналов. Вы должны сопоставлять эти двоичные значения со значениями входных сигналов в порядке их следования на входе. Блок содержит не более 500 строк. Для более подробной информации смотрите примеры.

Считайте, что входные данные корректны. Считайте, что данная схема будет работает правильно.

Вихідні дані

Для каждой строки значений входных сигналов выведите одну строку, содержащую нули и единицы. Цифры должны соответствовать значениям выходных сигналов, сохраняя их входной порядок.

Приклад

Вхідні дані #1
INPUT(a)
INPUT(b)
x = DFF(a)
t = OR(a, b)
y = AND(x, t)
OUTPUT(x)
OUTPUT(y)
INPUT VALUES
10
11
00
Вихідні дані #1
00
11
10
Вхідні дані #2
# 4 inputs
# 1 output
# 3 D-type flipflops
# 2 inverters
# 8 gates (1 AND+1 NAND+2 ORs+4 NORs)


INPUT(G0)
INPUT(G1)
INPUT(G2)
INPUT(G3)

OUTPUT(G17)

G5 = DFF(G10)
G6 = DFF(G11)
G7 = DFF(G13)

G14 = NOT(G0)
G17 = NOT(G11)

G8 = AND(G14, G6)

G15 = OR(G12, G8)
G16 = OR(G3, G8)

G9 = NAND(G16, G15)

G10 = NOR(G14, G11)
G11 = NOR(G5, G9)
G12 = NOR(G1, G7)
G13 = NOR(G2, G12)

INPUT VALUES
0000
0001
0010
0100
1000
1010
Вихідні дані #2
1
0
0
0
1
1
Джерело 2007 Петрозаводск, Saratov for Karelia with love, Январь 28, Задача E