eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

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

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

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

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

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

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

Giriş verilənləri

Состоит из двух блоков. Первый блок содержит несколько строк. Если первый символ строки диез (#), то строка содержит комментарий. Игнорируйте ее. Также игнорируйте пустые строки. Строка описывающая входные сигналы выглядит как 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 строк. Для более подробной информации смотрите примеры.

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
00
11
10
Giriş verilənləri #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
Çıxış verilənləri #2
1
0
0
0
1
1
Mənbə 2007 Петрозаводск, Saratov for Karelia with love, Январь 28, Задача E