Завдання II етапу Всеукраїнської учнівської олімпіади з інформатики (програмування) 2016

Опубліковано завдання учнівської районної олімпіади з інформатики (програмування). Нагадаємо, що доступними мовами були: Pascal, C++, C# i Java. Свої розв’язки учасники олімпіади тестували в онлайн режимі на сайті http://algotester.com.

Скачати олімпіадні завдання

Задача А

Торт для Петрика
Зовсім скоро у Петрика день нароження і він в нетерпінням чекає цього свята. Його друзі слоненята вирішили зробити йому подарунок і приготувати ідеальний торт.

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

Слонетяна вирішили, що радіус найбільшого ярусу їхнього торту має бути 11. Допоможіть слоненятам обчислити яким же буде радіус найменшого.
Вхідні дані

У єдиному рядку через пробіл задано два цілих числа N та II відповідно кількість ярусів та радіус набілишого яруса в ід сланому торті.
Вихідні дані

Виведіть єдине число радіус найменшого ярусу з абсолютною похибкою, що не нервищує 10-4.

Задача В

Петрик із Слоненятком грають у комп’ютерну гру “Змійка”. Гра проходить на наскінченній площині і полягає в наступному: спочатку задано координати х, у голови змійки. Гра триває N ходів: на кожному ході вибирають напрямок в якому буде рухатись голова змійки далі. Хвіст і тіло змійки залишаються нерухомими, тобто після кожного коректного ходу довжина змійки зростає на 1. Гра закінчується успішно якщо буде виконано всі N ходів і голова змійки жодного разу не зіткнеться із тілом змійки.

Для вибраних Петриком початкових координат х, у і послідовності ходів, обраних Слоненятком, вам слід відповісти чи успішно закінчиться гра. У випадку, коли гра закінчиться неуспішно, виведіть номер ходу, після якого відбудеться перше зіткнення голови змійки з тілом.
Вхідні дані

У першому рядку задано х, у — початкові координати змійки. У другому рядку задано стрічку S, що визначає послідовність ходів. Стрічка S складається тільки із символів ’L’, ’Д’, ’U’, ’D’. Якщо голова змійки знаходиться в точці з координатами (х, у), то у випадку команди ’L’ вона перейде в точку (х — 1, у) ’Д’ — в точку (х + 1, у) ’U’ — в точку (x, у + 1) ’D’ — в точку (x, у — 1).

Вихідні дані

Виведіть ” Success” (без лапок) якщо гра завершиться успішно. Інакше, в першому рядку виведіть ”Fail” (без лапок), в другому рядку виведіть номер ходу після якого відбудеться перше зіткнення голови змійки з тілом. Ходи номеруються починаючи з одиниці.

Зачада С

Слоненя подарувало Петрику набір кубиків, на кожному з яких написана певна буква, і впорядкувало їх так, що послідовніств букв утворювала стрічку Э. Петрик, як великий естет і поці-новувач стрічок, відразу почав проводити різні експерименти над нею: брав довілвні два кубики і міняв їх місцями.

В резулвтаті таких змін можна утворити багато різних стрічок. Слоненятко стало запитувати Петрика, яку найменшу в алфавітному порядку стрічку він може утворити.

Щоб завдання не здавалосв таким простим, Слоненя дозволяє Петрику обмінювати місцями тілвки кубики на певних позиціях. Кожен з доволених обмінів він може зробити довілвну кілвкіств разів.
Вхідні дані

У першому рядку задано стрічку Э. Гарантуєтвся, що стрічка складаєтвся виключно із меленьких букв англійського алфавіту.

У другому рядку задано ціле число М — кількість пар індексів кубиків, які можна міняти місцями.

В наступних М рядках задано по два різних числа цілих числа щ та Ь – індекси кубиків, які можна міняти місцями. Гарантується, що в списку жодна пара не повтрюється більше одного разу. Пари (а, Ь) та (Ь, а) вважаються однаковими.
Вихідні дані

В єдиному рядку виведіть найменшу в алфавітному порядку стрічку, яку зможе отримати Петрик.

Задача D

Петрик і Слоненя грають в захоплюючу настільну гру. У них є нескінченна пряма, на якій в позиції 0 знаходиться фішка. Задано N позицій хі, Х2,…, х^, по яких гравці переміщують фішку. Нехай фішка знаходяться в позиції Хі (вважатимемо, що перед першим ходом і=0 та жо=0), тоді на своєму ході гравець обирає число т таке, що 1 < т < К та і + т < N та переміщує фішку в позицію Хі+т. При цьому гравець отримує Хі+т — Хі очок за свій хід (зауважте, що кількість отриманих очок може бути від’ємною).

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

В першому рядку дано два цілі числа через пробіл N та К. В другому рядку дано N цілих чисел Хі, Х2, …, Хм-

Вихідні дані

В єдиному рядку виведіть ціле число – максимальну сумарну кількість очок, яку Петрик може набрати.