http://www.e-olimp.com.ua/ua/problems/857 

Опукла оболонка

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

Готуємось до олімпіади з інформатики (додаток 4)

Задача 1

Від’їжджаючи з домівки, поет залишив коту, прикутого до дуба ланцюгом довжиною L, N рибин. Знаючи координати голови та хвоста кожної з них, порахуйте, на яку добу у кота виникне почуття голоду, якщо він починає голодувати тоді, коли за добу з’їсть менше, ніж К рибин. Рибину кіт може з’їсти тільки тоді, коли зможе дотягнутися хоча б до однієї її точки. Координати дуба (0, 0). Усі числа цілі, не перевищують за модулем 100. (Автор задачі Присяжнюк А.В.)

Задач 2.

FOREST. Сергійко заблукав в лісі і вийти з нього він може тільки потрапивши на шосе, яке має вигляд нескінченної прямої, що задається рівнянням ax + by =1. В початковий момент часу Сергійко знаходиться в точці (х_о,у_о) і щоб остаточно не заблукати він вирішив йти по компасу в одному з чотирьох напрямків: "Північ", "Південь", "Захід" або "Схід". В довільний момент часу він може змінити напрямок руху на інший з вказаних чотирьох.

Осі координатної системи в умові задачі направлені по сторонам світу.

Необхідно допомогти Сергійку знайти найкоротший шлях від початкової точки до шосе.

Вхідні дані: Єдиний рядок вхідного файлу FOREST.DAT містить числа a, b, х_о та у_о. Всі числа цілі та знаходяться в межах від -1000 до 1000, a і b одночасно не дорівнюють 0.

Вихідні дані: Єдиний рядок вихідного файлу FOREST.SOL має містити довжину найкоротшого шляху з точністю до двох знаків після коми.

Задач 3

VIОLАТION. В деякому місті шоферам заборонено при русі робити ліві повороти. За кожен такий поворот шофер повинен сплачувати штраф в розмірі М гривень. Для спостереження за рухом транспорту в місті встановлена комп'ютерна система, яка фіксує координати автомобіля на початку руху, в кінці та при кожному повороті.

Необхідно по заданій послідовності координат руху обчислити суму штрафу.

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (х_i, у_i), і=1,2,...,М, де (х₁, у₁) - точка початку руху, (х_N,у_N) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані:Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

Задач 4.

 Вписаний трикутник

Дано опуклий N-кутник. Знайдіть площу максимального трикутника, який лежить всередині (або на межі) цього N-кутника.

Формат вхідних даних: у першому рядку записано число N – кількість вершин многокутника (3 ≤ N ≤ 2000). Далі йдуть N рядків, у кожному з яких записані два цілих числа, що не перевищують по модулю 10⁷ - координати вершини многокутника. Координати йдуть в порядку обходу многокутника або за часовою стрілкою, або проти.

Формат вихідних даних: виведіть площу знайденого трикутника з точністю до трьох знаків.

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

Задача 5.

Ім’я вхідного файлу: POINT.DAT

Ім’я вихідного файлу: POINT.SOL

Максимальний час роботи на одному тесті: 1с

Багатокутник (не обов'язково опуклий) на площині заданий координатами своїх вершин.Потрібно підрахувати кількість точок з цілочисельними координатами, що лежать всерединінього (але не на його межі).

Формат вхідних даних

У першому рядку міститься N (3 <= N <= 1000) - число вершин багатокутника. У наступнихN рядках йдуть координати (Xi, Yi) вершин багатокутника в порядку обходу за годинниковоюстрілкою. Xi і Yi - цілі числа, по модулю не перевищують 1000000.

Формат вихідних даних

У вихідний файл вивести одне число - шукану кількість точок.

Приклади:

Задача 6

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

Вхідні дані

В першому рядку знаходиться натуральне N (3<=N<=50) – число поселень. В наступних рядках координати кожного поселення X,Y, які записуються через пропуск. X,Y – цілі числа (-1000<=X<=1000; -1000<=Y<=1000).

Вихідні дані

В першому рядку Р, а в другому S. P i S – дійсні числа із виведеними двома розрядами після коми.

Задача 7

 „STARWAR“. Давним-давно, в одній далекій-далекій галактиці, Лукас Скайуокер разом із своїми товаришами вирішив штурмувати планету військ Імперії Корусант. І яка ж війна без карт? Зрозуміло, що Лукас з товаришами використав дроїдів, які склали N карт. Отже, мапи вже були, але все ще залишалась одна проблема: «Якими силами потрібно проводити штурм?» А для цього треба знати загальну площу, яку покривають карти повстанців. Тут Лукас з товаришами кинулись шукати людину, яка б допомогла їм... і знайшли Вас. Вам же ж потрібно допомогти Лукасу  та його товаришам і  скласти програму, яка знаходить загальну площу території, яку  штурмуватимуть друзі.

Формат вхідних даних:  У вхідному файлі  Corusant.DAT перший рядок містить єдине натуральне число N (1<=N<=10 000) – кількість карт, що має у розпорядженні Лукас. Кожен з наступних N рядків описує єдину карту і містить чотири цілих числа x₁, y₁, x₂,y₂ (0<=x₁<x₂<=30 000, 0<=y₁<y₂<=30 000). Значення (x₁, y₁) і (x₂,y₂) – координати, у вказаному порядку, лівого нижнього і правого верхнього кута карти. Кожна карта має форму прямокутника і її сторони паралельні до осей Декартової системи координат.

Формат вихідних даних: У вихідному файлі Corusant.SOL повинно міститися єдине ціле число – загальна площа, яку займають карти.

Наприклад:

2

10 10 20 20

 Задача 8

 “Зона досяжності”. Нещодавно на ринок операторів мобільного зв’язку вийшла нова компанія – NOVOTEL. Щоб відразу ж стати конкурентоспроможною, підприємство відразу ж намагається укласти контракти з органами місцевої влади на права встановлення своєї зони покриття. Компанія NOVOTEL встановлює сітку зв’язку в кожному місті за таких умов: оператор мобільного зв’язку зобов’язується надати зв’язок як мінімум K домівкам в певному місті, тобто, щоб K будинків були в зоні досяжності. Оскільки компанія NOVOTEL – дебютат на ринку зв’язку, то їх невеликий бюджет дозволяє встановити лише базову станцію стільникового зв’язку з певним радіусом дії сигналу на ній. При цьому економісти компанії наполягають, щоб гроші всіх акціонерів використовувалися найраціональнішим чином. І тому, оскільки кошторис робіт пропорційний величині зони покриття, яка встановлюється оператором, то, звичайно, підприємці дали директиву встановити базову станцію стільникового зв’язку так, щоб зона її покриття була найменш можливою, але неодмінно покривала щонайменше K домівок. (Дім вважається в зоні досяжності, якщо відстань від нього до базової станції стільникового зв’язку менша або рівна, ніж радіус досяжності станції передачі).

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

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

Формат вхідних даних: Перший рядок вхідного файла містить два цілих числа N і K (1<K<N<500), де – N кількість домівок у місті, а K – кількість домівок, які повинні бути забезпечені зв’язком. Тоді у наступних N рядках міститься по два цілих числа (X,Y) (0<X,Y<10000) координати домів.

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

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

  Наприклад:

Задача 9

Розділення многокутників http://www.e-olimp.com.ua/ua/problems/4518

   На площині задано дві фігури, що обмежені опуклими многокутниками. Фігури розташовані таким чином, що їх вершини не співпадають, а контури мають рівно 2 точки перетину.

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

   Наприклад, на рисунку зображена пряма, що задає певне розділення многокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D) + (C + E) та (A + D) + (B + C). З рисунку, D + C + E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D + C + E.

   Напишіть програму, яка за заданими двома многокутниками знаходить пряму, яка утворює розділення з найменшим дефектом.

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

   Вхідні дані

   Перший рядок містить одне ціле число N (3 ≤ N ≤ 20) - кількість вершин першого многокутника. Наступні N рядків містять пари цілих чисел – координати вершин першого многокутника у порядку обходу. (N + 2) -ий рядок файлу містить число M (3 ≤ M ≤ 20) - кількість вершин другого многокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого многокутника. Координати точок додатні і не перевищують 1000.

   Вихідні дані

   Вивести в одному рядку дві пари чисел - координати двох точок, які однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x₁ y₁ x₂ y₂. Координати потрібно виводити з точністю 10^-3. Координати точок повинні бути додатними і не перевищувати 1000.

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за тест: 4.7619
Автор: Богдан Рубльов,Тарас Галковський
Джерело: 2007 XX Всеукраїнська олімпіада з інформатики, Кременчук, Квітень 10 - 16, тур 2

Приклад

Тематика задач

Зміст

Тема: Сортування

Тема: Формула (рекурентна, загального елемента)

Тема: Повний перебір

Тема: Обчислювальна геометрія

Тема: Теорія графів

Тема: Динамічне програмування

Тема: Жадібні алгоритми

Тема: Робота з рядками (синтаксичний і лексичний розбір виразів)

Тема: Дерева (бінарні, остові)

Тема: Сортування

XXI Всеукраїнська олімпіада з інформатики (2008)

Другий тур

Знижки

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

1. При купівлі трьох товарів ви платите за них як за два найдорожчих з них.

2. При купівлі чотирьох товарів ви платите за них як за три найдорожчих з них.

Таким чином, певні товари можна об’єднати у трійки або четвірки і заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків.Наприклад, якщо ціни п’яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна окремо придбати чотири перших товари, отримати за них знижку, та потім купити подарунок, що залишився за його номінальну ціну. Загалом вся покупка буде коштувати 250 грошових одиниць, замість 300.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DISCOUNT.DAT містить одне ціле число N (0≤N≤10 000). Другий рядок містить N натуральних чисел – ціни подарунків. Сума цін усіх подарунків менша за 10⁹. Об’єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.

Вихідні дані

Єдиний рядок вихідного файлу DISCOUNT.SOL має містити одне ціле число – знайдену мінімальну суму грошей, за яку можна купити усі подарунки.

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

Тема: Формула (рекурентна, загального елемента)

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

Перший тур

Гірлянда

Новорічну ялинку прикрашено гірляндою нескінченної довжини, що складається з послідовно з'єднаних лампочок. Коли гірлянду вмикають, загоряється лише першалампочка, рахуючи від вимикача, яка горить одну секунду. Далі гірлянда починає мигати за таким правилом. Щосекунди для кожної лампочки перевіряється умова: якщо рівно одна із її сусідніх лампочок горить, тоця лампочка буде горіти на наступній секунді; інакше – не буде горіти. Перша лампочка має лише одну сусідню.

Завдання

Напишіть програму GARLAND, яка за номером секунди знаходить кількість лампочок гірлянди, що будуть горіти протягом цієї секунди.

Вхідні дані

Єдиний рядок вхідного файлу GARLAND.DAT містить одне ціле число N (1≤N≤10⁹) – номер секунди.

Вихідні дані

Єдиний рядок вихідного файлу GARLAND.SOL має містити ціле число – кількість лампочок, що будуть горіти на секунді N.

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

Тема: Повний перебір

Щасливий білет

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

$11.     Спочатку номер розбивають на цифри, та певні сусідні цифри об’єднують у числа.

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

$13.     Неможна міняти місцями цифри.

$14.     Якщо вдається скласти такий вираз, який після обчислення дорівнюватиме шуканому числу k, то білет вважається щасливим.

Операцію «розділити» можна використовувати тільки у випадках, коли в наслідок ділення буде отримано ціле число.

                Наприклад, розглянемо білет номер: 182836. Візьмемо k=840. Розіб’ємо число на чотири: 1, 8, 2, 836. Число k можна отримати, наприклад, таким чином: 1*(8/2+836)=840.

Завдання

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

Вхідні дані

Єдиний рядок вхідного файлу LUCKY.DAT містить два числа: ціле k (1≤k≤1000) та номер білету. Номер білету складається з шести цифр, та може починатися з 0.

Вихідні дані

Єдиний рядок вихідного файлу LUCKY.SOL повинен містити будь-який з можливих наборів чисел на які може бути розбитий номер білету для отримання числа k. Якщо число не може бути отримане, то єдиний рядок вихідного файлу повинен містити число 0 (нуль).

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

Тема: Обчислювальна геометрія

Відстань

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

Завдання

Напишіть програму DIST, що за переліком точок площини обчислює максимальну відстань від точки до прямої.

Вхідні дані

Перший рядок вхідного файлу DIST.DAT містить єдине ціле число – кількість точок N
(3≤N≤700) заданих на площині. Далі йдуть N рядків, кожен з яких задає точку площини у форматі “x y” (-5000≤x, y≤5000), x та y – цілі числа. Жодні дві точки не мають однакових координат.

Вихідні дані

Єдиний рядок вихідного файлу DIST.SOL повинен містити найбільшу відстань від однієї з заданих точок, до прямої побудованої на двох інших точках, з точністю до 10^-6. Відповідь повинна бути записана у форматі з точкою (<ціла частина>.<дрібна частина>)

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

Розділення багатокутників

На площині задано дві фігури, що обмежені опуклими багатокутниками. Фігури розташовані таким чином, що їх вершини не співпадають, а контури мають рівно 2 точки перетину.

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

Наприклад, на рисунку зображена пряма, що задає певне розділення багатокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D)+(C+E) та (A+D)+(B+C). З рисунку, D+C+E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D+C+E.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DIVIDE.DAT містить одне ціле число N (3≤N≤20) – кількість вершин першого багатокутника. Наступні Nрядків містять пари цілих чисел – координати вершин першого багатокутника у порядку обходу. (N+2)-й рядок файлу містить число M (3≤M≤20) – кількість вершин другого багатокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого багатокутника. Координати точок додатні та не перевищують 1000.

Вихідні дані

Єдиний рядок вихідного файлу DIVIDE.SOL має містити дві пари чисел – координат двох точок, що однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x₁ y₁ x₂ y₂. Координати потрібно виводити з точністю 10^-3. Координати точок мають бути додатні та не більші за 1000. 

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

Тема: Теорія графів

Робочий стіл

На робочому столі операційної системи розташовано N ярликів, кожен з яких заданий цілими координатами x та y, а також назвою. Назва ярлику складається з маленьких символів латинського алфавіту (a-z). Необхідно перейти (тобто перемістити виділення) з виділеного ярлика S до ярлика F, за допомогою клавіатури, використавши найменшу можливу кількість натискань. Перехід здійснюється за допомогою натискань на клавіші з літерами a-z, або на стрілки “↑”,“↓”,“←” та “→”.

При натисканні на клавіші з літерами перехід відбувається за такими правилами:

$11.     Якщо на робочому столі є ярлики, назва яких починається на натиснуту літеру, та виділено однин з них, то перехід відбувається на ярлик, з назвою наступною у лексикографічному порядку серед тих, які починаються на цю букву (після останнього, виділення переходить на перший). Тобто, якщо є ярлики a, ab, b, то при натисканні a виділення буде переходити лише між aта ab.

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

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

При натисканні на стрілку перехід відбувається на найближчий у звичайному геометричному розумінні ярлик, що лежить в секторі стрілки. Визначимо сектор стрілки як прямий кут з вершиною у виділеному ярлику, бісектрисою якого є промінь, що відповідає стрілці. Якщо ярлик лежить на границі сектору, то він відноситься до верхнього або нижнього сектору (а не до лівого, або правого). Якщо у певному секторі немає жодного ярлику, то перехід не відбувається. Якщо найближчих ярликів декілька, то обирається ярлик з найменшою x координатою, а якщо і таких декілька, то обирається з найменшою y-координатою.

Наприклад, якщо виділено ярлик a (див. рисунок), то при натисканні стрілок можуть відбутись такі переходи:

$11.      Стрілка “←”. Виділення переходить на ярлик b, оскільки він є найближчим у секторі цієї стрілки. При наступному натисканні “←” виділення перейде на c.

$12.      Стрілка “↑”. В секторі стрілки знаходяться ярлики d та e. Виділення перейде на d – цей ярлик ближче.

$13.      Стрілка “→”. В секторі “→” знаходиться тільки ярлик g, який і буде виділено.

$14.      Стрілка “↓”. В цьому секторі знаходяться ярлики f та h, які рівновіддалені від a. Виділення переходить на ярлик h, оскільки x-координата цього ярлика менша. Якщо після цього натиснути “↓”, то виділення залишається на h,оскільки у секторі знизу немає жодного ярлику.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DESKTOP.DAT містить три цілих числа N (1≤N≤1000) – кількість ярликів на робочому столі, S (1≤S≤N) – номер обраного ярлика, F (1≤F≤N) – номер ярлика на який потрібно перейти. Кожен з наступних N рядків задає окремий ярлик у такому форматі «x y text», x,y – цілі числа  (0≤x, y≤10⁶), а текст складається з не більш ніж 50, та не менше ніж з одного маленького символу латинського алфавіту a-z.

                Жодні два ярлика не мають однакових координат, або ж однакових назв. Координатна сітка – стандартна, тобто “↑” збільшується y-координата, а “→” x-координата.

Вихідні дані

Єдиний рядок вихідного файлу DESKTOP.SOL має містити одне ціле число – мінімальну кількість натискань на клавіатуру що дозволять перейти з ярлика S до ярлика F.

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

Острови

Аби не відставати від сучасної світової тенденції, уряд країни Олімпія планує побудувати декілька островів для залучення туристів. Карта островів вже підготовлената являє собою таблицю розміром N´Mклітинок. Кожна клітинка може бути водою або сушею. Набір клітинок, що представляють сушу, є островом, коли з будь-якої з них можна потрапити в будь-яку іншу, переміщуючись сусідніми по горизонталі або вертикалі клітинами, та не існує інших таких клітин поза набором.

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

Завдання

Напишіть програму ISLANDS, що за картою островів знаходить мінімальну вартість будівництва групи мостів, що з’єднують всі острови.

Вхідні дані

Перший рядок вхідного файлу ISLANDS.DAT містить два цілих числа N та M (1≤N, M≤500) – розміри карти островів. Кожен з наступних N рядківмістить Mсимволів 0 (вода) або 1 (суша).

Вихідні дані

Єдиний рядок вихідного файлу ISLANDS.SOL має містити одне ціле число – знайдену мінімальну вартість будівництва мостів. Якщо сполучити острова мостами неможливо, потрібно вивести число -1.

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

Тема: Динамічне програмування

Альтернативні шляхи (100  балів)

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

Будемо поблажливими до Мандрівника, і вважатимемо «гарними» не лише шляхи, на котрих в точності досягається максимально можлива сума, а ще й шляхи, сума котрих відрізняється від макси­маль­ної не більше ніж на K.

Кількість «гарних» шляхів гарантовано не перевищує 10⁹.

Завдання

Напишіть програму GOODWAYS, що знаходить значення макси­ма­льно можливої суми та кількість «гарних» шляхів.

Вхідні дані

Перший рядок вхідного файлу GOODWAYS.DAT містить три цілих числа M (2≤M≤200), N (2≤N≤200) та K (0≤K≤200). Кожен з наступних Mрядків містить N чисел, записаних у відповідних клітинках.

Вихідні дані

Перший рядок вихідного файлу GOODWAYS.SOL має містити максимальну можливу суму; другий рядок – кількість маршрутів, сума чисел котрих відрізняється від максимальної не більш ніж на K.

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

Тема: Жадібні алгоритми

Доставка

Місто Прямий Ріг являє собою одну пряму вулицю. У місті працює компанія, що займається доставкою товарів. Для зручності, адреси доставки надані у вигляді чисел, що задають відстань від офісу компанії. Додатні числа в один бік, а від’ємні – в інший. Замовлення на доставку виконуються компанією послідовно, у тому порядку, в якому вони були задані.

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

Завдання

Напишіть програму ORDER, що за відстанями адресатів від офісу компанії знаходить найменшу сумарну відстань, що пройдуть її робітники.

Вхідні дані

Перший рядок вхідного файлу ORDER.DAT містить ціле число N (1≤N≤100000) – кількість замовлень. Далі слідує N рядків, кожен з яких містить єдине ціле число – відстань від офісу до адресата. Якщо відстань додатня – то адресат знаходиться у одній частині міста відносно офісу компанії, а якщо від’ємна, то у іншій. Відстані за модулем не перевищують 10⁸.

Вихідні дані

Єдиний рядок вихідного файлу ORDER.SOL має містити одне ціле число, яке є мінімальною можливою сумарною відстанню, що пройдуть обидва робітники компанії.

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

Тема: Робота з рядками (синтаксичний і лексичний розбір виразів)

Пошук рядку

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

Завдання

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

Вхідні дані

Вхідний файл SUBSTR.DAT містить послідовність, яка, для зручності, розбита на декілька рядків. Кожен рядок містить не більше 100 символів. Загальна довжина послідовності – не більше 10000 000символів.

Вихідні дані

Єдиний рядок вихідного файлу SUBSTR.SOL має містити першу з підпослідовностей найбільшої довжини, що не містить однакових символів.

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

Тема: Дерева (бінарні, остові)

Катакомби

Піратські катакомби на острові Скарбів було вирито за таким принципом. Після прихованого входу розташована печера, з якої виходять два тунелі – наліво і направо. Кожен із тунелів закінчується печерою, з якої також виходить два тунелі, і т.д. Довжина кожного тунелю рівна одиниці. Кінцеві печери, що знаходяться на відстані D від входу, не мають подальших виходів. Ніякі тунелі між собою не перетинаються, та не ведуть до одної печери. Число D називають глибиною катакомб.

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

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

Завдання

За наданими вхідними файлами, що містять опис печери зі скарбами, створіть відповідні вихідні файли, що містять мінімальну сумарну відстань, яку піратам доведеться нести сундуки, та послідовність обмінів.

Вхідні дані

Вам надано 10 вхідних файлів, що мають назви CATACOMB.D01, CATACOMB.D02,…, CATACOMB.D10, у такому форматі. Перший рядок містить одне ціле число D– глибину катакомб. Другий рядок містить 2^D різних цілих чисел від 1 до 2^D. Кожне i-те з них ідентифікує номер печери до якої повинен попасти сундук, що находиться спочатку у печері i.

Вихідні дані

Створіть 10 файлів CATACOMB.S01,…, CATACOMB.S10. Ці файли повинні містити відповіді для відповідних вхідних файлів. Перший рядок файлу має містити єдине ціле число – мінімальну сумарну відстань, яку пройдуть пірати зі скарбами. Другий рядок: ціле число K – відповідна кількість обмінів. Кожен наступний з K рядків: два числа, що є номерами печер, між якими відбувається обмін. Обміни повинні бути вказані у тому порядку, в якому вони мають відбуватися.

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

Наприклад, можна проводити обміни таким чином. Спочатку поміняти місцями скарби у печерах 3 та 4. Пройдена відстань 4 (по 2 для кожного сундука). Потім поміняти скарби у печерах 4 і 1, та 3 і 2. Відстань в обох випадках – 8. Таким чином – усі встануть на свої місця, а сумарна відстань буде 20.

10-11 класи

1. Приготування яєць. Петя любить їсти варені яйця. Для того, щоб приготувати яйце некруто потрібно варити його Х хвилин. Щоб приготувати яйце круто, потрібно спочатку приготувати його некруто, а потім варити ще Y хвилин. Петя любить їсти яйце, коли воно наполовину приготовлено круто, тобто коли яйце спочатку приготовлено некруто, а потім ще пройшла половина часу, необхідного для того, щоб це яйце стало приготованим круто. Знайдіть скільки хвилин Петі потрібно варити яйце.

У єдиному рядку задаються два цілих числа Х і У (1 ≤ Х, У <10¹⁸).

Виведіть одне число - час у хвилинах, необхідне для приготування наполовину крутого яйця.

2. Годинник. Є свідчення N годин. Відомо, що До з них показують неправильний час, показання інших - вірні. Потрібно написати програму для визначення точного часу.

У першому рядку задається два цілих числа N і К (0 <К GNG 1000). У кожному з наступних N рядків задаються по два числа - кількість годин (від 0 до 23) і хвилин (від 0 до 59), які показують відповідні години.

Виведіть два числа, що визначають правильний час у годинах і хвилинах. Якщо неможливе можна однозначно визначити точний час, виведіть одне число -1.

З. Транспортна задача. У країні Інформландія є всього два види міського транспорту: метро і автобус. Грошова одиниця в Інформландіі - природно, біт. Одна поїздка на метро коштує 3 біта, а на автобусі - 2 біти. При цьому можна купити місячний проїзний на необмежену кількість поїздок: на метро - 40 бітів, на автобус - 30 бітів, на автобус і метро - 60 бітів. Яку найменшу суму потрібно витратити на проїзд у місяць жителю Інформландіі, якщо в тому місяці належить зробити х поїздок на метро і у на автобусі.

У єдиному рядку задаються два цілих числа х і у (0 <х, у <100).

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

4. Морозиво. Є N морозив. Дитина з'їдає будь морозиво за 1 хвилину. Для кожного морозива відомо, через скільки хвилин воно розтане. Потрібно визначити мінімальну кількість дітей, які можуть з'їсти ці всі ці морозива так, щоб ні одне з них не встигло розтанути. Кожну хвилину одна дитина може їсти лише одне морозиво, і кожне морозиво може їсти лише одна дитина.

У першому рядку задано ціле число N (1 ≤N ≤ 10⁵). Другий рядок містить N натуральних чисел, що не перевищують 10⁶, кожне з яких визначає час, через який розтане відповідне морозиво.

Виведіть одне число - мінімальну кількість дітей, які зможуть з'їсти все морожені, не допустивши їх танення.

5. Ліфт. У будівлі з N поверхами поставили новий ліфт, який необхідно перевірити ліфтерові. За посадової інструкції перевірка працездатності ліфта полягає в тому, щоб зробити принаймні по одному разу поїздки між кожною парою різних поверхів (при цьому поїздки від одного поверху до іншого і у зворотний бік вважаються різними). Спочатку ліфт знаходиться на першому поверсі. Далі ліфтер послідовно натискає кнопки на панелі ліфта, переміщаючи ліфт на відповідні кнопкам поверхи. Працівник хоче впоратися з перевіркою якомога швидше, тому просить вас написати програму для знаходження послідовності натискань на кнопки мінімальної довжини.

У єдиному рядку задано ціле число N (1≤N≤1000).

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

Зауваження. При виконанні наведеної в прикладі послідовності натискань ліфт здійснить такі поїздки: {(1 - + 3), (3 - + 2), (2 - + 3), (3 - + 1), (1 - + 2), (2 - + 1)}, що є достатнім для перевірки, оскільки містить в собі всі можливі поїздки.

ІІIетапВсеукраїнськоїучнівськоїолімпіадизінформатики(м.Луцьк) 2013-2014н.р

http://www.e-olimp.com.ua/problems/7234

http://www.e-olimp.com.ua/ua/problems/7235

http://www.e-olimp.com.ua/ua/problems/7236

http://www.e-olimp.com.ua/ua/problems/7237

http://www.e-olimp.com.ua/ua/problems/7238

http://www.e-olimp.com.ua/ua/problems/7239

http://www.e-olimp.com.ua/ua/problems/7240

http://www.e-olimp.com.ua/ua/problems/7241

http://www.e-olimp.com.ua/ua/problems/7242

http://www.e-olimp.com.ua/ua/problems/7243

Матеріали IІІетапуВсеукраїнськоїучнівськоїолімпіадизінформатики 2013-2014

A. Кондиціонер Степана

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

Кондиціонер може працювати в наступних чотирьох режимах:

- «freeze» - охолодження. У цьому режимі кондиціонер може тільки зменшувати температуру. Якщо температура в кімнаті і так не більше бажаної, то він вимикається.

- «heat» - нагрів. У цьому режимі кондиціонер може тільки збільшувати температуру. Якщо температура в кімнаті і так не менше бажаної, то він вимикається.

- «auto» - автоматичний режим. У цьому режимі кондиціонер може як збільшувати, так і зменшувати температуру в кімнаті до бажаної.

- «fan» - вентиляція. У цьому режимі кондиціонер здійснює тільки вентиляцію повітря і не змінює температуру в кімнаті.

Кондиціонер досить потужний, тому при налаштуванні на правильний режим роботи він за годину доводить температуру в кімнаті до бажаної.

Потрібно написати програму, яка по заданій температурі в кімнаті t_room, встановленим на кондиціонері бажаної температурі t_cond і режиму роботи визначає температуру, яка встановиться в кімнаті через годину.

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа t_room, і t_cond, розділених рівно одним пропуском (-50 ≤ t_room ≤ 50 , -50 ≤ t_cond ≤ 50).
Другий рядок містить одне слово, записане малими літерами латинського алфавіту - режим роботи кондиціонера. 

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

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

У першому прикладі кондиціонер знаходиться в режимі нагріву. Через годину він нагріє кімнату до бажаної температури в 20 градусів.

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

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

B. "Поле чудес"

Степан пройшов до суперфіналу новорічного шоу "Поле чудес". На відміну від звичайних ігор новорічна відрізняється тим, що проводиться не за круглим барабаном, а на прямокутному полі, розбитому на квадратики. Кожен такий квадратик містить одне число (числа можуть бути як доданими, так і від'ємними). Гравець розташовується у верхній лівій клітинці і може переміщуватись у три сусідніх клітинки: праву, нижню та праву нижню по діагоналі (див. малюнок) і повинен потрапити до правої нижньої клітинки.  

Звісно, що Степан має бажання виграти гру і набрати якомога більше балів. Якщо набрана сума додатна, то Степан виграв, інакше програв.

Напишіть програму, яка доможе Степану визначити програє чи виграє він у грі і яку суму він зможе набрати.

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

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

Формат вихідних даних:Перший рядок вихідного файлу має містити одне слово - winner, якщо Степан виграв гру, або loser - в іншому випадку.

Другий рядок має містити одне число - набрану суму.

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

C. Winter

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

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

Формат вхідних даних: В першому рядку записано два числа N і M (1 ≤ N ≤ 100000,0 ≤ M ≤ 200000)– кількість міст в Ужляндії та кількість не заблокованих доріг відповідно. В наступних M рядках записано по два числа i та j (1 ≤ i,j ≤ N), що значить дорога між містами з номерами i та j не заблокована. Міста в Ужляндії нумеруються в 1 до N.

Формат вихідних даних:В єдиному рядку виведіть мінімальну кількість приземлень гвинтокрила.

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

Міста 1, 2 та 3 з’єднані між собою, а тому щоби забезпечити їх обігрівачами, необхідно здійснити одне приземлення в одному з цих міст, далі обігрівачі доставлять вантажівками. Міста 4 та 5 зв’язані між собою, тому треба ще одне приземлення. І нарешті місто 6, яке ізольоване від інших, щоби доставити обігрівачі в це місто, треба окреме приземлення гвинтокрила. Всього виходить 3 приземлення.

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

D. Гарні числа

Школа №1331 в Ужляндії відома дуже високим рівнем знань своїх учнів з математики, тому що більшість учнів відвідують факультативні заняття відомого вчителя Антона Андрійовича.

Сьогодні Антон Андрійович розказав своїм учням про числа, які, на його думку, можуть володіти рядом цікавих властивостей. Він назвав такі числа гарними. Число називається гарним, якщо не існує такого цілого числа, більшого одиниці, на квадрат якого воно б ділилося без залишку. Наприклад, число 12 не є гарним, тому що воно ділиться на 4, тобто на квадрат числа 2. Числа 13 і 14 є гарними числами.

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

Однак, Марися, краща його учениця, швидко впоралась з цим завданням. Щоб якось її зайняти, вчитель написав на дошці N чисел і дав їй нове завдання : визначити, чи є добуток цих чисел гарним числом. Дуже скоро Марися отримала відповідь, однак вона хоче перевірити себе. Тому вона просить Вас написати програму, яка перевіряє: чи є добуток чисел гарним числом, а якщо ні, то їй потрібно знати яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток цих чисел.

Формат вхідних даних:Перший рядок вхідного файлу містить число N (1 ≤ N ≤ 100) - кількість чисел, які вчитель написав на дошці для Марисі. Другий рядок містить N натуральних чисел - самі числа. Кожне з чисел не перевершує 10¹⁸.

Формат вихідних даних:Якщо число є гарним, виведіть єдиний рядок, що складається з слова Beautiful. Інакше, виведіть яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток N чисел.

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

Перший приклад: 5*6*7 = 210. Не існує числа, більшого за одиницю, на квадрат якого 210 ділилось би без залишку, тому 210 - гарне число.

Другий приклад: 35*12 = 420. 420 ділиться на 4, тобто на квадрат числа 2. 

Оцінювання:

A₁ * A₂ * ... * A_N ≤ 10⁶ – неменше 20 балів

A₁ * A₂ * ... * A_N ≤ 10¹² – не менше 40 балів

Для усіх і: A_i ≤ 10¹² – не менше 60 балів

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

Якщо жодна з умов не виконується, потрібно вивести “Beautiful”.

E. Вправи Степана

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

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

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

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

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

Формат вхідних даних:Перший рядок вхідного файлу містить єдине ціле число N (1 ≤ N ≤ 10⁵) - кількість днів тренувань.

Другий рядок містить два цілих числа T, D (1 ≤ T ≤ 10⁶, 1 ≤ D ≤ 10⁵), якщо в якийсь день Степан виконає вправу більш T разів, то йому доведеться відпочивати D наступних днів.
Наступні N рядків описують вправи, i+2-ий рядок містить опис вправи в день i. Кожна вправа описується числами A_i, B_i, K_i, F_i, (0 ≤ K_i ≤ 10⁹, 1 ≤ A_i ≤ B_i ≤ 10⁶, 1 ≤ F_i ≤ 10⁶), розділеними одиночними пробілами, - де A_i, B_i відповідно рекомендований мінімум і максимум кількості разів виконання вправи, K_i-кількість втрачаються рівнів сили при вивченні вправи, F_i- кількість рівнів сили, одержуваних за кожен раз виконання вправи.

Формат вихідних даних:Перший рядок вихідного файлу має містити одне ціле число S - максимальний рівень сили, який Степан може досягти до кінця тренувань.
Наступний рядок повинен містити N цілих чисел X_i - кількість разів виконання вправи в день і, якщо в і-ий день він відпочивав, то виведіть 0.

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

Щоб досягти максимального рівня сили, треба в перший день виконувати вправу 4 рази, щоб не довелося пропускати наступний день. У другий день Афанасій зможе збільшити свій рівень ще на 790 (втрачає 10 рівнів при вивченні та виконує вправу 8 разів), але тоді він не зможе займатися 1 день (третій день).

У четвертий день він збільшує свій рівень на 48, так як Степан виконав вправу більше 4 разів, він змушений пропустити п'ятий.

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

A. "Все, Степан! Ти мене дістав!"

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок "три - чотири" хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час t₁, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робе те ж саме за час t₂.

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

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

Наприклад, якщо t₁ = 2, t₂ = 3, то буде відбуватись наступне:

Степан надуває бульбашку з моменту часу t = 0 до моменту часу t = 2, потім бульбашка лопається, і він надуває бульбашку заново - з моменту часу t = 2 до моменту часу t = 4, а потім ще раз - з моменту часу t = 4 до t = 6. 

Товариш Степана надуває бульбашку з t = 0 до t = 3 і ще раз з t = 3 до t = 6.

В момент часу t = 6 бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: "Все, Степан! Ти мене дістав!".

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа t₁, t₂ (1 ≤ t₁, t₂ ≤ 10⁹).

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

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

B. Степан - бізнесмен

Ужляндія, як відомо, країна з розвиненими торговими відносинами.

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

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

Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас - кращому програмісту Ужляндії.

Формат вхідних даних:Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа N, M (1 ≤ N, M ≤ 10⁵) - кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
Другий рядок містить N цілих чисел A_i (0 ≤ A_i ≤ 10⁹) - вартості, за якими продавці готові продавати комп'ютери.
Третій рядок містить M цілих чисел B_i (0 ≤ B_i ≤ 10⁹) - суми, які потенційні покупці готові віддати при покупці комп'ютера.

Формат вихідних даних:Перший рядок вихідного файлу має містити одне ціле число S - розмір максимальної вигоди в монетах, яку може отримати Степан.

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

У першому прикладі Степан купує комп'ютери у 1-го і 2-го продавців і продає їх будь-яким двом покупцям.
У другому прикладі Степану найбільш вигідно купити комп'ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям. 

Оцінювання:

N + M ≤ 20, для усіхі: A_i, B_j≤ 1000– не менше 40 балів

N + M ≤ 2000, для усіхі: A_i, B_j≤ 1000– не менше 50 балів

N + M ≤ 2000– не менше 75 балів

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

C. Transit

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

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі N днів. Згідно з новим договором має обратися певне число m – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує A_i обігрівачів, буде відвантажено рівно A_i-m одиниць іноземної продукції (звичайно, якщо A_i > m, інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за N днів обігрівачів повинна бути не менша K, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із N днів (ця інформація надається за умовами контракту). Знайдіть максимальне число m, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних:В першому рядку записано два числа N, K (1 ≤ N ≤ 10⁶, 1 ≤ K ≤ 2*10⁹). В наступному рядку задано N чисел – кількість обігрівачів у потязі в кожен з N днів, що не перевищує 10⁹.

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

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

Всього територією Ужляндії пройде 4 потяги з 11, 6, 1 та 8 обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше 7 обігрівачів. Очевидно, що максимальне можливе m, яке задовольнить цю умову, буде рівне 6, тоді з потягів буде відвантажено відповідно 5, 0, 0, 2 обігрівачів, що в сумі дорівнює 7 і задовольняє умову.

Оцінювання:

N ≤ 300 – не менше 20 балів

N ≤10000 – не менше 40 балів

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

D. Дорожня система Ужляндії

Велика і прекрасна країна Ужляндія! Вона складається з N міст, пронумерованих від 1 до N, і M доріг між ними. Кожна дорога пов'язує між собою два різних міста та забезпечує пересування між ними. Дорожня система в Ужляндії вельми специфічна. Всі дороги мають двосторонній рух, і між кожною парою міст проходить не більше однієї дороги.

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

Скінчену послідовність номерів міст C₁,..., C_K(K ≥ 2)будемо називатишляхом, якщо для будь-якої сусідньої пари елементів послідовність C_i, C_i+1(C_i ≠ C_i+1, для 1 ≤ i < K)існує дорога між містами з номерами C_i C_i+1. Якщо C₁= C_K, то такий шлях будемо називати замкнутим. Довжину шляху C₁, ..., C_Kбудемо вважати рівною довжині послідовності, тобто рівній K. Отже, правилонепарностіговорить,що всі замкнуті шляхи в Ужляндії мають непарну довжину, тобто не існує замкнутого шляху парної довжини.

Дорожня мережа, зображена на рисунку №1, має властивість непарності, а дорожня система на рисунку №2 не володіє цією властивістю через наявність у ній замкнутого шляху парної довжини 4: 1 2 4 1.

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

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

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

Формат вхідних даних: Перший рядок вхідного файлу містить цілі числа N (1 ≤ N ≤ 10 000)і M (0 ≤ M ≤ 100000). Наступні M рядків описують дороги Ужляндії. У кожному рядку знаходиться опис рівно однієї дороги. Кожна дорога описується двома цілими числами X і Y (1 ≤ X, Y ≤ N, X ≠ Y). Ці числа відповідають номерам міст, зв'язаних дорогою. Міста нумеруються послідовно цілими числами від 1 до N.

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

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

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

Дорожня мережа з першого прикладу приведена на малюнку № 1. Задана дорожня мережа з другого прикладу представлена н​​малюнку №3, а її стан після додавання до неї нових доріг зображено на малюнку №4.

У другому прикладі можна добавити 5 нових доріг: 2 5, 1 4, 1 6, 3 4, 3 6. 

Оцінювання:

M = 0 – не менше 20 балів

N ≤ 10, M > 0 – не менше 20 балів

N ≤ 100, M > 0 – не менше 40 балів

N ≤ 1000, M > 0 – не менше 60 балів

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

E. Відео-кафе Ужляндії

Як відомо, чемпіонат світу з хокею в 2014 році пройде в Ужляндії. Для успішного проведення заходу приймаючій стороні належить виконати ряд вимог, що пред'являються Міжнародної хокейної федерацією. Хокейні матчі планується провести в м.Ужкачево та м.Ужковель (в Ужляндіїї усі міста починаються на Уж). Дані міста пов'язані між собою прямою автомагістраллю Ужкачево - Ужковель.

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

1. Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе іпопереднімна автомагістралі відео-кафе (якщо таке є) повинно бути не меншеАкм і не більшеВкм.

2. Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе і наступним на автомагістралі відео-кафе (якщо таке є) повинно бути не менше А км і не більше В км.

3. Відстань від м.Ужкачево та м.Ужковель до найближчого відео-кафе не повинно бути менше А км і не більше В км.
 
Рисунок до прикладу №1: N=5, K=3, A=20, B=70.

Для кожного i-го побудованого відео-кафе введемо коефіцієнт Z_i - відстань від даного відео-кафе до всіх інших. Міжнародна хокейна федерація встановила, що чим більша сума коефіцієнтів Z_i, тим cвоєчасніше мандрівники зможуть отримувати інформацію про проведення хокейних матчів.

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

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

Другий рядок вхідного файлу містить два цілих числа A, B (1 ≤ A < B ≤ 10⁹).
Третій рядок вхідного файлу містить одне ціле число S (1 ≤ S ≤ 10⁹) - відстань між м.Ужкачево та м.Ужковель.
Четвертий рядок вхідного файлу містить N цілих чисел C_i (0 < C_i < S, C_i < C_j якщо i < j) - відстань i-го кемпінгу від м.Ужкачево.

Формат вихідних даних:Вихідний файл повинен містити одне ціле число - максимальну суму коефіцієнтів Z_i побудови K відео-кафе. Рішення завжди існує.

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

У першому прикладі кемпінги {1, 2, 4} 

У другому прикладі кемпінги {2, 5, 8, 10}. 

Оцінювання:

K ≤ 2 – не менше 15 балів

N^K ≤ 10⁶ – не менше 30 балів

N ≤ 50 – не менше 45 балів

N ≤ 300 – не менше 60 балів

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

Матеріали IІІетапуВсеукраїнськоїучнівськоїолімпіадизінформатики 2012-2013

http://www.e-olimp.com.ua/ua/problems/4281

http://www.e-olimp.com.ua/ua/problems/4282

http://www.e-olimp.com.ua/ua/problems/4283

http://www.e-olimp.com.ua/ua/problems/4284

http://www.e-olimp.com.ua/ua/problems/4285

http://www.e-olimp.com.ua/ua/problems/4286

http://www.e-olimp.com.ua/ua/problems/4287

http://www.e-olimp.com.ua/ua/problems/4288

http://www.e-olimp.com.ua/ua/problems/4289

http://www.e-olimp.com.ua/ua/problems/4250

А  - Неуважність

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

Формат вхідних даних: перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.

Формат вихідних даних: вихідний файл має містити виправлений текст.

Приклади

sCHOOL

School

B - День святого Валентина

Скоро день святого Валентина і, Степану як великому прихильнику даного свята, доручили вибрати кульки для прикраси зали. Профорг університету, де навчається Степан, веде строгий перелік усіх кульок, згідно якому в наявності є N однокольорових (що поробиш – бідні студенти) кульок, діаметр i-ї кульки (1 ≤ i ≤ N) дорівнює Di міліметрів. Згідно новим вимогам профкому, залу необхідно прикрасити не менше ніж K кульками. Оскільки профоргу університету не подобається свято закоханих, то вона ввела своє поняття – так званий показник некрасивості – рівний максимально можливому числу Di – Dj при 1 ≤ i, j ≤ M, де M – кількість кульок для зали, а Di – їх діаметр. Допоможіть Степану із N іграшок вибрати М (M ≥ K) так, щоб для вибраних M кульок показник некрасивості був мінімальним.

Формат вхідних даних: перший рядок вхідного файлу містить два натуральних числа N (2 ≤ N ≤ 100 000) і K (2 ≤ K ≤ N) відповідно. Другий рядок містить N цілих чисел Di (1 ≤ Di ≤ 10⁹) – діаметр i-ї кульки.

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

Пояснення: Приклад 1 - Існує кілька різних варіантів вибору. Степан може вибрати, наприклад, 6 кульок: 3, 5, 6, 4, 7 і 8
Приклад 2- Степан вибере 4 кульки: 1, 5, 3 і 6.

Приклади

8 5

10 20 10 20 10 10 20 20

10

6 4

21 12 17 28 16 21

5

C - Степан і Пари

Останнім часом Степан дуже цікавиться парами чисел, а крім пар чисел його цікавить найбільший спільний дільник пари чисел, позначимо його як НСД(x, y). Зараз у Степана є ціле число n і його цікавить така інформація: скільки існує пар цілих чисел (i,j), таких що 1 ≤ i, j ≤ n і виконується рівність i = НСД(i, j). Допоможіть йому у вирішенні нелегкої задачі.

Формат вхідних даних: у першому рядку дано ціле число n (1 ≤ n ≤ 10⁶).

Формат вихідних даних: єдиний рядок має містити відповідь на задачу.

Зауваження: У першому прикладі підходящою парою є пара (1, 1), так як НСД(1, 1) = 1.
У другому прикладі підходять 8 пар чисел: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).

Приклади

1

1

4

8

10

27

D - Спадок Степана

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

Формат вхідних даних: у першому рядку записані два цілих числа N (2 ≤ N ≤ 1000) і M (1 ≤ M < N) – загальна кількість місць на стоянці і кількість місць з лівого боку відповідно. У кожному із наступних N рядків записано по N цілих додатних чисел. j-е число i-го рядка означає, скільки буде платити i-ий житель за місце з номером j на цій стоянці. Кожне з цих чисел не перевищує 10⁶.

Формат вихідних даних: єдиний рядок має містити одне число – максимальний прибуток стоянки.

Зауваження: Не менш чим у 50% тестів N ≤ 30.

Приклади

2 1

3 2

6 4

8

4 1

4 3 1 1

3 1 1 1

1 1 4 1

1 1 1 2

12

E- Конфетна проблема Степана

Степан закохався і вирішив привернути увагу дівчини великою коробкою цукерок. За порадою друзів він поїхав на саму відому кондитерську фабрику ShenRo і дізнався, що великі коробки цукерок мають трикутну форму. Цукерки в цих коробках розташовуються у кілька рядів. У першому ряду знаходиться одна цукерка, у другому – дві, у третьому – три цукерки і так далі. На фабриці випускаються коробки цукерок з любим числом рядів у межах від 1 до N. Степан хоче купити одну із таких коробок. Але є одна проблема: його дівчина засмутиться, якщо кількість цукерок у коробці не буде ділитись націло на M, тому що у цьому випадку комусь із друзів дівчини дістанеться більше цукерок, чим іншим, або ж якісь цукерки залишаться лишніми. Тому Степан вирішив, що число цукерок у коробці має обов’язково ділитись націло на M.

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

Вам необхідно по заданих числах N і M знайти число способів вибору коробки цукерок із множини коробок з кількістю рядів від 1 до N. Способи вважаються різними, якщо їм відповідають коробки з різною кількістю рядів цукерок.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N - максимальна кількість рядів цукерок у коробці і M – кількість друзів дівчини Степана (1 ≤ N, M ≤ 2*10⁹) відповідно.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість різних способів вибору коробки цукерок.

Оцінювання: N, M ≤ 1000 – не менше 35 балів, N, M ≤ 10⁵– не менше 55 балів.

Приклади

20 10

4

53 199

0

5705 145

157

А - Арифметика

Молодший брат Степана Мишко навчається у першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану, напишіть програму, яка визначає, кількість різних цифр у числі Мишка.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 10¹⁰⁰⁰), записане Мишком.

Формат вихідних даних: вихідний файл має містити одне число – кількість різних цифр у числі.

Приклади

1233

3

B- Степан і сірники

Степан дуже полюбляє гратись із сірниками. Але він не балується ними, не розпалює вогонь, а розв'язує різні головоломки. Наприклад, він уміє прирівнювати число дев'ять до числа одинадцять, переклавши лише один сірник. Нещодавно батьки Степана подарували йому декілька наборів, кожен з яких складається з дванадцяти сірників. Хлопчик почав збирати з них різні геометричні фігури. Він вже зібрав багато різних фігур, але тепер йому стало цікаво: з яких наборів можливо склеїти каркас паралелепіпеда за допомогою дванадцяти сірників з набору та клею? Ламати сірники не можна і жоден із сірників не повинен виступати за каркас.

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

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

Формат вихідних даних: вихідний файл має містити N рядків. Для кожного набору сірників виведіть “yes”, якщо з нього можливо склеїти каркас паралелепіпеда, і “no” в іншому випадку.

Приклади

2

1 1 1 1 2 2 2 2 3 3 3 3

1 1 1 1 2 2 2 2 3 3 3 4

yes

no

C - Задача від Степана

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

Наприклад, прямокутник зі сторонами 1 і 10 можна повністю накрити прямокутником 10 і 3, але не можна накрити прямокутником зі сторонами 9 і 9. Прямокутники зі сторонами 10 і 3, а також зі сторонами 9 і 9 накрити не можна, відповідно в наборі із цих трьох прямокутників тільки один маленький. Напишіть програму, яка вирішить згадану Степаном задачу – визначить кількість маленьких прямокутників у даному наборі.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (2 ≤ N ≤ 200000). У кожному з наступних N рядків міститься два цілих додатних числа – розміри одного прямокутника. Усі розміри не перевищують 1000000. Серед даних прямокутників немає однакових.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість маленьких прямокутників у даному наборі.

Приклади

3

1 10

9 9

10 3

1

4

1 7

2 6

3 5

4 4

0

D - Штрафи

Степан нещодавно купив автомобіль, але водійські права ще не отримав. В зв’язку з цим він не має права на ньому їздити. Але його дружина вже спланувала вихідні, і поїздка до столиці входить в ці плани. Недовго думаючи, Степан знайшов вихід. Відомо, що ДАІ стоять не на всіх дорогах, а лише на тих, які обминути не можна, тому що так вони спіймають більше правопорушників. Відомо, що в країні Степана N міст, і вони з’єднані M дорогами. Зрозуміло, ніякі дві дороги не з’єднують одну й ту саму пару міст (в країні ж розумні люди працюють). Степан живе в місті А, а столиця знаходиться в місті 1. За відсутність водійських прав штраф складає 1000 карбованців. Скажіть, скільки в нього має бути при собі грошей, щоб він міг виплатити всі штрафи.

Формат вхідних даних: Перший рядок містить два числа N, M (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵). Інші М рядків містять два числа Xi і Yi, які описують дорогу між містом Xi і містом Yi. В останньому рядку написано число A (2 ≤ A ≤ N) – місто в якому живе Степан.

Формат вихідних даних: Виведіть в одному рядку єдине число – кількість карбованців які Степан має мати при собі.

Приклади

6 7

1 2 

2 3

3 1

3 4

4 5

4 6

5 6

6

1000

E - Ремонт

Степан придбав нову квартиру і до приїзду батьків вирішив поклеїти шпалери. На перший погляд все просто, але, коли він приступив до роботи, виявилась невелика проблема – необхідно вирівнювати малюнки на сусідніх полосах шпалер. Як визнаний програміст, Степан сформулював задачу таким чином. Кожну полосу шпалер можна описати її частиною – прямокутником довжиною N і шириною M (щоб отримати повну полосу, цей прямокутник можна багато разів домалювати до самого себе справа і зліва). Для простоти подумки поділимо цей прямокутник на рівні клітинки так, щоб утворилось N рядків і М стовпців. Щоб було ще простіше, рисунок на шпалерах позначимо символами ”.” і ”*” (крапка і зірочка), по одному символу в кожній клітинці.

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

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N і M(1 ≤ N ≤ 20, 1 ≤ M ≤ 100000). Наступні N рядків містять по М символів кожна – опис першої полоси шпалер. Наступні N рядків містять по М символів кожна – опис другої полоси шпалер. Кожен рядок опису шпалер містить тільки символи ”.” і ”*”.

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

Приклади

2 5

.*.*.

*.*.*

*.*..

.*.**

1

1 5

***..

*..**

2

Готуємось до олімпіади з інформатики

$11.                   Сума арифметичної прогресії

$12.                   Числа Фібоначі

$13.                   Алгоритм Евкліда

$14.                   Прості числа (решето Ератосфена)

$15.                   Зчитування та порівняння рядків та символів

$16.                   Швидке сортування

$17.                   Повний перебір

$18.                   Векторний добуток

$19.                   Повний обхід дерева

$110.               Рекурсивний пошук шляху в графі

$111.               Побудова остового дерева

$112.                Пошук мінімального шляху (Флойд)

ІІI етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2012-2013н.р

http://176.31.28.231/cgi-bin/new-client?contest_id=11  

ІІIетапВсеукраїнськоїучнівськоїолімпіадизінформатики(м.Луцьк) 2013-2014н.р

http://www.e-olimp.com.ua/problems/7234

http://www.e-olimp.com.ua/ua/problems/7235

http://www.e-olimp.com.ua/ua/problems/7236

http://www.e-olimp.com.ua/ua/problems/7237

http://www.e-olimp.com.ua/ua/problems/7238

http://www.e-olimp.com.ua/ua/problems/7239

http://www.e-olimp.com.ua/ua/problems/7240

http://www.e-olimp.com.ua/ua/problems/7241

http://www.e-olimp.com.ua/ua/problems/7242

http://www.e-olimp.com.ua/ua/problems/7243

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

з інформатики 2014-2015 н.р.

Задача 1. «Код» (25 балів)

Ім’я файлу програми: kod.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 1с

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

«Ігрове поле»  абстрактне, по вертикалі в нас види транспорту, а по горизонталі - номер прохідної ділянки маршруту Матриця тепер прямокутна 3х4 (три види транспорту і 4 ділянки  шляху) .

На малюнку представлене положення покажчиків і фішок до моменту виведення  першої і другої послідовності видів транспорту на  маршруті.

Вхідні дані. Вхідний текстовий файл містить один рядок з чотирицифровим числом.

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

Приклади файлів

Задача 2. «Варіанти» (25 балів)

Ім’я файлу програми: variant.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 1с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянок  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …).  Кожним з видів транспорту можна скористуватися Kразів. Потрібно визначити кількість способів, якими можна проїхати маршрут.

Вхідні дані. Вхідний текстовий файл містить один рядок з трьома цілини числами N,M,K (1≤M,K,N≤50)).

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

Приклад файлів

Задача 3. «Транспорт» (25 балів)

Ім’я файлу програми: transport.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txtМаксимальний час роботи на одному тесті: 1с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянки  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …).  Кожним з видів транспорту можна скористуватися A_M разів і при цьому вартість одного проїзду цим видом транспорту B_M, де M номер виду транспорту. Потрібно визначити мінімальну вартість витрат на подолання шляху.

Вхідні дані. Вхідний текстовий файл містить три рядки. В першому рядку два цілих числа N,M (1≤M≤N≤1000000)). Два наступних рядки місять по M цілих чисел, які задають кількість можливих варіантів проїзду і вартість проїзду (0≤2A_M,B_M ≤2147483647).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду. Якщо проїзд неможливий то вивести “no”.

Приклад файлів

Задача 4. «Оптимальний маршрут» (25 балів)

Ім’я файлу програми: optimal.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 5с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянки  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …). Кожним з видів транспорту можна скористатися не більше K разів.  Вартість проїзду для кожної ділянки певним видом транспорту задано в таблиці T_NM, де N – номер ділянки, M - номер виду транспорту. Потрібно визначити мінімальну вартість витрат на подолання шляху.

Вхідні дані. Вхідний текстовий файл містить три рядки. В першому рядку три цілих числа N, M, K (1≤N, M, K≤1000)). В наступних M рядках містяться по N цілих чисел, які задають вартість проїзду (0≤T_MN ≤2147483647).

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

Приклад файлів