1. Задания олимпиады

Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики 2021-2022 н.р. у Вінницькій області 

5 лютого 2022 р.  Час виконання - 5 годин.

Задача  Fleas. Три блохи стрибають по числовій осі цілих  чисел. На початку кожна комаха  «сидить»  на якомусь цілому числі.  За один хід одна з зовнішніх комах стрибає в простір між іншим двома, «займаючи», зрозуміло, інше ціле число.  Ні в якому разі дві блохи не можуть «займати» однакове число. Допоможіть їм стрибати якомога довше.

Технічні умови Програма   Fleas   читає  з пристрою стандартного введення три цілих числа A, B і C (0 < A < B < C < 10⁹) -  початкові позиції бліх. Програма виводить на пристрій стандартного виведення найбільшу кількість стрибків, яку можуть зробити блохи.

ПРИКЛАДИ

Задача Password2022 Для проходження останнього рівня нової гри необхідно після проходження всіх попередніх рівнів отримати пароль, що являє собою послідовність маленьких англійських літер. Під час гри пароль з’являється на екрані, але дуже швидко зникає. Герой олімпіад Василько тричі доходив у грі до останнього рівня і щоразу записував пароль на чернетці. Деякі символи Василько не встигав записати (він замінив їх зірочками) , а деякі записав неправильно. Відомо, що гра видає  даному учаснику один і той самий пароль. Допоможіть Васильку відновити цей пароль. Програма штучного інтелекту відновлює пароль за таким алгоритмом:

• якщо  у всіх трьох записах  3 або 2 літери  у відповідній позиції співпадають, то ця літера гарантовано входить до пароля на цій позиції;
• якщо у двох записах у відповідній позиції «зірочки», а у третьому – літера, то вона входить до пароля у відповідній позиції;
• у решті випадків відновити літеру у даній позиції неможливо, тому на цій позиції у паролі доведеться поставити зірочку. 

Технічні умови. Програма Password2022 читає з пристрою стандартного введення три рядки однакової довжини, не більші 1000 символів завдовжки – маленькі англійські літери або зірочки. Програма виводить на пристрій стандартного виведення відновлений рядок – пароль,

ПРИКЛАД

Задача Robot2022. У гуртку з робототехніки є прямокутне поле MxN клітинок. Клітинки пронумеровано з 1 до M з півночі на південь та з 1 до N з заходу на схід. У клітинці (1,1) знаходиться робот, який може пересуватись або на південь, або на схід на сусідню клітинку. На перехід між клітинками робот не витрачає енергії, але при зміні напрямку руху робот витрачає одну енергію.  Робот  може рухатись, якщо в нього немає жодної енергії, але не може змінити напрямок руху. Скількома способами  робот може потрапити до клітинки (M,N), якщо на початку він мав K енергій?

Технічні умови. Програма Robot2022 читає з пристрою стандартного введення через пропуск натуральні числа M,N,K (2≤M,N≤5000, 1≤K≤10000) і виводить на пристрій стандартного виведення шукану кількість способів за модулем 1000000007.

ПРИКЛАД

Введення   4 5 3

Виведення 19

Задача Jump2022  Жабенята роду Пепе дуже вправні в математиці, а тому представляють надзвичайний інтерес для науковців. Нещодавно вчені виявили, що якщо розмістити жабеня у якусь з  клітинок на смужці,  і у кожній клітинці написати число, жабеня може стрибати вперед чи назад, а стрибок може мати  максимальну довжину  у таку кількість клітинок, яка написана на поточній.   Більше того, жабенята достатньо розумні, щоб знайти маршрут, навіть якщо він достатньо складний. Тепер, знаючи числа, що написані на смужці, науковцям цікаво, чи існує маршрут з першої клітини на останню за  даних умов.

Технічні умови Програма jump2022 читає з пристрою стандартного виведення ціле число T (1 ≤ T ≤ 5) - кількість смужок.

Далі йдуть рівно T рядків, у кожному спершу ціле число N (1 ≤ N ≤10⁵ ) - довжина смужки, а далі рівно N цілих невід’ємних чисел, кожне з яких не перевищує 10⁵  - числа, що записані на смужці. Програма виводить рядок з T літер “Y” та “N”, де i-та літера позначає відповідь для i-тої смужки (Y, якщо існує маршрут, N, якщо маршруту немає). 

Приклад

Задача Game2022 Антон і Влад мають деякі числа і вирішили зіграти з ним у наступну гру. Спершу Антон робить свій хід - може або відняти від числа 1, або нічого не віднімати. Далі Влад за свій хід може відняти 2, або ж нічого не відіймати. Далі Антон може або відіймати, або не відіймати 4. У свою чергу Влад наступним ходом може або віднімати 8, або ні. Більш формально - Антон по черзі робить ходи з парними степенями двійки, як то 1, 4, 16, 64…, а Влад - з непарними, як то 2, 8, 32, …. Гра продовжується до тих пір, поки потенційне віднімання поточного гравця не зробить число від’ємним - у такому випадку поточний гравець програв. Наприклад, якщо зараз хлопці мають число 7, а Влад має зробити свій хід з числом 8, він програє - бо потенційне відіймання від сімки вісімки зробить результат від’ємним. Обох хлопців цікавить, хто виграє за правильної стратегії обох?

Технічні умови. Програма Game2022 читає з пристрою стандартного введення число T (1≤ T ≤ 5) - кількість тестів. Далі програма читає рівно T чисел A_i  (0 ≤ A_i  ≤ 10¹⁸  - числа, з якими хочуть грати Антон і Влад. Для кожного з цих чисел програма має вивести A або V в залежності від того, чи виграє Антон (A), чи Влад (V). 

Приклад