|
2 тур - з 19.11 по 26.11.2018
точка входу для відправлення розв'язків
http://134.249.159.199//cgi-bin/new-client?contest_id=63
(скачати)
Задача А. (100 балів)
Обмеження по пам'яті: 64Мб
Обмеження по часу: 1с
Ми попали в Майнкрафтію, в якій все складається з блоків розміром 1*1*1.
Вся країна поділена на однакові чанки, по одному чанку для кожного жителя. Чанк представляє собою паралелепіпед розміром n*m*k блоків. Автор задачі живе в одному з таких чанків. Деякі блоки цього чанку пусті і через них можна пройти, а деякі заставлені каменем, тобто є непрохідними. Автор зараз знаходиться в блоці з координатами (1;1;1) і йому потрібно потрапити в блок з координатами (n;m;k). Відповідно, ці два блоки завжди пусті. Автор може переходити в сусідній блок, якщо він пустий. Сусіднім вважається блок, який має спільну грань з даним, тобто знаходиться в одному з шести напрямків: знизу, зверху, зліва, справа, ззаду, спереду. Виходити за межі чанка заборонено законами Майнкрафтії.
Визначте, за яку найменшу кількість переходів автор може потрапити з блока з координатами (1;1;1) в блок з координатами (n;m;k).
Вхідні дані:
Перший рядок містить 3 числа n, m, k(1≤n,m,k≤60) – розміри чанка.
В наступному рядку знаходиться n*m*k чисел, які описують чанк. Якщо певне число рівне одиниці, то відповідний блок пустий, інакше блок є непрохідним.
Номери блоків ідуть в наступному порядку:
(1;1;1),(2;1;1),(3;1;1)...(n;1;1), (1;2;1), (2;2;1)...(n;m;1), (1;1;2), (2;1;2)... (n-1;m;k), (n;m;k).
Вихідні дані:
Виведіть найменшу кількість переходів, необхідну для того, щоб потрапити з блока з координатами (1;1;1) в блок з координатами (n;m;k).
Гарантується, що завжди можна дістатися з початкового в кінцевий блок.
Приклади:
|
2 3 2
0 1 1 1 0 1 0 0 1 0 1 0
|
4
|
|
3 3 3
0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0
|
6
|
В першому прикладі автор може рухатися наступним маршрутом:
(1;1;1), (1;1;2), (2;1;2), (2;2;2), (2;3;2)
Задача В. ( 100 балів)
Обмеження по пам'яті: 64Мб
Обмеження по часу: 2с
Майнкрафтія відома не тільки своєю кубічністю. В цій країні діє неймовірна редстоун механіка, на основі якої можна будувати різні механізми. Зокрема, дана механіка дозволяє створювати логічні оператори, які представляють собою побітові операції. Логічні операції бувають чотирьох видів: AND(і, 2 вхідних сигнали), OR(або, 2 вхідних сигнали), XOR(додавання за модулем два, 2 вхідних сигнали), NOT(не, 1 вхідний сигнал).
Автор задачі побудував механізм на основі побітових операції, який представляє собою неорієнтоване дерево, в коренем в вершині 1. Всі листки дерева, крім кореня, є початковими сигналами і можуть повертати 0 або 1. Всі інші елементи є одними з побітових операцій. Такі елементи приймають сигнали від дітей і повертають значення результату функції, яку вони виконують. Результатом такого механізму буде значення, яке поверне корінь.
Вам стало цікаво, який буде результат механізму, якщо змінити сигнал, який повертає саме даний вхід, на протилежний.
Вхідні дані:
Перший рядок містить одне ціле число n (1≤n≤3*103) – кількість вершин в дереві (входів+бітових операторів).
Наступні n рядків містять опис кожної з вершин, починаючи нумерацію з 1. Спочатку іде тип вершини: "AND", "OR", "XOR", "NOT" або "IN". Якщо ця вершина типу "IN" – це вхідний сигнал, тобто далі іде одне число, яке позначає тип сигналу(0 або 1). Якщо ця вершина якогось з інших типів, то далі іде одне або два числа, які позначають дітей, від яких бере сигнал дана вершина.
Для кращого розуміння, дивіться вхідні дані.
Вихідні дані:
Виведіть рядок з символів "0" або "1" – відповідь на задачу для кожного входу, в порядку їх сортування в вхідних даних.
Приклади:
|
3
OR 2 3
IN 0
IN 1
|
10
|
|
20
OR 17 10
IN 0
IN 0
NOT 6
OR 18 14
IN 1
OR 16 3
XOR 5 4
IN 0
XOR 11 9
NOT 15
AND 20 19
IN 0
IN 1
IN 1
NOT 8
NOT 12
IN 1
AND 13 7
NOT 2
|
11111111
|
Зображення до першого прикладу (жовтий – 0, зелений – 1): початковий стан, змінений сигнал другого елемента, змінений сигнал третього елемента
|
