Вітаю Вас, Гость

Задача А. VSD

Бали за задачу: 30
Обмеження часу: 1 с
Обмеження пам'яті: 64 M

   Одна із прадавніх легенд говорить: «У непрохідних джунглях недалеко від міста Ханоя є храм бога Брами. У ньому перебуває бронзова плита із трьома алмазними стрижнями. На один зі стрижнів бог при створенні світу нанизав 64 диски різних діаметрів із чистого золота. Найбільший диск лежить на бронзовій плиті, а інші утворюють піраміду, що звужується догори. Це вежа Брами. Працюючи день і ніч, жерці храму переносять диски з одного стрижня на інший, дотримуючись законів Брами:
   1) диски можна переміщати з одного стрижня на іншій тільки по одному;
   2) не можна класти більший диск на менший;
   3) не можна відкладати диски убік, при переносі дисків з одного стрижня на інший можна використовувати проміжний третій стрижень, на якому диски повинні перебувати теж тільки у вигляді піраміди, що звужується догори. Коли всі 64 диска будуть перенесені з одного стрижня на іншій, настане кінець світу».

   Ця прадавня легенда покладена в основу завдання про Ханойську вежу: перемістити n дисків зі стрижня 1 на стрижень 3, використовуючи проміжний стрижень 2 і дотримуючи законів Брами.

   Вхідні дані:
   Стандартний потік містить одне натуральне число N( N ≤ 1000) – кількість дисків, у грі «Ханойська вежа», яку грають оптимально.

   Вихідні дані:
   У стандартний потік записати оптимальну кількість ходів, щоб усі диски перенести із одного стрижня на інший.

   Приклади

Вхідні дані   Результат роботи
2 3

 

Задача B. VSD

Бали за задачу: 30
Обмеження часу: 1 с
Обмеження пам'яті: 64 M
Ім'я файлу, який містить вхідні дані: b.dat
Ім'я вихідного файлу: b.sol

   В початковий момент часу послідовність задана формулою: an=n2 mod 12345 + n3 mod 23456 Необхідно багато разів відповідати на запитання:
   • Знайти різницю між максимальним та мінімальним значеннями елементів: ai, ai+1,…,aj
   • Присвоїти елементу аі значення j.

   Вхідні дані:
   Перший рядок вхідного файлу b.dat містить натуральне число k – кількість запитів (k ≤ 100000). Наступні k рядків містять запити, по одному у рядку. Запит за номером i містить два числа xi,yi. Якщо xi > 0, то необхідно знайти різницю між максимальним та мінімальним елементами аxi …аyi. При цьому 1≤ xi ≤ yi ≤ 100000. Якщо xi<0, то необхідно присвоїти елементу a|xi| значення yi. При цьому -100000 ≤ xi ≤ -1 та |yi| ≤ 100000

   Вихідні дані:
   Для кожного запиту першого типу у вихідний файл b.sol необхідно вивести один рядок, який містить різницю між максимальним та мінімальним елементами послідовності на відповідному відрізку.

   Приклади

Вхідні дані   Результат роботи
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
34
68
250
234
1



 

 

Задача C. VSD

Бали за задачу: 30
Обмеження часу: 1 с
Обмеження пам'яті: 64 M

   Одна із прадавніх легенд говорить: «У непрохідних джунглях недалеко від міста Ханоя є храм бога Брами. У ньому перебуває бронзова плита із трьома алмазними стрижнями. На один зі стрижнів бог при створенні миру нанизав 64 диски різних діаметрів із чистого золота. Найбільший диск лежить на бронзовій плиті, а інші утворюють піраміду, що звужується догори. Це вежа Брами. Працюючи день і ніч, жерці храму переносять диски з одного стрижня на інший, дотримуючись законів Брами:

   1) диски можна переміщати з одного стрижня на іншій тільки по одному;
   2) не можна класти більший диск на менший;
   3) не можна відкладати диски убік, при переносі дисків з одного стрижня на інший можна використовувати проміжний третій стрижень, на якому диски повинні перебувати теж тільки у вигляді піраміди, що звужується догори. Коли всі 64 диска будуть перенесені з одного стрижня на іншій, настане кінець світу». Ця прадавня легенда покладена в основу завдання про Ханойську вежу: перемістити n дисків зі стрижня 1 на стрижень 3, використовуючи проміжний стрижень 2 і дотримуючи законів Брами. Якщо вежа складається з одного диска, то він переноситься за один хід: 1->3. Вежа із двох дисків переноситься за три ходи: 1->2, 1->3, 2->3. Для переносу вежі із трьох дисків буде потрібно вже сім ходів: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Зверніть увагу, за перші три ходи ми переносимо вежу із двох верхніх дисків на другий проміжний стрижень. Потім переносимо найбільший диск із першого стрижня на третій і ще раз проробляємо добре знайому нам операцію: переносимо вежу із двох дисків на третій диск. Пронумеруємо диски у порядку збільшення їх радіусів від 0 до 30. Нехай переміщення дисків проходить оптимально (зайвих переміщень ми не здійснюємо). Усі наші ходи пронумеровані від 1 до N-1 (N≤2∙109). Як по номеру ходу визначити який диск переміщуємо?

   Вхідні дані:
   Стандартний потік містить одне натуральне число N (N ≤ 2∙109) – номер ходу, у грі «Ханойська вежа», яку грають оптимально.

   Вихідні дані:
   У стандартний потік записати номер диску (число від 0 до 30)

   Приклади

Вхідні дані   Результат роботи
176 4

 

Задача D. VSD

Бали за задачу: 30
Обмеження часу: 1 с
Обмеження пам'яті: 64 M
Ім'я файлу, який містить вхідні дані: d.dat
Ім'я вихідного файлу: d.sol

   Бджілка Жу-Жу має у своєму розпорядженні медові соти, які містять n рядів та m стовпців правильних шестикутників. джілка Жу-Жу вирішила з’єднати сусідні чарунки каналом, для передачі меду. Так, як отримання меду досить трудомістка операція, то перед бджілкою постала непроста задача: з’єднати чарунки таким чином, щоб по побудованій системі каналів можна було передати мед у будь-яку чарунку, і при цьому щоб витрати меду були найменшими. Кількість меду, необхідного для заповнення каналу між двома сусідніми чарунками, обчислюється за формулою: (x1x2 + p1y1y2) mod p2, де x1, y1, x2, y2 – координати початкової та кінцевої чарунок, р1, р2 – прості числа. Перша координата – це номер ряду, у якому знаходиться чарунка, а друга координата – це номер чарунки у цьому ряді. Ряди нумеруються зверху вниз, а чарунки у цих рядах – зліва направо. На малюку зображена карта поля розміром n=3, m=3:

   Вхідні дані:
   Вхідний файл d.dat містить містить чотири натуральних числа n, m, p1, p2 (1 ≤ n, m, p1, p2 ≤ 1000). За умовою р1 та р2 – прості числа.

   Вихідні дані:
   У єдиний рядок вихідного файлу d.sol записати відповідь на задачу.

   Приклади

Вхідні дані   Результат роботи
3 3 11 23 28

 

Задача E. VSD

Бали за задачу: 30
Обмеження часу: 3 с
Обмеження пам'яті: 64 M
Ім'я файлу, який містить вхідні дані: e.dat
Ім'я вихідного файлу: e.sol

   Діма з Льошиком полюбляють грати у таку гру: Ігрове поле являє собою прямокутник, який розбитий на клітинки. Деякі клітинки зафарбовані у чорний колір, а решту клітинок – у білий. Діма з Льошиком по черзі задають координати випадкової клітинки, якщо вона білого кольору, то її перефарбовують у чорний, а якщо вона чорного кольору, то залишають без змін. Гра зупиняється у момент, коли ігрове поле розпадається на дві частини по границі чорних клітинок (одна із частин може бути порожньою). Границя має проходити зверху вниз по сусідніх клітинках чорного кольору, тобто має починатися на першому рядку і закінчуватися на останньому. Сусідніми клітинками будемо вважати ті, які мають спільну сторону. Право першого ходу має Діма. Оскільки гравці не повинні бачити ігрове поле, то ваша задача написати програму, яка визначає переможця і виводить координати останньої клітинки, на якій зупиняється гра.

   Вхідні дані:
   Перший рядок вхідного файлу містить два натуральних числа n, m (3 ≤ n,m ≤ 2000) – розмір ігрового поля. У наступних n рядках через пропуск записані m символів 0 або 1. Нуль відповідає чорній клітинці, а 1 – білій клітинці. Наступний рядок містить натуральне число k (k ≤ 100000) – кількість ходів гравців. Наступні k рядків містять два натуральних числа i,j (i ≤ n, j ≤ m)- координати випадкових клітинок, які задають гравці. Гарантується, що дана кількість ходів однозначно визначає переможця.

   Вихідні дані:
   У єдиний рядок вхідного файлу записати символ D – якщо переміг Діма або символ L – якщо перемогу отримав Льоша, а далі через пропуск записати координати клітинки, яка визначає переможця.

   Приклади

Вхідні дані   Результат роботи
5 4
1 1 1 1
1 1 0 0
1 0 1 1
1 1 1 0
0 0 0 0
8
1 1
2 4
1 3
1 2
2 4
1 1
3 4
5 1
D 3 4













 
4 4
0 1 1 1
1 0 1 1
1 1 1 1
0 1 1 1
7
1 2
2 2
3 3
3 2
1 1
4 3
2 1
L 4 3