Задачі фінального туру NetOI-2024
15 лютого 2025 р.
Задача Trip2025. В одній мальовничій країні з N міст є рівно N-1 двонаправлена дорога, при чому з будь-якого міста можна потрапити до будь-якого іншого міста цими дорогами. Міста при цьому пронумеровані від 1 до N, і чим більший номер числа, тим воно цікавіше. Перша в країні туристична агенція вирішила запустити індивідуальні тури, при чому кожному клієнту обіцяють незабутні і унікальні враження за доступною ціною.
При цьому:
- Доступність ціни планують забезпечити тим, що екскурсії в рамках туру будуть відбуватися виключно в трьох містах (маршрут може пролягати через інші міста, просто без зупинки), при цьому одна з екскурсій обовʼязково буде у місті-початку маршруту, а друга у кінцевому місті;
- Незабутність буде забезпечуватися тим, що кожна наступна екскурсія буде відбуватися у місті, яке цікавіше за попереднє місто, а подорож клієнта ніколи не проходитиме через одну й ту саму дорогу двічі;
- Нарешті, унікальність забезпечується тим, що усі клієнти матимуть свій унікальний маршрут.
Тепер туристична агенція хоче зрозуміти, яку максимальну кількість клієнтів вона може обслужити - іншими словами, скільки існує різних маршрутів з трьома екскурсіями таких, що екскурсії щоразу проходять у цікавішому місті, і маршрут не пролягає через ту саму дорогу двічі. Два маршрути вважаються різними, якщо міста для екскурсій у цих маршрутах відрізняються.
Технічні умови. Програма Trip2025 читає зі стандартного пристрою введення (клавіатури) у першому рядку єдине ціле число N (1 ≤ N ≤ 100000) - кількість міст у країні. Наступні N - 1 рядків містять по два натуральних числа - номери міст, які зʼєднані дорогою. Програма виводить єдине ціле число - відповідь на задачу.
Приклад
|
Введення |
Виведення |
Коментар |
|
6 1 3 2 3 4 3 4 5 4 6 |
12 |
Нижче наведено ілюстрацію до мапи міста. Маршрути, які задовольняють умову задачі: 1 – 3 – 4 1 – 3 – 5 1 – 3 – 6 2 – 3 – 4 2 – 3 – 5 2 – 3 – 6 3 – 4 – 5 3 – 4 – 6 1 – 4 – 5 1 – 4 – 6 2 – 4 – 5 2 – 4 – 6 |
Задача line2025. Петрик захопився аналітичною геометрією, тому хоче трохи з нею погратися.У Петрика є пряма y = A•x + B, з цілими коефіцієнтами A та B. Крім того, Петрик має N точок (xі, yi). Петрик вважає, що точкам буде комфортно, якщо для кожної з його точок виконуватиметься A•xi + B ≥ yi. Для того, щоб забезпечити комфорт його точкам, Петрик може збільшувати щоразу або A, або B рівно на 1. Петрику цікаво, яку ж мінімальну кількість операцій йому потрібно зробити, щоб усім його точкам стало комфортно.
Технічні умови. Програма line2025 зчитує з пристрою стандартного введення (клавіатури) три цілих числа - N (1 ≤ N ≤ 105), A та B (-109 ≤ A, B ≤ 109).
У наступних N рядках програма читає по два числа Xi, Yi (-109 ≤ Xi, Yi ≤ 109), що задають координати точок. Програма виводить єдине число - відповідь на задачу.
Приклади
|
Введення |
Виведення |
Коментар |
|
3 1 1 0 0 0 1 1 1 |
0 |
Умова вже справджується. Дійсно: 1•1 + 0 ≥ 1 |
|
1 2 3 2 8 |
1 |
Спершу умова не справджується. Дійсно, 2•2 + 4 = 8 ≥ 8 |
Задача Game2025big. Двоє грають у гру. Спочатку є N (1⩽N⩽1018) паличок. На кожному ході кожен гравець може забирати або одну, або дві, або три палички, але не більше, чим їх є всього (тобто, якщо лишається тільки 1 паличка, то забрати можна лише одну, а якщо 2, то або одну, або дві). Описані досі ходи будемо називати традиційними. Крім них, існують спеціальні ходи: задається кілька пар цілих чисел (a1, b1), (a2, b2), …, (at, bt), де 0⩽t⩽123 та 0⩽bi<ai⩽1018. Спеціальні ходи працюють так: якщо кількість паличок дорівнює якомусь із ai, то гравець може замінити ai паличок на bi; це можна також назвати «забрати (ai–bi) паличок». Якщо гравець може зробити спеціальний хід, він сам вирішує, чи робити його, чи якийсь із традиційних, але зробити якийсь один хід треба. Ситуація, коли відразу кілька пар мають однакове значення ai, можлива; в такій ситуації гравець теж сам вирішує, яким із доступних ходів (спеціальних чи традиційних) скористатися. В будь-якому разі, після кожного ходу черга ходити переходить до іншого гравця, пропускати хід не можна. Закінчується гра тоді, коли лишається 0 паличок (це може статися хоч після традиційного ходу, хоч, якщо існує пара, де bi=0, після спеціального), і той, хто походив у цю позицію, виграв, а той, кому така позиція дісталася, програв. Напишіть програму, яка визначатиме, хто виграє при ідеальній грі обох гравців. Щоб відповідь не так легко було вгадати, задачу слід розв'язати, при одній і тій самій сукупності пар (a1, b1), (a2, b2), …, (at, bt), для різних початкових кількостей паличок.
Технічні умови. Програма Game2025big читає з пристрою стандартного введення в першому рядку два цілі числа k та t, де k (3⩽k⩽12345) задає кількість різних початкових кількостей паличок, а t задає кількість пар, що утворюють спеціальні ходи. Потім вона читає у другому рядку самі спеціальні ходи, як 2t цілих чисел a1 b1 a2 b2…at bt , для яких виконуються всі вищезгадані обмеження. Потім вона читає у третьому рядку k натуральних чисел N1, N2,…, Nk (1⩽Ni⩽1018) – різні початкові кількості паличок, для яких слід розв'язати задачу.
Програма виводить в один рядок без пропусків рівно k великих латинських літер W та/або L, де W позначає, що при відповідній початковій кількості паличок виграє перший гравець, а L – що другий
Приклади
Введення
6 2
12 4 9 3
3 5 4 17 15 16
Виведення
WWLLWW
Задача Game2025looped Двоє грають у таку гру. Спочатку є N (1⩽N⩽105) паличок. На кожному ході кожен гравець може забирати або одну, або дві, або три палички, але не більше, чим їх є всього (тобто, якщо лишається тільки 1 паличка, то забрати можна лише одну, а якщо 2, то або одну, або дві). Описані досі ходи будемо називати традиційними. Крім них, існують спеціальні ходи: задається кілька пар цілих чисел (a1, b1), (a2, b2), …, (at, bt), де 0⩽t⩽12345, 1⩽ai⩽105 та 0⩽bi⩽105. Спеціальні ходи працюють так: якщо кількість паличок дорівнює якомусь із ai, то гравець може замінити ai паличок на bi. Якщо гравець може зробити спеціальний хід, він сам вирішує, чи робити його, чи якийсь із традиційних, але зробити якийсь один хід треба. Ситуація, коли відразу кілька пар мають однакове значення ai, можлива; в такій ситуації гравець теж сам вирішує, яким із доступних ходів (спеціальних чи традиційних) скористатися. В будь-якому разі, після кожного ходу черга ходити переходить до іншого гравця, пропускати хід не можна. (Щоправда, користуватися ходом, де bi=ai, можна, і це в деякому смислі відповідає пропуску ходу; але ж це можливо, лише якщо поточна кількість паличок якраз рівна таким bi та ai, для яких існує такий спеціальний хід.) Закінчується гра тоді, коли лишається 0 паличок (це може статися хоч після традиційного ходу, хоч, якщо існує пара, де bi=0, після спеціального), і той, хто походив у цю позицію, виграв, а той, кому така позиція дісталася, програв. Однак, ця гра може й не завершуватися, бо завдяки спеціальним ходам з чи bi>ai чи кількість паличок може так ніколи й не стати 0. Такий результат кожен з гравців розцінює як гірший, чим виграш, але кращий, чим програш. Напишіть програму, яка визначатиме, хто виграє при ідеальній грі обох гравців. Щоб відповідь не так легко було вгадати, задачу слід розв'язати, при одній і тій самій сукупності пар (a1, b1), (a2, b2), …, (at, bt), для різних початкових кількостей паличок.
Технічні умови. Програма Game2025looped спочатку читає в першому рядку два цілі числа k та t, де k (3⩽k⩽12345) задає кількість різних початкових кількостей паличок, а t задає кількість пар, що утворюють спеціальні ходи. Потім вона читає у другому рядку самі спеціальні ходи, як 2t цілих чисел a1 b1 a2 b2…at bt , для яких виконуються всі вищезгадані обмеження. Потім вона читає у третьому рядку k натуральних чисел N1, N2,…, Nk (1⩽Ni⩽105) – різні початкові кількості паличок, для яких слід розв'язати задачу. Програма виводить в один рядок без пропусків рівно k великих латинських букв W та/або L та/або D, де W позначає, що при відповідній початковій кількості паличок перший гравець може гарантувати собі виграш, L – що другий, а D – що жоден з гравців не може гарантувати собі виграшу, але перший гравець може гарантувати, що гра триватиме нескінченно довго.
Приклади
Введення
17 3
7 17 8 4 13 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Виведення
WWWLWWWWLWWWDDDDD
Задача Platforms2025. У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь персонаж стрибає по платформах (або острівцям), які висять у повітрі. Він повинен перебратися від одного краю екрану до іншого. При цьому при стрибку з платформи на сусідню, герой витрачає ∣y2−y1∣ одиниць енергії, де y1 і y2 — висоти, на яких розташовані ці платформи. Крім того, у героя є суперприйом, який дозволяє перескочити через платформу, але на це витрачається 3⋅∣y3 −y1∣ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від kmin до kmax разів (обидві межі включно). Звісно, енергію слід витрачати максимально економно.
Технічні умови. Програма Platforms2025 читає в першому рядку кількість платформ n (1⩽n⩽10000), потім у другому рядку n цілих чисел, модулі яких не перевищують 30000 — висоти, на яких розташовані платформи, потім у третьому рядку два цілі невід'ємні числа kmin та kmax (0⩽kmin⩽kmax ⩽(n−1)/2). Ваша програма виводить єдине число — мінімальну кількість енергії, яку має витратити гравець.
Приклади
|
Введення |
Виведення |
Коментар |
|
3 1 5 10 0 1 |
9
|
У першому прикладі, вигідно стрибати, не користуючись суперприйомом (використавши його 0 разів). |
|
3 1 5 10 1 1
|
27
|
У другому прикладі персонаж мусить використати суперприйом рівно один раз, і не має іншого вибору, крім як стрибнути з першої платформи на останню |
Завдання підготувли К.Денисов, Г.Непомнящий, Ю.Пасіхов, І.Порубльов, М.Стречень