1. Банкiвська справа, 20 балiв
Молодий ломбардець Гуччо Бальйонi (герой серiї творiв французького письменника Морiса Дрюона) часто виконував таємнi доручення сучасних йому можновладцiв Францiї, Анґлiї та Італiї. Не маючи можливостi протягом трьох рокiв безпосередньо самому займатися справами, вiн вирiшив отримати зиск, вклавши грошi у справи паризьких банкiрiв. Виявилося, що розмiр винагороди (% зиску) рiзний у рiзних банкiрiв. Звичайно, чим бiльшу суму вiн дасть банкiру, тим бiльше отримає через 3 роки. І не менше, нiж дав банкiру. Але в кожного банкiра % зиску рiзний для рiзних сум. Нажаль, за розрахунками Гуччо, йому нiколи не отримати бiльше 1000 лiврiв (середньовiчних французьких монет).

Завдання
Створiть програму profit.*, яка домоможе молодому ломбардцю отримати якнайбiльшi статки.

Вхідні дані
Перший рядок файлу profit.dat у вказаному порядку мiстить 2 натуральних числа:
m — кiлькiсть лiврiв, яку молодий Гуччо може використати для збагачення;
n — кiлькiсть паризьких банкiрiв.
Тут m і n не перевищують 100.
Для j в межах вiд 1 до m (j + 1)-ий рядок цього файлу мiстить послiдовнiсть n натуральних чисел. k-ий член цiєї послiдовностi — це кiлькiсть монет, яку отримає Гуччо через три роки вiд k-го банкiра, вiддавши йому j монет перед вiд'їздом.

Вихідні дані
Перший рядок вихiдного файлу profit.res має мiстити найбiльшу кiлькiсть лiврiв, яку може мати молодий ломбардець через 3 роки, використавши m лiврiв належним чином.
Другий рядок цього файлу має мiстити послiдовнiсть n невiд'ємних цiлих чисел. k-ий член цiєї послiдовностi — це кiлькiсть лiврiв, яку має дати Гуччо k-му банкiру, щоб отримати максимальний зиск вiд своїх капiталовкладень (потрiбно подати хоча б один з варiантiв розподiлу).

Приклад

2. Криниця, 20 балів.
Будівельники отримали завдання спорудити огорожу, яка на плані має вигляд замкненої ламаної без самоперетинів, і впорядкувати криницю.

Завдання
Створіть програму well.*, яка допоможе з'ясувати:

• яка відстань від криниці до огорожі;
• чи буде криниця знаходитися всередині огородженої ділянки.

Вхідні дані
Файл well.dat містить лише натуральні числа, які не перевищують 30.

Перший рядок цього файлу містить n — кількість прямолінійних частин огорожі, довжину кожної з яких виражено натуральним числом.

Другий рядок цього файлу містить послідовність n абсцис (у деякій декартовій системі координат) всіх початків (кінців) прямолінійних ділянок огорожі у порядку обходу її периметру.

Третій рядок цього файлу містить послідовність n ординат всіх початків (кінців) прямолінійних ділянок огорожі у тому самому порядку, що й другий рядок файлу.

Четвертий рядок цього файлу містить координати криниці (у тій же системі координат).

Вихідні дані
Перший файлу well.res має містити відстань від криниці до огорожі, подану:

• або цілим числом;

• або коренем квадратним натурального числа, яке не є точним квадратом іншого натурального числа, у вигляді sqrt(…);

• або нескоротним дробом, чисельник і знаменник якого — натуральні числа. Якщо знаменник цього дробу дорівнює 1, то риску дробу / і знаменник записувати непотрібно.

Другий рядок цього файлу має містити один з прийменників анґлійської мови: in, on, out, якщо криниця буде знаходитися відповідно всередині огорожі, на одній з ланок огорожі чи зовні її відповідно.

Приклади

3. Лабіринт, 20 балів.

Завдання
Створіть програму labirint.*, яка допоможе герою твору Джерома К.Джерома «Троє у човні, не рахуючи собаки» Гаррісу якнайшвидше вийти з Гемптон-Кортського лабіринту. Лабіринт на плані має вид прямокутника, сторони якого спрамовані із заходу на схід або з півночі на південь (наскільки це можливо, враховуючи кулясту форму Землі). Розміри лабіринту в ярдах (анґлійська міра довжини, приблизно 91,44 см) вздовж паралелі та мередіану виражено натуральними числами n та m відповідно, а його загальна площа mn не перевищує 10000 (квадратних ярдів). Всю територію лабіринту поділено на квадрати з довжиною сторони 1 ярд. Частину квадратів засаджено кущами з колючками, які можна лише обійти.

Вхідні дані
Перший рядок файлу labirint.dat містить два натуральних числа m і n — розміри лабіринту в ярдах.

Наступні m рядків по n символів цього файлу містять схему лабіринту, в якій символ « » (пропуск) означає вільний квадрат поверхні, інший символ — квадрат з кущем, хрестик (знак додавання) «+» — початкове розташування Гарріса. Виходу з лабіринту відповідають елементи 1-го та m-го рядка і 1-ий та n-ий елемент кожного рядка, якщо вони є пропуском або знаком додавання. Рух у лабіринті здійснюють у напрямку сторін світу на вільний від кущів сусідній квадрат. Рухові на північ південь, захід чи схід відповідає рух вгору, вниз, ліворуч чи праворуч на один символ на схемі, поданій файлом labirint.dat.

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

Другий рядок цього файлу має містити опис такого найкоротшого шляху — кроків від першого до останнього, у якому літера n позначає крок на північ (анґлійською north), s — на південь (south), e — на схід (east), w — на захід (west).

Якщо Гарріс вже знаходяться на виході, то перший рядок файлу labirint.res містить лише число 0, а другий рядок — порожній або відсутний.

Якщо вийти з лабіринту неможливо (не будемо обговорювати, яким чином у цьому випадку Гарріс потрапив у відповідне місце лабіринту), то єдиний рядок labirint.res має містити лише число –1.

Приклад

9 9
ШШШШШШШШШ
Ш        
Ш ШШШШШШШ
Ш Ш   + Ш
Ш Ш Ш Ш Ш
Ш Ш Ш Ш Ш
Ш Ш Ш Ш Ш
Ш   Ш   Ш
ШШШШШШШШШ

22
wwwsssswwnnnnnneeeeeee

4. Куб, 24 бали
Відстанню на поверхні многоґранника між двома точками називають найменшу довжина ламаної, що з'єднує дві дані точки, і всі ланки якої (ламаної) належать поверхні багатоґранника. Нехай у декартовій системі координат координати вершин куба дорівнюють 0 або деякому натуральному числу a, яке не перевищує 15.

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

Вхідні дані
Перший рядок файлу cube.dat містить у вказаному порядку 2 натуральних числа — a і n.

Для j в межах від 1 до n включно (j + 1)-ий рядок цього файлу містить 6 цілих невід'ємних чисел — відповідно координати (порядок усталений: спочатку абсциса x, потім — ордината y, і лише потім — апліката z) точки, розташованый на ґрані куба і в координатній площині xy, і довільної точки на поверхні куба.

Вихідні дані
Файл cube.res утворити з cube.dat дописуванням у кожен рядок, починаючи з другого, шуканого квадрату довжини ламаної, що з'єднує точки, чиї координати записано у цьому самому рядку.

Приклад

5. Вуличнi перегони, 30 балів
Орґанiзацiйний комiтет велосипедних перегонiв Лазуровий Берег-99 звернувся до жандармерiї Сан-Тропе з проханням дозволити провести велосипеднi перегони вулицями цього курортного мiстечка таким чином, щоб кожен учасник мав би певну свободу у виборi шляху до фiнiшу. Жандармерiя у вiдповiдь надiслала в органiзацiйний комiтет план проведення таких перегонiв. На плані пункти-перехрестя було позначено кругами i занумеровано натуральними числами в межах вiд 1 до певного натурального числа n, а окремi дiлянки перегонiв — вулицi з одностороннiм рухом — позначено стрiлками. На цьому планi:

• старт — пункт, з якого можна досягнути будь-який пункт перегонiв, i який неможливо досягнути з будь-якого iншого пункту;

• фiнiш — пункт, який можна досягнути з будь-якого iншого пункту, i з якого неможливо досягнути жоден iнший пункт.

Деякi пункти неможливо уникнути на шляху вiд старту до фiнiшу, не рахуючи останнiх.

Деякi з пунктiв, якi неможливо уникнути на шляху вiд старту до фiнiшу, розбивають план перегонiв на два плани. Інакше кажучи:

• кожен новоутворений план має пункти, вiдмiннi вiд старту й фiнiшу цього плану;

• новоутворенi плани не мають спiльних стрiлок, але мають єдиний спiльний пункт, що є фiнiшом для одного плану i стартом для iншого. Цей спільний пункт неможливо досягнути рухом вздовж стрілок, почавши рух з нього самого.

Завдання
Створiть програму race.*, яка допоможе членам органiзацiйного комiтету провести аналiз поданого плану.

Вхідні дані
Кiлькiсть рядкiв вхiдного файлу race.in дорiвнює n — кiлькостi всiх пунктiв перегонiв, що не перевищує 222. Для j в межах вiд 1 до n включно j-ий рядок цього ж файлу мiстить номери кiнцевих пунктiв тих стрiлок, якi виходять з j-го пункту.

Вихідні дані
Перший рядок вихiдного файлу race.out має мiстити у вказаному порядку номери пунктiв, що є стартом i фiнiшом.
Другий рядок цього самого файлу має мiстити кiлькiсть пунктiв, якi неможливо уникнути на шляху вiд старту до фiнiшу та номери цих пунктiв у порядку зростання.
Третiй рядок цього самого файлу має мiстити кiлькiсть пунктiв, якими можна розбити поданий план перегонiв на окремi плани, та номери цих пунктiв у порядку зростання.

Приклад

race.dat	race.res	план
3 3 4 5 6 6 7 8 9 5 9 1 2	10 9 2 3 6 1 3

6. Криптограма, 22 бали

Завдання
Створiть програму cripto.*, яка дешифрує запису дiї додавання, в якому всi доданки роздiлено знаком +, перед сумою стоїть знак =, а кожну цифру замiнено на лiтеру, причому:

• однаковi цифри замiнено на однаковi лiтери;
• рiзнi цифри замiнено на рiзнi лiтери;
• розрiзняються великi та малi лiтери;
• можуть використовуватися як лiтери латиницi, так i лiтери кирилицi;
• кiлькiсть доданкiв не перевищує 9, запис кожного з них мiстить не бiльше 9 цифр, але й не менше 2 цифр.

Вхідні дані
Перший рядок вхiдного файлу cripto.in мiстить натуральне число, яке є основою системи числення i лежить в межах вiд 5 до 10 включно.
Другий рядок цього самого файлу мiстить запис дії додавання. Роздiлення доданкiв, суми, знакiв + i = додатковими прогалинами не передбачається.

Вихідні дані
Файл cripto.out має містити всi способи дешифрацiї поданого запису дiї додавання по одному у кожному рядку без повторення (порядок довільний).

Приклад