Codeforces Round 402 (Div. 1) |
---|
Закончено |
Вася недавно прочитал о битовых операциях, которые используются в компьютерах: AND, OR и XOR. Он неплохо изучил их свойства и придумал новую игру. Изначально Вася выбирает разрядность m для своей игры, это значит, что все числа в игре будут состоять из m битов. Потом он просит Петю выбрать некоторое одно m-битное число. После этого Вася вычисляет значения n переменных. Каждой из переменных присваивается либо константное m-битное число, либо результат выполнения битовой операции, операндами которой могут являться уже определенные переменные или выбранное Петей число. После этого сумма очков, которую получает Петя, равна сумме значений всех переменных.
Вася хочет узнать, какое число должен выбрать Петя, чтобы получить минимально возможное число очков, и какое число он должен выбрать, чтобы получить максимальное число очков. В обоих случаях, если у Пети есть несколько способов получить такую сумму, найдите минимальное число, которое он может выбрать.
В первой строке содержатся два целых числа n и m — количество переменных и разрядность, соответственно (1 ≤ n ≤ 5000; 1 ≤ m ≤ 1000).
В следующих n строках содержится описание переменных. В каждой строке описывается ровно одна переменная. Описание имеет следующий вид: имя новой переменной, пробел, знак «:=», снова пробел, далее два варианта:
Имена переменных — строки из строчных латинских букв длиной не более 10 символов. Все имена переменных различны.
В первой строке выведите минимальное число, которое должен выбрать Петя, чтобы сумма значений всех переменных была минимальна, во второй строке — минимальное число, которое должен выбрать Петя, чтобы сумма значений всех переменных была максимальна. Оба числа выведите в виде двоичного m-битного числа.
3 3
a := 101
b := 011
c := ? XOR b
011
100
5 1
a := 1
bb := 0
cx := ? OR a
d := ? XOR ?
e := d AND bb
0
0
В первом тесте если Петя выбирает число 0112, то a = 1012, b = 0112, c = 0002, сумма их значений равна 8. Если же он выберет число 1002, то a = 1012, b = 0112, c = 1112, сумма их значений равна 15.
Для второго теста минимальная и максимальная суммы переменных a, bb, cx, d и e равны 2 и не зависят от загаданного числа, поэтому минимальное число, которое может выбрать Петя — 0.
Название |
---|