ЗАВДАННЯ ІІ ТУРУ NetOI-2023
ЧЕРЕЗ ТЕХНІЧНУ ПОМИЛКУ (ВЖЕ ВИПРВЛЕНУ) ТЕРМІН ПРОДОВЖЕНО ДО 0 ГОДИН 09.01.2024
Задача Game2024. Юний талант Василько Голопупенко грає у свою улюблену комп'ютерну стрілялку. У внутрішньоігровому магазині можна придбати 1 очко сили (d) за 1 монету або збільшити швидкість стрільби (s) на 1 за P монет. Основною характеристикою кожного гравця є його «шкода» за секунду (DPS = d * s). Василько, як порядний гравець, прагне максимально поліпшити свої шанси на перемогу. Визначте максимально можливу величину DPS, яку Василько зможе досягти, маючи при собі M монет. На початку гри d = s = 0. Обмежень на кількість покупок немає.
Технічні умови. Програма Game2024 читає з пристрою стандартного введення через пропуск M та P (1 ≤ M, P ≤ 2*109) і виводить на пристрій стандартного виведення шукану величину.
Приклад
Введення 10 2
Виведення 12
Коментар. 12 = 2 * 6.
Задача Mine2023 Карта мінного поля являє собою прямокутну таблицю заповнену 0 та 1. Якщо клітинка замінована, в ній записано число 1, ні – записано число 0. Якщо дві клітинки мають спільну сторону, то вони належать одній області. Якщо спеціальним снарядом влучити в одну з клітинок з міною, вибухає вона і всі міни її області. Так можна швидко розмінувати всю площу. Порахувати, яку мінімальну кількість пострілів треба зробити, аби розмінувати все мінне поле перед наступом.
Технічні умови. Програма Mine2023 читає з пристрою стандартного введення 2 натуральних числа N та М ( 2 ≤ N,M ≤ 1000 ) - розміри таблиці. Далі N стрічок по M символів 0 та 1 через пропуски – власне таблицю. Програма виводить на пристрій стандартного виведення єдине число – кількість областей, заповнених 1.
Приклад
Введення Виведення
4 3 3
0 1 1
1 0 0
1 0 1
0 0 0
Задача Rating. Приватний підприємець Василь набрав до своєї фірми k підлеглих. Щоб у фірмі був порядок, він вирішив надати рейтинги всім підлеглим, присвоюючи кожному певне натуральне число – чим більше це число, тим вище рейтинг (і заробітна платня) підлеглого. Для повного порядку всі підлеглі одержали різні рейтинги, а для розширення можливостей надання рейтингів, Михайло вибирає кількість рейтингів, більшу ніж k. Скільки варіантів наборів r різних рейтингів у розпорядженні Михайла, якщо встановлений ним найвищий рейтинг – n, а найменша різниця між рейтингами дорівнює одиниці?
Технічні умови. Програма Rating читає з пристрою стандартного введення цілі чилса n, k (1<k≤30, 3≤n≤60). Програма виводить на пристрій стандартного виведення шукану величину r.
Приклад
Введення Виведення
11 4 120
Задача Np2023. Герой олімпіад Василько отримав у подарунок перестановку N чисел a1,a2,…,aN. (у перестановці кожне з чисел 1, 2,…,N міститься рівно один раз) Він застосував її для набору чисел 1,2,…,N таким чином. Перше число (тобто 1) поставив на позицію a1, друге (тобто 2) - на a2, останнє (тобто N) - на aN. Наприклад, для перестановки 2 4 5 1 3 Василько матиме 4 1 5 2 3. Далі Василько повторює ці дії (i те число ставиться на ai позицію) для отриманого набору чисел. Так, з 4 1 5 2 3 вийде 2 4 3 1 5. Скільки дій знадобиться Васильку, щоб знову отримати 1, 2,…,N?
Технічні умови. Програма Np2023 читає з пристрою стандартного введення з першого рядка натуральне число N (1< N<=200), a далі в цьому ж рядку через пропуски – перестановку a1,a2,…,aN. Гарантується, що після кожної дії Василька порядок чисел у наборі змінюється. Програма виводить на пристрій стандартного виведення єдине шукане число. Якщо Василько не зможе отримати 1, 2,…,N, програма має вивести -1.
Приклад
Введення
5
2 4 5 1 3
Виведення
6
Коментар. Василько отримає такі набори
4 1 5 2 3,2 4 3 1 5,1 2 5 4 3,4 1 3 2 5,2 4 5 1 3,1 2 3 4 5
Задача Tetris2023. Є в достатній кількості прямокутні плитки двох типів - квадрати розміром 1 × 1 і прямокутники розміром 1 × 2. За допомогою цих плиток необхідно замостити доріжку розміром 2 × n, при цьому плитки не повинні накладатися одна на одну. Плитки дозволяється повертати. Вам необхідно підрахувати кількість способів замощення доріжки 2×n за допомогою наявних плиток .
Технічні умови. Програма Tetris2023 читає з пристрою стандартного введення єдине ціле число n - довжина доріжки (1≤ n ≤1018). Програма виводть на екран кількість способів замощення смуги за допомогою плиток вказаного виду. Відповідь запишіть за модулем (109 + 9)
Приклади
|
Введення |
Виведення |
|
2 |
7 |
|
3 |
22 |
Коментар
В першому прикладі n = 2, доріжка має розміри 2 × 2, і її можливо замостити наявними плитками 7 способами:
|
|
Завдання підготували Г.Непомнящий, Й.Ентін, Ю.Пасіхов, М.Швець