12.02.23 Початок о 10-00. Час виконання - 5 годин.
Задача Decrease. На жаль війна зробила суворою реальністю під час тривоги замість уроків в класі сидіння в укритті. Чим зайнятися учням? Вчитель вирішив провести конкурс, запропонував гру - і час спливає непомітно, і наче користь – розвиває мислення. Є масив, що складається з N чисел. За один крок дозволяється зменшити на 1 кілька (можливо один) підряд рівних елементів. Мета – зробити всі елементи рівними нулю. За яку мінімальну кількість кроків це може бути зроблено? А ви напишіть програму, яка зуміє гарантовано перевірити результат учнів.
Технічні умови. Програма Decrease зчитує з клавіатури (стандартного пристрою введення) натуральне число N (1≤N≤2∙105) – кількість чисел у масиві, а з наступного рядка N невід’ємних цілих чисел, елементів масиву, кожне з яких не перевищує 2∙109. Програма виводить на екран (стандартний пристрій виведення) єдине число – шукану мінімальну кількість кроків.
Приклади
Введення 1 Виведення 1
3 4
3 4 1
Введення 2 Виведення 2
3 6
3 1 4
Задача Shiny. Один маловідомий на той час математик, переглядаючи свою телефонну книжку, звернув увагу на те, що телефонний номер його знайомого 4937775 має таку цікаву властивість, що сума його цифр дорівнювала сумі цифр усіх його простих співмножників. Число 4937775 розкладається на прості співмножники таким чином: 4937775=3×5×5×65837. Сума цифр телефонного номера дорівнює 4+9+3+7+7+7+5=42 і сума цифр його розкладання на прості множники також дорівнює 3+5+5+6+5+8+3+7=42. Назвемо такий тип чисел «блискучими». Оскільки таку властивість мають всі прості числа, математик не включив їх до множини «блискучиАле відомість математику принесла знайдена можливість знаходити інші числа, що підпадають під означення. Для кожного числа із заданого набору знайдіть мінімальне «блискуче» число, що його перевищує.
Технічні умови. Програма Shiny зчитує з клавіатури (стандартного пристрою введення) натуральне число N (1≤N≤10) – кількість чисел у наборі, а також N натуральних чисел ai (1≤ ai ≤231). Всі числа розділено пропуском.
Програма Shiny виводить на екран (стандартний пристрій виведення) N знайдених чисел через пропуск.
Приклад
Введення Виведення
2 4937774 234 4937775 265
Задача Domino2023. Петрик придумав нову гру – бінарне доміно. На кісточках зображені лише нулі і одиниці. Таким чином, існують три типи плиток доміно: з нулями на кінцях, з одиницями на кінцях, а також з одиницею на одному кінці і нулем на іншому: 🀱, 🀹, 🀲. Гра починається з єдиної плитки на столі. Далі, гравці по черзі беруть одну плитку з купки і кладуть на стіл до одного з кінців – як і у класичному доміно, дозволено класти нуль лише до нуля, одиницю лише до одиниці. Обидва гравці бачать зміст купки (тобто кількість доміно певного виду, що залишились). Програє гравець, який не може зробити хід, тобто коли у купці немає доміно виду, який можна було б поставити на стіл. Звісно, що Петрику цікаво, щоб гра була збалансована, тому він просить вас для певних початкових ігрових ситуацій сказати, хто переможе за правильної гри обох гравців.
Технічні умови Програма Domino2023 читає з клавіатури (стандартного пристрою введення) єдине число N (1 ≤ N ≤ 10) – кількість ігрових ситуацій, які цікавлять Петрика. Далі програма читає N рядків, кожен з яких містить пʼять цілих невідʼємних чисел, що задають ігрову ситуацію – X, Y, O, I, M (0 ≤ X, Y≤ 1, 0 ≤ O + I + M ≤ 1000). X та Y задають цифри на кінцях першої плитки доміно, O – кількість доміно типу «два нулі» (🀱), I – кількість доміно типу «дві одиниці» (🀹), M – кількість доміно «одиниця та нуль» (🀲). Програма виводить на екран єдиний рядок з N цифр – 1 та 2, де i-те число позначає, хто виграє у i-тій ігровій ситуації. Зверніть увагу, що цифри не мають бути розділені пропусками.
Приклад:
|
__Введення__ |
__Виведення_ |
__Коментар_________________________________________________ |
|
3 1 0 0 0 20 0 0 1 1 0 0 1 1 1 1 |
212 |
У першій ігровій ситуації гра закінчиться, коли скінчилися доміно типу 🀲, що станеться на ході першого гравця, тому виграє другий. У другій ситуації, є можна поставити лише одну плитку доміно типу 🀱, після якої гра закінчиться. У третій ігровій ситуації, у першого гравця є наступні опції:Поставити доміно «два нулі», отримавши 🀱🀲, тоді другий гравець ставить доміно «один-нуль», 🀱🀲🀸 залишаючи у купці лише доміно «дві одиниці», яке не може бути поставлене до жодного з кінців ланцюжка доміно Аналогічним чином поставити «дві одиниці», ситуація ідентична попередній Поставити доміно «один-нуль», отримавши або нулі на обох кінцях ланцюжка, або одиниці. На кожен з цих ходів другий гравець може покласти відповідне доміно, залишивши першого гравця з непідходящою плиткою доміно. Іншими словами, ланцюжки перетворень можуть виглядати наступним чином: 1) 🀲 -> 🀲🀸 -> 🀲🀸🀱 -> залишається 🀹, яку не можна поставити; 2) 🀲 -> 🀸🀲 -> 🀸🀲🀹 -> залишається 🀱, яку не можна поставити
|
Задача Coop. Гноми-велетні знамениті своїми гігантськими розмірами та любов'ю до золота. В одному з поселень гномів існує N пар гномів, причому в i-ій (1 ≤ i ≤ N) парі як чоловік-гном, так і жінка-гном мають зріст рівно i. Крім того, кремезні чоловіки-гноми зазвичай виступають у якості опори, у той час як тендітні жінки-гноми вправно орудують киркою. Геологічна розвідка виявила неподалік селища гномів вертикальну нескінченно високу скелю. Гноми вирішили, що там з великою вірогідністю буде золото, тож домовилися вранці вирушити на полювання на нього. Щоправда, дійшовши до скелі, гноми виявили проблему: K сімей не прийшли на зустріч. Гноми збираються довбати скелю в наступний спосіб: нехай якийсь чоловік-гном зросту A виступає опорою для якоїсь жінки-гнома зросту B. Разом цей тандем здатний довбати скелю лише на висоті A + B. Для кожної висоти обирається підходящий тандем, причому будь-який присутній гном може виступати (в різні моменти часу) у складі різних тандемів. Тепер гномів цікавить, скільки ж існує досяжних висот. Іншими словами, для скількох висот знайдеться підходящий тандем?
Технічні умови Програма Coop спочатку зчитує з клавіатури (стандартного пристрою введення) два цілих числа N(1 ≤ N ≤ 2·109) та K (1 ≤ K ≤ min{N, 10000}) – кількість пар гномів у поселенні та кількість відсутніх на видобутку сімей гномів. Потім зчитується рівно K різних невід’ємних цілих чисел – номери сімей у довільному порядку, що не прийшли на видобуток. Кожне число не перевищує N. Програма виводить на екран (стандартний пристрій виведення) єдине ціле число – кількість досяжних висот.
Приклад
Введення 1 Виведення 1
6 2 9
3 6
Введення 2 Виведення 2
5 3 3
2 3 4
Введення 3 Виведення 3
10 4 15
2 3 4 5
Задача Chdk. Команда NetOI вирішила взяти участь у чемпіонаті з гри «Що? Де? Коли?». Чемпіонат складається з t турів. Кожен тур містить деяку кількість запитань. Серія питань – це підпослідовність питань одного туру від l-ого до r-ого включно, причому l ≤ r і підпослідовність неперервна (беруться до уваги всі підряд питання від l-ого до r-ого). Команда будуть вважати серію питань вдалою, якщо вони дадуть відповіді не менш, ніж на q відсотків питань з цієї серії. Для підняття настрою команди, знайдіть для кожного туру кількість вдалих серій.
Технічні умови Програма Chdk зчитує з клавіатури (стандартного пристрою введення) число t – кількість турів у чемпіонаті, 1 ≤ t ≤ 10. У наступних t рядках знаходиться інформація про кожен з турів у такому вигляді: n q a1...an, 0 ≤ q ≤ 100. ai може бути 0, якщо команда не відповіла на i-те питання, або ж 1 в іншому випадку. Крім того, усього на чемпіонаті було задано не більш, ніж 500000 питань. Усі числа вхідних даних цілі. Програма виводить на екран (стандартний пристрій виведення) рівно t чисел в один рядок через пробіл: i-те число дорівнює кількості вдалих серій питань у i-ому турі.
Приклад
Введення Виведення
2
10 50 1 0 1 0 1 1 0 0 0 1 32 4
5 50 1 0 0 0 1
Завдання підготували Журі ХХІІ Всеукраїнської комплексної олімпіади "Турнір чемпіонів", Г.Непомнящий, М.Стречень, Ю.Пасіхов