Завдання 3-го туру
4
Розв'язки надіслати до 0 годин 2.02.25 р.
Термін прийняття розв'язків продовжено
Задача Travel2025. Є N аеропортів, між якими призначено авіарейси. Кожний авіарейс триває на менше однієї хвилини та не більше доби. Всі рейси щоденні. Ви знаходитесь в аеропорту 1, годинник показує 0 годин 0 хвилин. Скільки часу вам знадобиться, щоб дістатися в аеропорт N?
Технічні умови. Програма Travel2025 читає з пристрою стандартного введення натуральні числа N (1≤N≤500)- кількість аеропортів і K – кількість рейсів (1≤K≤5000), далі з K рядків розклад у форматі I J H1 M1 H2 M2, де I – аеропорт вильоту, J – аеропорт прильоту, H1, M1 – час вильоту, H2, M2 – час прильоту (1≤I,J≤N, 0≤H1,H2≤23, 0≤M1,M2≤59). Програма виводить на пристрій стандартного одне число – шукану мінімальну кількість хвилин. Якщо потрапити в аеропорт неможливо, програма має вивести -1
Приклади
Введення
5 4
1 3 12 10 16 20
1 5 2 25 1 0
1 3 2 15 5 0
3 5 5 0 9 0
Виведення
540
Введення
5 4
1 3 12 10 16 20
1 4 2 25 1 0
1 3 2 15 5 0
5 3 5 0 9 0
Виведення
-1
Задача Mean2024. Середнім арифметичним двох рядків назвемо половину конкатенації двох рядків. Наприклад, середнє арифметичне рядків “b” та “aaaaa” є половина рядка baaaaa, тобто рядок “baa”, для рядків “b” та “c” це рядок “b”, а для рядків “cd” та “e” середнім арифметичним буде рядок “c” (для непарних довжин “половина” округлюється до меншого числа). Аналогічно, для рядка “” (порожній рядок) та “bb” середнім арифметичним буде “b”. Позначатимемо середнє арифметичне двох рядків S та T як mean(S, T).
Процес усереднення для двох рядків S та T наступний. Спершу у R (результат) записуємо порожній рядок. Далі виконуємо рівно N кроків. Якщо крок непарний - у R записуємо середнє арифметичне mean(R, S), якщо ж парний - mean(R, T). Псевдокодом цей процес можна описати наступним чином:
S, T: рядки
N: натуральне число
R = “”
для i від 1 до N:
якщо i непарне:
R = mean(R, S)
інакше
R = mean(R, T)
повернути R
Для заданих рядків S, T та кількості кроків N потрібно знайти результат процесу усереднення.
Технічні умови. Програма Mean2024 читає з пристрою стандартного введення у першому рядку число N (1 ≤ N ≤ 109); у другому - рядок S довжиною не більше 100000 символів, який складається виключно з малих літер латинської абетки; у третьому - рядок T довжиною не більше 100000 символів, який складається виключно з малих літер латинської абетки. Програма виводить на пристрій стандартного виведення шукану величину - результат усереденення рядків S та T після N кроків.
Приклади
|
Введення |
Виведення |
|
|
2 aaa bbb |
ab |
Після першого кроку R = ‘a’ Після другого кроку R = “ab” |
|
3 a aaaaaaaa |
aa |
Після першого кроку R = “” Після другого кроку R = “aaaa” Після третього кроку R = “aa” |
Задача Robot2025. Мапа лабіринту представляє з себе таблицю NxM, де кожна клітинка або прохідна, або заблокована. Сам лабіринт оточений непрохідними клітинками, не показаними на плані.
Робот рухається у лабіринті по клітинках за наступним алгоритмом.
Алгоритм:
- Якщо прямо у напрямку руху вільна клітинка, робот поїде прямо (переміститься на 1 клітинку у напрямку руху) і почне виконувати алгоритм наново.
- Якщо прямо їхати не можна, а ліворуч від напрямку руху вільна клітинка, то робот повернеться на 90° ліворуч і почне виконувати алгоритм наново.
- Якщо прямо їхати не можна, ліворуч від напрямку руху клітинка заблокована, а праворуч вільна, робот повернеться на 90° праворуч і почне виконувати алгоритм наново.
- Якщо прямо їхати не можна, а ліворуч і праворуч від напрямку руху клітинки заблоковані, то робот зупинить виконання алгоритму
Потрібно заблокувати деяку кількість клітинок таким чином, щоб в якийсь момент робот зупинив виконання алгоритму (а не кружляв вічно), при цьому зробити якнайменше змін.
Технічні умови. Програма Robot2025 читає з пристрою введення два натуральних числа N та M (1 ≤ N, M ≤ 1000) - розміри мапи. Верхня ліва клітинка має координати (1, 1). У наступних N рядках програма зчитує по M символів, які задають мапу. Символ “.” означає прохідне поле, символ “X” - заблоковану клітинку, а символ “R” - початкову позицію робота.
Гарантується, що на мапі присутній робот. З самого початку робот направлений на північ (“вгору”).
Програма виводить спершу L - кількість змін. У наступних L рядках програма виводить по 2 цілих числа - координати, що задають рядок та стовпчик, де потрібно поставити блок (поміняти на мапі “X” на “.”). Забороняється блокувати клітинку, на якій робот розміщенний з самого початку.
|
Введення |
Виведення |
Коментар |
|
1 3 .RX |
0 |
Робот поверне, пройде одну клітинку і зупиниться, тож ніяких змін робити не потрібно |
|
2 2 .. .R |
1 1 1 |
Після зміни мапа виглядатиме наступним чином: 2 2 X. .R Таким чином, робот пройде одну клітинку і зупиниться. При цьому, якщо залишити мапу без змін, робот нескінченно кружлятиме по мапі. |
Задача Stairs2025. На складі одного поштового оператора є всього одна лампочка, і зараз вона перегоріла. Щоб замінити лампочку і продовжити обслуговування клієнтів, було вирішено побудувати сходинки з підручних матеріалів - прямокутних ящиків певного розміру. Кожна наступна сходинка має бути на один метр вище за попередню (зокрема, перша сходинка має мати висоту 1), при цьому ящики можна перевертати як завгодно, але не можна ставити один ящик на інший чи деформувати самі ящики. Кожен ящик можна використати лише один раз.
Потрібно знайти максимальну висоту сходинок, що можна побудувати у такий спосіб
Технічні умови. Програма Stairs2025 читає з пристрою стандартного введення число N (1 ≤ N ≤ 10000) - кількість ящиків на складі. У наступних N рядках програма читає по три натуральних числа (кожне не більше за мільйон) - розміри відповідного ящика. Програма виводить єдине число - максимальну висоту сходинок, що можна побудувати з ящиків на складі.
Приклади
|
Введення |
Виведення |
Пояснення |
|
3 7 7 7 8 8 8 9 9 9 |
0 |
Немає жодного ящика з висотою 1, тож побудувати сходи навіть висотою в 1 метр не вийде. |
|
3 4 3 1 3 5 4 7 2 7 |
3 |
У даному випадку ящик 4х3х1 використано у якості першої сходинки, ящик 7х2х7 - у якості другої, ящик 3х5х4 - у якості третьої сходинки.
|
Задача Covid2025. Боротьба з вірусами -- надскладна задача, і якщо нічого не робити, то хвороба пошириться швидко, особливо в великому місті. Маємо сітчасту мапу міста. Кожна клітинка цієї сітки - квартал, який у певний момент часу або вже завірусований, або ще ні. Вірус поширюється наступним чином: якщо два сусідніх квартали вже завірусовані, то на наступний день і поточний квартал теж буде завірусовано. Потрібно знайти, на який день вірус заполонить максимальну кількість кварталів і перестане поширюватися.
Технічні умови. Програма Covid2025 читає з пристрою стандартного введення числа N, M (1 ≤ N, M ≤ 1000) - висота та ширина мапи міста відповідно. У наступних N рядках програма читає по M символів “P” або “.”. Символ “P” означає, що відповідний квартал вже завірусовано, а символ “.” - що ще ні.
Приклади
|
Введення |
Виведення |
Пояснення |
|
2 2 .. .. |
1 |
Місто зовсім немає кварталів, які завірусовано, тож вже на перший день епідемія досягне свого “піку” та вірус перестане поширюватися. |
|
2 2 P. .. |
1 |
Місто має один осередок вірусу, але цей осередок не зможе поширитися на сусідні квартали (адже жоден з кварталів не має двох сусідніх уражених вірусом кварталів) |
|
3 3 PP. P.. ... |
2 |
На другий день місто матиме наступну мапу : PP. PP. ... |
Задання підготували Г.Непомнящий М.Стречень, Ю.Пасіхов