Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики

(Вінницька область)

31 січня 2016 р, сервер //netoi.org.ua

===================================================================

Задача Hotel.   Місто Вінниця впевнено стає туристично привабливим. Потік туристів постійно зростає, будуються нові готелі. Готель «Олімпія» розрахований на n постояльців. Всі номери у готелі двомісні, тому зрозуміло, що n число парне.   До готелю має заїхати група туристів. Половина групи бажає мати сусідів по номеру, а половина бажає жити в номері по одному, тобто готова сплатити за  2-місний номер, але у номері бути без сусіда. З якої максимально  можливої кількості туристів може складатися група, аби адміністратор готелю зміг задовільнити всі забаганки? На момент  прибуття групи в готелі «Олімпія» не було постояльців, тобто всі номери вільні.

Технічні умови Програма   Hotel  читає з пристрою стандартного введення число n (2 <=n <= 10⁹ ) – кількість місць у готелі. Програма виводить на пристрій стандартного виведення максимальну чисельність групи, яку можна розселити так, аби всі були задоволені.

Приклад

 Введення 20

Виведення 12

===================================================================

Задача Cube2016. Розглянемо куб, сторони якого пофарбовані в певні кольори. Куб завжди можливо повернути до спостерігача так, що видно буде рівно одна, дві або три його грані. Дізнайтеся, чи вдасться  заданий куб повернути таким чином,  щоб можливо було побачити дві або три  його грані так, щоб всі видимі грані були одного кольору. Для зручності кольори позначено числами  від 1 до 10.

Технічні умови Програма Cube2016   читає  з  пристрою стандартного введення  опис кількох кубів.  В першому рядку  ціле число N - кількість кубів (1 <= N <=10).  Кожний з наступних N рядків містить  опис одного куба: 6 цілих чисел в інтервалі від 1 до 10 через пропуск, числа вказують на  кольори граней. Числа виписані в такому порядку:

передня_грань,  задня_грань, ліва_грань, права_грань верхня_грань, нижня_грань

Програма виводить на пристрій стандартного виведення одну стрічку з  N  символів (по одному для кожного з кубів, описаних при введенні). Якщо куб можливо повернути так, аби виконувалась умова, виводимо Y, а якщо не можливо, то N.

Приклад

===================================================================

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

Технічні умови. Програма Maxseq читає з пристрою стандартного введення  число N  (4≤N≤2*10⁸ ). Програма виводить на пристрій стандартного виведення у єдиному   рядку через один пропуск  кількість виграшних квитків, а далі  номери першого та останнього квитка з числа тих, що перемогли (нагадаємо, що переможні номери повинні утворювати неперервну послідовність натуральних чисел). Якщо для даного  N не існує такої послідовності,  усі три числа мають дорівнювати 0 (у лотереї ніхто не виграв…).

===================================================================

Задача Game2016.  Два учні розважаються під час нудного уроку. Wi-Fi  у школі вимкнули, тому доводиться розважатися як це робили колись, граючи у якусь «тиху» гру на папері. Перший учень на ім’я Петро знайшов у зошиті з англійської мови сторінку з диктантом, і викреслив з тексту дві однакові літери, а на заміну їм додав одну якусь літеру. Наприклад,  набір літер {a, b, a}  він міг би перетворити в один з наборів {a, b}, {b, b}, {b, c}, . . . , {b, z}. (так як учні не дуже добре писали диктанти з англійської, в тексті були лише малі літери латинського алфавіту). Тоді аналогічним чином робить свій хід другий учень на ім’я Арсеній, а далі знову Петро – і так по черзі. Правил гри ніхто не порушує. Програє той, хто не може зробити черговий хід – на сторінці залишилися лише різні літери.  Але хлопці у вільний від вивчення шкільної інформатики час займалися програмуванням. Тому вже на другій сторінці з диктантом їм стало не цікаво – переможця (звичайно, за оптимальної  стратегії обох гравців) вони визначали, не розпочинаючи гру. Спробуйте і ви створити програму, яка може це зробити. Нагадаємо, що для гри використовувалися лише малі літери латинського алфавіту,  а Петрик завжди ходить першим.

Технічні умови. Програма Game2016 читає з пристрою стандартного введення у першому рядку кількість партій, K (1<=K<=10) які встигли за урок зіграти Петрик та Арсеній а далі K рядків, у кожному з яких без пропусків записано  рядок, що складається з  Z(k)  (1<=Z(k)<=100000)  малих літер латинського алфавіту. Програма виводить на пристрій стандартного виведення без пропусків в один рядок K символів, кожен із яких має значення G, якщо виграє Петрик, або D, якщо виграє Арсеній. 

Приклад

Введення    Виведення

2                     DG

abc

aba

===================================================================