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

Завдання І туру 

 А. Дивні шахи

Input file name:	chess.in
Output file name:	chess.out
Time limit:	100 ms
Memory limit:	256 M

Степан нещодавно придумав свою версію шахів, в якій гра відбувається на дошці, що має форму відмінну від традиційної.

Його дошка складається з N стовпців, i-ий з яких містить A_i клітинок. Нижні клітинки всіх стовпців утворюють один горизонтальний ряд, причому довжини стовпців впорядковані зліва направо по незростанню. На малюнку нижче наведений приклад дошки, в якій три стовпчика містять 5, 2 і 1 клітинку відповідно.

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

Формат вхідних даних. Перший рядок вхідного файлу містить ціле число N (1 ≤ N ≤ 1000) – кількість стовпців дошки. Наступний рядок містить N цілих чисел A₁, A₂, …, A_N – кількість клітинок у стовпцях (1 ≤ A_i ≤ 1000, A₁ ≥ A₂ ≥ … ≥ A_N).

Формат вихідних даних. У першому рядку виведіть число K – мінімальну кількість тур, яку можна розставити на дошці так, щоб кожну клітинку дошки била хоча б одна тура. Наступні K рядків повинні містити опис позицій тур, по одній у кожному рядку. Позиція тури задається двома числами: номер стовпця, в якому стоїть тура, і номер клітинки в стовпці. Стовпці нумеруються починаючи з 1 зліва направо, клітинки в стовпцях нумеруються знизу вгору також починаючи з 1.

Якщо існує кілька розстановок, що задовольняють умову, дозволяється вивести будь-яку з них.

Приклади вхідних та вихідних даних:

chess.in	chess.out
3 5 2 1	2 1 5 2 1

Малюнок до прикладу:

B. Анаграми

Input file name:	anagrams.in
Output file name:	anagrams.out
Time limit:	100 ms
Memory limit:	256 M

Два непорожні рядки однакової довжини називаються анаграмами один одного, якщо другий рядок складений із символів першого, і кожен символ використовується тільки один раз. Так, пари рядків «дереза» і «резеда» є анаграмами, а пари рядків «каток» і «відкат», «стежка» і «пірат» - ні.

Ви повинні визначити, чи є два даних рядки анаграмами один одного. Рядки містять тільки символи латинського алфавіту, причому великі та малі літери вважаються різними.

Формат вхідних даних. Вхідний файл описує групу тестів, що складається з декількох рядків. Перший рядок файлу містить ціле число K (2 ≤ K ≤ 5) – кількість тестів у групі. Далі слідують K пар рядків – кожна пара відповідає одному тесту. Довжина одного рядка не перевищує 3000 символів (у 50% груп тестів ця довжина не перевищує 200).

Формат вихідних даних. Вихідний файл містить єдиний рядок з K чисел, відокремлених одним пропуском. Кожне число відповідає одному тесту і має дорівнювати 1, якщо введені рядки є анаграмами, і 0 в іншому випадку.

Приклади вхідних та вихідних даних:

anagrams.in	anagrams.out
4 Acad cAda AbRa arBA duda adua termo metro	1 0 0 1

C. Гра «70368744177664»

Input file name:	game.in
Output file name:	game.out
Time limit:	100 ms
Memory limit:	256 M

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

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

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

Формат вхідних даних. У першому рядку записане одне число N (1 ≤ N ≤ 2¹⁶) – кількість чисел. Другий рядок містить N цілих чисел A_i (1 ≤ A_i ≤ 2³⁰) – числа, що записані на полі на початку гри.

Формат вихідних даних. У єдиному рядку виведіть одне число – найбільше число, що може з’явитися на полі під час гри.

Приклади вхідних та вихідних даних:

game.in	game.out
2 4 4 4 8	16
9 4 4 4 4 4 4 4 4 4	32

D. Цікаве число

Input file name:	numbers.in
Output file name:	numbers.out
Time limit:	100 ms
Memory limit:	256 M

Степан на факультативі з програмування почав вивчати системи числення. На першому уроці вчитель розповів про систему числення з основою два, дуже популярною в комп'ютерному світі. На другому уроці Степан дізнався про систему числення з основою три. І так далі на кожному наступному уроці він дізнавався про нові системи числення, так що на i-му уроці була розглянута система числення з основою i+1.

Щоб краще запам'ятати, Степан на кожному уроці бере одне і те ж число X і записує його в зошит в останній вивченій системі числення. Приклад переведення числа 81 в систему числення з основою 6:

Одного разу Степан помітив, що у записаного ним числа X в новій системі числення всі цифри однакові. До того ж, він розуміє, що таке відбувається вперше, і ні на якому з попередніх уроків число не виходило таким цікавим.

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

Формат вхідних даних. Єдиний рядок вхідного файлу містить одне ціле число X (1 ≤ X ≤ 10¹²) – число записане в десятковій системі числення.

Формат вихідних даних. Вихідний файл повинен містити одне ціле число B (2 ≤ B) – шукана система числення.

Приклади вхідних та вихідних даних:

numbers.in	numbers.out
3	2
219	8
1009	1008

Пояснення до прикладів:

1.         «3» – це «11» в системі числення з основою 2.

2.         «219» – це «333» в системі числення з основою 8.

3.         «1009»  – це «11» в системі числення з основою 1008.

Е. Хрестики-нулики 2015

Input file name:	game.in
Output file name:	game.out
Time limit:	300 ms
Memory limit:	128 M

Два брата Сергій і Іван любили довгими зимовими вечорами грати в різні ігри. Особливою популярністю у хлопців користувалася гра «Хрестики-нулики». Однак через свою простоту вона їм швидко стала нецікавою. Брати вирішили придумати модифікацію цієї гри і назвали її «Хрестики-нулики 2014».
Для гри необхідний аркуш паперу з N клітинками по вертикалі і N по горизонталі, який назвемо ігровим полем. Для ускладнення і неповторності гри деяку кількість клітин може бути закрашено. Гравці ходять по черзі, починаючи з гравця, що грає хрестиками. За один хід гравцеві дозволяється вибрати будь-яку порожню незафарбовану клітинку і намалювати там фігуру свого типу (гравець, який грає хрестиками, може малювати тільки хрестики, який грає нуликами - тільки нулики). Гра продовжується до тих пір, поки на полі існує хоча б одна порожня і незафарбована клітинка або з'явиться рядок/стовпчик, в якому відсутні порожні і незафарбовані клітинки і кількість фігур одного типу більше кількості фігур іншого типу. Якщо в цьому рядку/стовпці кількість хрестиків більше ніж кількість нуликів, то виграв гравець, який грає хрестиком, а якщо більше нуликів - виграв гравець, який грає нуликами. Якщо на полі не залишилося жодної порожньої клітинки і в кожному рядку і стовпці кількість хрестиків і нуликів збігається, то вважається, що гра зіграна в нічию. У будь-яку незафарбовані клітинку дозволяється ставити не більше однієї фігури.
Івану дуже не щастило - він весь час програвав своєму супернику, але, тим не менш, не сумував, граючи партію за партією. Одного разу, зігравши в нічию, Іван був на сьомому небі від щастя і вирішив поділитися своїм успіхом з батьками. Для більшої переконливості хлопці вирішили показати їм ігрове поле, отримане після гри.
Але от невдача... Іван ненавмисно пролив на ігрове поле склянку води, від якої деякі фігури розпливлися, і їх неможливо було розпізнати. Чітко можна було розібрати тільки зафарбовані клітини. Хлопці вирішили відновити ігрове поле. Допоможіть Сергію та Івану відновити ігрове поле, отримане після гри в «Хрестики-нулики 2014», яка завершилася в нічию.

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа N, M (2 ≤ N, M ≤ 80).

У наступних N рядках файлу записано по M символів без пробілів. Кожен j-й символ в i-му рядку описує відповідну клітинку ігрового поля.

Для опису клітинки ігрового поля допускається чотири типи символів: 'X' (ASCII 88) - зафарбована клітинка.
'+' (ASCII 43 ) - у клітинці знаходиться хрестик.

'-' (ASCII 45 ) - у клітинці знаходиться нулик.

'?' (ASCII 63 ) - у клітинці знаходиться фігура, тип якої неможливо розпізнати (тобто в клітинці може знаходитися як хрестик, так і нулик).

Формат вихідних даних: Вихідний файл повинен складатися з N рядків по М символів у кожному - відновлене ігрове поле. Гарантується, що рішення завжди існує. Якщо існує декілька варіантів рішення, то виведіть будь-яке з них.

Оцінювання: 1 ≤ N, M ≤ 5 - 15 балів Ігрове поле містить тільки символи '?' i 'X' - 40 балів

Приклади вхідних та вихідних даних:

Input in game.in	Output in game.out
2 2 ?? ??	+- -+
3 4 +?XX ?X?X X??X	+-XX -X+X X+-X
6 4 X??X X?-X ?+?? -??? ?XX+ ?XX?	X-+X X+-X ++-- --++ -XX+ +XX-

Завдання ІІ туру

A.    Перевезення

Input file name:	transportation.in
Output file name:	transportation.out
Time limit:	100 ms
Memory limit:	256 M

З пункту A в пункт В необхідно перевезти X тонн вантажу, для чого в пункті A знаходяться 2 вантажівки. Перша вантажівка може везти V₁ тонн вантажу і долає шлях від A до B (або назад) за час T₁, другa, відповідно, V₂ тонн вантажу і за час T₂. За який мінімальний час вантажівки перевезуть вантаж в пункт B? Завантаження та розвантаження здійснюються тільки в кінцевих пунктах.

Вхідні дані: У єдиному рядку вхідного файлу знаходяться п'ять цілих чисел X, V₁, T₁, V₂, T₂ (1 ≤ X, V₁, T₁, V₂, T₂ ≤ 2³¹-1).

Вихідні дані: У єдиному рядку вихідного файлу виведіть одне число - мінімальний час, за який буде перевезено вантаж.

Приклад вхідних і вихідних даних:

transportation.in	transportation.out
10  2  3  5  4	12
100  2  3  5  4	105

B.     Підготовка до олімпіади

Input file name:	olympiad.in
Output file name:	olympiad.out
Time limit:	100 ms
Memory limit:	256 M

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

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

Нехай, наприклад, на 5 день стануть доступні чотири нові задачі. Тоді одну з них Степан розв’яже п’ятого дня, а розв’язання інших трьох перенесе на 6, 7 і 8 дні. А якщо виявиться, що на 7 день стане відкритою ще одна задача, то її розв’язанням олімпіадник займеться тільки 9 дня.

Напишіть програму, яка, знаючи кількість нових задач, що стануть доступним у кожен з наступних N днів, визначить, в які дні Степан працюватиме, а в які відпочиватиме.

Вхідні дані: У першому рядку записане одне ціле число N – кількість днів, про які відомо, як працюватиме сайт.

У другому рядку знаходяться N невід’ємних цілих чисел – для кожного дня вказано, скільки нових задач стане доступно на сайті в цей день.
Гарантується, що 1 ≤ N ≤ 100000, і що сума всіх чисел у другому рядку не перевищує 100000.

Вихідні дані: Виведіть один рядок, що складатиметься із символі «+» або «-». Символом «+» позначайте день, в який Степан розв’язуватиме задачу, а «-» – відпочиватиме. Виведіть як мінімум N символів – по одному на кожен день, про який відома робота сайту. Але якщо розв’язання задач доводиться переносити на дні після N-го (що дозволяється), то виведіть більшу кількість символів – до останнього дня, в який буде розв’язана задача. Символи розділяйте пропусками.

Приклад вхідних і вихідних даних:

olympiad.in	olympiad.out
5 0 3 0 0 0	- + + + -
10 0 4 0 2 0 0 0 0 1 0	- + + + + + + - + -
3 0 3 0	- + + +

C.    Спільний дільник

Input file name:	divisor.in
Output file name:	divisor.out
Time limit:	100 ms
Memory limit:	256 M

Степан вивчив на уроці математики найбільший спільний дільник двох чисел. Степан дуже талановитий хлопчик і відразу зрозумів, що до чого. Він моментально порахував найбільший спільний дільник чисел A і B. Вчителька математики одразу придумала для Степана нову задачу - для даних чисел A і B знайти таке додатне ціле число D, що A ділиться на D, B ділиться на D, а сума цифр числа D максимальна.
Допоможіть Степану знайти спільний дільник чисел A і B з найбільшою сумою цифр.

Вхідні дані: У єдиному рядку вхідного файлу знаходяться два цілих числа A, B (1 ≤ A, B ≤ 10⁹).

Вихідні дані: У єдиному рядку вихідного файлу виведіть спільний дільник чисел A і B з найбільшою сумою цифр. Якщо відповідей декілька, можете вивести будь-яку.

Приклад вхідних і вихідних даних:

divisor.in	divisor.out
10 20	5

D.    Щасливі квитки

Input file name:	tickets.in
Output file name:	tickets.out
Time limit:	100 ms
Memory limit:	256 M

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

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

Крім того, за повідомленнями кондукторів маршруток, серед пасажирів почалася боротьба за щасливі квитки. Правда, стандартні способи визначення "щасливості" квитка не працюють за нової системою номерів. Тому, спеціально за вказівкою Степана, кондуктори маршруток провели дослідження, яке показало, що пасажири придумали нове визначення щасливого квитка. А саме, якщо позначити числа, надруковані на квитку, як m(1), m(2), ..., m(N), то квиток щасливий тоді і тільки тоді, коли m(m(i)) = m(i) для кожного i від 1 до N.

Наприклад, при N=2 з 4 можливих квитків три є щасливими, і тільки квиток 2 1 - не щасливий (оскільки, наприклад, m(m(2))=m(1)=2 ≠ m(2)=1); при N=4, наприклад, квитки 1 1 3 1 і 1 2 3 4 є щасливими, а 2 2 2 3 - ні (оскільки, m(m(4))=m(3)=2 ≠ m(4)=3).

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

Вхідні дані: У першому рядку одне число N (1 ≤ N ≤ 30). 

Вихідні дані: Виведіть у вихідний файл одне число - кількість можливих щасливих квитків при даному N без ведучих нулів по модулю 10⁹+7.

Приклад вхідних і вихідних даних:

tickets.in	tickets.out
2	3

E.     Аквапарк

Input file name:	aquapark.in
Output file name:	aquapark.out
Time limit:	300 ms
Memory limit:	128 M

У новому аквапарку є N басейнів, заповнених водою. Деякі пари басейнів з'єднані трубами, всього М труб. Система труб збудована так, щоб з будь-якого басейна у будь-який інший можна було при потребі перегнати воду, можливо, скориставшись іншими басейнами як проміжними. На кожній трубі стоїть програмований насос, який здатний перекачувати у будь-який бік довільно заданий потік води. Крім того, в деякі басейни додатково тече вода з відомою швидкістю, а з деяких вода витікає - також з відомою швидкістю.

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

Формат вхідних даних: У першому рядку вказано кількість басейнів N (1 ≤ N ≤ 100). Далі йдуть N рядків, що містять інформацію про басейни. Для кожного басейну, починаючи з 1-го і закінчуючи N-им, вказана різниця між додатковим потоком, що тече до басейну і потоком, що витікає - ціле число, що не перевищує за модулем 30 000 (додатне число відповідає потоку що тече у басейн, від'ємне - потоку, що витікає).

На наступному рядку вхідного файлу знаходиться число труб M (0 ≤ M ≤ 4950). У наступних M рядках знаходиться опис труб: для кожної труби вказані два числа - номери басейнів, які труба з'єднує. Між кожною парою басейнів є не більше однієї труби, труби не можуть з'єднувати басейн з самим собою. 

Формат вихідних даних: Якщо рішення існує, виведіть у вихідний файл M рядків, по числу на рядок. Для кожної труби в тому ж порядку, як у вхідному файлі, має бути зазначено ціле число - потік води через неї. Додатним числом позначається потік від басейну, зазначеного першим у вхідному файлі, до другого; від'ємним - зворотний потік. Потоки у вихідному файлі не повинні перевищувати 2 000 000 000.

Якщо можливо кілька рішень, можна виводити будь-яке з них.

У разі, коли рішення не існує, вихідний файл повинен містити один рядок 'Impossible'.

Приклад вхідних і вихідних даних:

aquapark.in	aquapark.out
4 -100 -100 100 200 4 1 2 4 3 1 3 4 1	Impossible
4 -100 -100 100 100 4 1 2 4 3 1 3 4 1	100 0 -100 100