XVIII  Всеукраїнська комплексна олімпіада з математики, фізики
та інформатики

"Турнір чемпіонів"

2011 р.

Завдання з інформатики

Задача Три грибники (MUSHROOM)

Три грибники Петро, Василь та Микола, повертаючись з лісу додому, вирішили влаштувати привал, а заодно і перекусити. Як це у нас прийнято, через деякий час кожен почав вихвалятись своїми сьогоднішніми успіхами, а з часом і ділитись знайденими грибами зі своїми товаришами. Перед привалом у кожного з них була деяка цілочисельна кількість грибів. Спочатку Петро дав Василю та Миколі по стільки грибів, скільки у них вже було. Микола швидко зрозумів, що так буде не «по-братськи», і дав Василю та Петру по стільки грибів, скільки у них стало. Василь не міг відстати від друзів і також дав кожному з друзів по стільки грибів, скільки у них на цей момент було у наявності. І тут усі з подивом виявили, що у них стало грибів порівну.

Скілько грибів було у кожного перед привалом, якщо відомо, що всі разом вони зібрали N грибів?

Технічні умови

Програма MUSHROOM читає з клавіатури одне натуральне число N (N≤30000) і виводить на екран початкові кількості грибів у Петра, Василя та Миколи відповідно. Гарантується, що відповідь для даного N існує.

Приклад:

Задача Секретне повідомлення (SECRET)

До Штірліца не дійшов лист із Центру. Перечитав  ще раз… Все одно  не дійшло…

Для передачі секретних повідомлень своїм співробітникам розвідувальна агенція «Колобок» використовує наступний метод. Спочатку повідомлення кодується з використанням стандартної таблиці ASCII, а потім розбивається на дві рівні частини. У одні  ті самі  позиції отриманих частин додається одне і те ж число, якого не було у початковму повідомленні, – так званий ключ. Після цього кожна з числових послідовностей циклічно зсувається, причому одна частина зсувається ліворуч, а друга – праворуч, кількість позицій зсуву однакова.

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

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

Технічні умови.  Програма SECRET  читає з клавіатури  число N (1≤N≤200000). Далі читаються два рядки  по N чисел, які задають знайдені Васею послідовності. В останньому рядку  одне число – ключ P. Всі  числа є цілими і лежать в межах від 1 до 255 включно.  Програма виводить єдине число – мінімальний зсув для отримання числових послідовностей початкового повідомлення. Якщо числові послідовності належать різним початковим повідомленням, вивести число −1.

Приклад:

Задача Дорожна реформа (ORIENT)

Місто Вінниця, як і більшість міст України, має мережу доріг з двостороннім рухом по кожній з них. Ця мережа має властивість зв’язності, тобто по цих дорогах можна потрапити з довільної точки міста у довільну іншу.

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

Технічні умови

Програма ORIENT читає з клавіатури два цілих числа N – кількість перехресть у місті та M – кількість доріг (1≤N≤20000, 1≤M≤200000). Далі читає M рядків, у кожному з яких записано два числа – номери перехресть, зв’язаних дорогою. Кожні два перехрестя з’єднуються не більш ніж однією дорогою.

Програма виводить на екран одне число K – максимальну кількість доріг, на яких можна увести односторонній рух.

Приклад: