1. Завдання 3 туру NetOI-2023

Задачі 3 туру NetOI-2023

ЗАВДАННЯ ВИКОНАТИ ДО 0 ГОДИН  4.02.2024 р.

Зверніть увагу на назву 1 задачі!

Прийом робіт продовжено до 0 годин 5.02.24

Задача Crossword2024. Задано набір з N різних слів, кожне слово складається з великих літер латинського алфавіту. Необхідно знайти кількість неоднакових кросвордів, які можна скласти з цих слів. Крім того, нас цікавлять лише кросворди з одним словом по вертикалі та двома словами по горизонталі.

Два кросворди вважаються однаковими, якщо вони складаються з однакових наборів слів, що перетинаються у тому самому порядку і у тих самих позиціях.

M   M A Y   M   D A Y	M   D A Y   M   M A Y	M A M A     A   D A Y	M   M A Y   M   D A Y
Неоднакові кросворди		І це теж неоднакові кросворди

Приклади
Введення	Виведення	Введення	Виведення
3 KEY RAY MAMA	2	3 DAY MAY MAMA	14

Технічні умови. Програма  Crossword2024 читає з пристрою стандартного введення число N (N≤10), а далі в N рядках - слова, що складаються не більше як з 10 великих літер латинського алфавіту. Програма виводить на пристрій стандартного виведення єдине число – шукану кількість кросвордів.

 

 

 

 

---

 

Задача Jump2024. Задано таблицю з N рядків і M стовпчиків з цілими невідʼємними числами. Гравець починає з клітинки першого рядка будь-якого стовпчика і щоразу стрибає на наступний рядок, обираючи клітинку таким чином, щоб значення на ній відрізнялось від поточного щонайменше в K разів. Наприклад, якщо K = 2 і значення на поточній клітинці рівне 7, то гравець може стрибнути на клітинки, у яких записано або число, не більше за 3, або число, що не менше за 14.

Гравцю необхідно зібрати найбільшу можливу суму, рухаючись за заданими правилами  до останнього рядка.  Якщо зібрати суму неможливо, необхідно вивести -1.

Технічні умови. Програма Jump2024 читає з пристрою стандартного введення в першому рядку  3 числа N,M,K  (N, M,K ≤ 700), далі в N рядках по M чисел власне елементи таблиці  (кожен не більший за 10¹⁹  ). Всі числа розділено пропусками Програма виводить на пристрій стандартного введення єдине число – шуканий результат.

Приклади

Введення	Виведення	Коментар
2 4 3 1 2 3 4 5 4 3 2	6	Починаємо у клітинці зі значенням 1, стрибаємо на клітинку зі значенням 5. Це дозволено, бо 5 не менше за 1 * K = 1 * 3
Введення 3 1 2 1 8 3	Виведення       12	Єдиний можливий маршрут 1-8-3 є коректним за умовою задачі.

---

Задача Horse2024. На квадратній шаховій дошці розміром NxN розміщено 2 шахових коня (чорнй та білий). Рядки і стовпці дошки пронумеровані від 1 до N. Коні можуть знаходитися в 1 клітинці та ходити по черзі за правилами руху шахового коня, розпочинати може будь-який. Через яку мінімальну кількість ходів  коней вони можуть опинитися в одній клітинці (один хід – це рух одного коня, загальна кількість ходів – їх сума).

Технічні умови. Програма  Horse2024 читає з  пристрою стандартного введення в одному рядку через пропуск 5 чисел N (1≤N ≤10⁶) далі 2 координати W1 та W2 білого коня і дві координати  В1 та В2 чорного коня (1≤W1,W2,B1.B2≤N). Програма виводить на  екран єдине число – мінімальну сумарну кількість ходів коней. Якщо зустріч не відбувається, вивести число -1

Коментар. Якщо ви не граєте в шахи – кінь ходить літерою Г

 

Введення	Виведення
8 1 1 8 8	6
2 1 1 2 2	-1
5 3 3 3 3	0
Введення	Виведення
8 1 1 8 8	6
2 1 1 2 2	-1
5 3 3 3 3	0

---

Задача Numhanoy. Нехай маємо N стрижнів, виставлених в ряд і M дисків діаметром 1, 2, …, M. Необхідно знайти кількість різних ханойських замків, які можна скласти, використавши усі диски.

Ханойським замком називається N стрижнів, кожен з яких має хоча б один диск. Диски також мають іти у спадному порядку - тобто певний диск має стояти або на землі, або на диску більшого діаметру, тобто бути ханойською вежею. Оскільки відповідь дуже велика, потрібно вивести її за модулем 1000000007.

Технічні умови. Програма Numhanoy читає з пристрою стандартного введення 2 числа N та M  (N, M ≤ 10⁵). Програма виводить єдине число – шукану величину по модулю 1000000007.

 

Приклади

Введення	Виведення	Коментар
3	6	Можливі ханойські замки. Числа від 1 до М – діаметри дисків,  числа  в спільних дужках   означає, що диски на одному стрижні. (1) (2) (3) (1) (3) (2) (2) (1) (3) (2) (3) (1) (3) (1) (2) (3) (2) (1)
2 3	6	Можливі ханойські замки: (1 2) (3) (1) (2 3) (1 3) (2) (2) (1 3) (2 3) (1) (3) (1 2)
3 4	36

 

---

 Задача Newyearset.  Нехай задано натуральне число N.   Дозволяється відняти від N будь-який дільник числа N, більший за 1, що не перевищує N. З отриманим числом N’ дозволяється робити те саме - тобто відняти будь-який дільник нового числа N’, більший за 1, що не перевищує N’. Множину чисел, які можна отримати з заданого числа N, називають новорічним набором для числа N. Необхідно знайти кількість чисел у такому новорічному наборі.

Технічні умови. Програма Newyearset читає з пристрою стандартного введення  число N  (N  10¹¹). Програма виводить на пристрій стандартного виведення  кількість чисел у такому новорічному наборі.

 

Введення	Виведення	Коментар
2	2	До новорічного набору входять числа 0 та 2.
8	6	До новорічного набору входять числа: 8 6 (8 - 2 = 6) 4 (8 - 4 = 6) 3 (8 - 2 = 6 -> 6 - 3 = 3) 2 (8 - 4 = 4 -> 4 - 2 = 2) 0 (8 - 8 = 0)
10	8

---

Завдання підготували К.Денисов, Г.Непомнящий, М.Стречень, Ю.Пасіхов