e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Məsələlər

Логическое дерево

Логическое дерево

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

Каждая вершина дерева имеет связанное с ней логическое значение (1 или 0). Кроме этого, каждая внутренняя вершина имеет связанную с ней логическую операцию ("И" или "ИЛИ"). Значение вершины с операцией "И" - это логическое "И" значений ее детей. Аналогично, значение вершины с операцией "ИЛИ" - это логическое "ИЛИ" значений ее детей. Значения всех листьев задаются во входном файле, поэтому значения всех вершин дерева могут быть найдены.

Наибольший интерес для нас представляет корень дерева. Мы хотим, чтобы он имел заданное логическое значение v, которое может отличаться от текущего. К счастью, мы можем изменять логические операции некоторых внутренних вершин (заменить "И" на "ИЛИ" и наоборот).

Дано описание логического дерева и набор вершин, операции в которых могут быть изменены. Найдите наименьшее количество вершин, которые следует изменить, чтобы корень дерева принял заданное значение v. Если это невозможно, то выведите строку "IMPOSSIBLE" (без кавычек).

Входные данные

В первой строке входного файла находятся два числа n и v (1n10000, 0v1) - количество вершин в дереве и требуемое значение в корне соответственно. Поскольку все вершины имеют ноль или двоих детей, то n - нечетное. Следующие n строк описывают вершины дерева. Вершины нумеруются с 1 до n. Первые (n-1)/2 строк описывают внутренние вершины. Каждая из них содержит два числа - g и c, которые принимают значение либо 0, либо 1. Если g=1, то вершина представляет логическую операцию "И", иначе она представляет логическую операцию "ИЛИ". Если c=1, то операция в вершине может быть изменена, иначе нет. Внутренняя вершина с номером i имеет детей 2i и 2i+1. Следующие (n+1)/2 строк описывают листья. Каждая строка содержит одно число 0 или 1 - значение листа.

Выходные данные

В выходной файл выведите ответ на задачу.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
17 1
0 1
1 0
1 0
1 1
0 1
1 1
1 1
1 1
0
1
0
1
0
0
1
0
1
Çıxış verilənləri #1
2