4 8
Робочий стіл
На робочому столі операційної системи розташоване N ярликів, кожен з яких заданий цілими координатами x і в, а також назвою. Назва ярлика складається з маленьких символів латинського алфавіту (a-z). Необхідно перейти (тобто перемістити виділення) з виділеного ярлика S до ярлика F, за допомогою клавіатури, використавши найменшу можливу кількість натиснень. Перехід здійснюється за допомогою натиснень на клавіші з буквами a-z, або на стрілки “^”,“v”,“<” і “>”.
При натисненні на клавіші з буквами перехід відбувається по наступних правилах:
1. Якщо на робочому столі знаходяться ярлики, назва яких зачинається на букву, що натискує, і виділений один з них, то перехід відбувається на ярлик, з назвою, наступною в лексикографічному ладі серед тих, які зачинаються на цю букву (після останнього виділення переходить на перший). Тобто якщо є ярлики а, ab, b, то при натисненні а виділення переходитиме лише між а і ab.
2. Якщо назва поточного ярлика не зачинається на вибрану букву, то виділення переходить на лексикографічно найменший ярлик, який зачинається на букву, що натискує.
3. Якщо на робочому столі немає ярликів, назва яких зачинається на букву, що натискує, перехід не здійснюється.
При натисненні на стрілку перехід відбувається на найближчий в звичайному геометричному сенсі ярлик, який лежить в секторі стрілки. Визначимо сектор стрілки як прямий кут з вершиною у виділеному ярлику, бісектрисою якого є промінь, відповідний стрілці. Якщо ярлик лежить на кордоні сектора, то він відноситься до верхнього або нижнього сектора (а не до правого або лівого). Якщо в певному секторі немає жодного ярлика, то перехід не здійснюється. Якщо найближчих ярликів декілька, то вибирається ярлик з найменшою x координатою, а якщо і таких декілька, то вибирається з найменшою у-координатой.
Наприклад, якщо виділений ярлик а, те при натисненні стрілок можуть статися такі переходи:
1. Стрілка “<”. Виділення переходить на ярлик b, оскільки він є найближчим в секторі цієї стрілки. При подальшому натисненні “<” буде виділений ярлик з.
2. Стрілка “^”. У секторі стрілки знаходяться ярлики d і e. Виділення перейде на d, який ближче.
3. Стрілка “>”. У секторі “>” знаходиться лише ярлик g, на який і перейде виділення.
4. Стрілка “v”. У цьому секторі знаходяться ярлики f і h, які рівновіддалені від ярлика а. Виділення переходить на ярлик h, оскільки x-координата цього ярлика менша. Якщо після цього натискувати “v”, то виділення залишається на h, оскільки в секторі знизу немає жодного ярлика.
Завдання
Напишіть програму DESKTOP, яка за інформацією про назви ярликів і про їх розташування визначить найменшу можливу кількість натиснень клавіатури, за допомогою яких можна з вибраного ярлика досягти цільового.
Вхідні дані
Перший рядок вхідного файлу DESKTOP.DAT містить три цілі числа: N (1 N 1000) – кількість ярликів на робочому столі, S (1 S N) – номер вибраного ярлика, F (1 F N) – номер ярлика на який потрібно перейти. Кожна з подальших N рядків задає ярлик у форматі «x в text», x, в – цілі числа (0 x, в 106), а текст містить не більше ніж 50, і не менше чим один маленький символ латинського алфавіту a-z.
Жодні два ярлики не мають однакових координат і однакових назв. Координатна сітка – стандартна, тобто “^” збільшується у-координата, а “>” x-координата.
Вихідні дані
Єдиний рядок вихідного файлу DESKTOP.SOL повинна містити одне ціле число – мінімальну кількість натиснень на клавіатуру, які дозволять перейти від ярлика S до ярлика F.
Приклад вхідних і вихідних даних
DESKTOP.DAT
DESKTOP.SOL

8 1 4
5 4 а
2 3 b
3 2 h
0 3 з
4 6 d
7 6 e
7 2 f
9 6 g
1

Іспит
У вчителя своє ноу-хау запобігання списуванню під час іспиту. Він проводить іспит в двох аудиторіях, в першій з яких вірогідність списування низька, а в другій – висока, і необхідно уважно стежити за учнями. Першу аудиторію він формує по наступних положеннях:
1. Кожен хлопчик повинен сидіти за однією партою з дівчинкою. Кількість хлопчиків повинна дорівнювати кількості дівчаток.
2. В результаті спостережень вчитель знає, які пари хлопчиків і дівчаток не дозволяють один одному списувати. Лише такі пари можуть сидіти за однією партою.
3. Кількість учнів, які сидітимуть в першій аудиторії має бути найбільшою можливою.
Кожен учень має свій порядковий номер в списку класу, який включає хлопчиків і дівчаток. Варіант вибору учнів в першу аудиторію можна задати як впорядковану за збільшенням послідовність номерів учнів. Для визначеності, знайдемо лексикографічно найменший серед варіантів вибору учнів в першу аудиторію.
Розгледимо приклад класу з п'яти учнів. Хай вчитель знає, що хлопчика 1 можна посадити разом з дівчатками 2, 4, 5, а хлопчика 3 з дівчатками 2 і 5. Тоді максимальна кількість пар, яку можна сформувати для того, щоб посадити в першу аудиторію рівне 2. Можливі варіанти вибору можна записати так: (1, 2, 3, 4), (1, 2, 3, 5), (1, 3, 4, 5). Серед цих варіантів перший є лексикографічно найменшим.
Завдання
Напишіть програму EXAM, яка по кількості учнів в класі і набору пар хлопчиків і дівчаток, яких вчитель може посадити разом, знаходить найменший впорядкований список учнів, які писатимуть іспит в першій аудиторії.
Вхідні дані
Перший рядок вхідного файлу EXAM.DAT містить два цілі числа: N (1?N?50) – кількість учнів в класі, M (M?0) – кількість пар хлопчиків і дівчаток, яких вчитель може посадити за одну парту. Далі слідує M рядків, кожна з яких містить два номери в списку класу – номер хлопчика і номер дівчинки (саме у такому ладі). У вхідному файлі пари не повторюються. Всі номери від 1 до N.
Вихідні дані
Єдиний рядок вихідного файлу EXAM.SOL повинна містити послідовність цілих чисел впорядкованих за збільшенням – список учнів, які писатимуть іспит в першій аудиторії. Якщо неможливо знайти жодної пари, яка зможе писати іспит в першій аудиторії, вихідний файл повинен містити одну порожню рядок.
Приклад вхідних і вихідних даних
EXAM.DAT
EXAM.SOL

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

XIX Всеукраїнська олімпіада по інформатиці
Другий тур
Пошук рядка
У послідовності, яка складається з маленьких символів латинського алфавіту, необхідно знайти підпослідовність найбільшої довжини, яка складається з різних символів, що йдуть підряд в послідовності.
Завдання
Напишіть програму SUBSTR, яка по заданій послідовності знаходить першу підпослідовність, що складається з різних символів.
Вхідні дані
Вхідний файл SUBSTR.DAT містить послідовність, яка, для зручності, розбита на декілька термін. Кожен рядок містить не більше 100 символів. Спільна довжина послідовності – не більше 10 000 000 символів.
Вихідні дані
Єдиний рядок вихідного файлу SUBSTR.SOL повинна містити першу з підпослідовностей найбільшої довжини, які не містить однакових символів.
Приклад вхідних і вихідних даних
SUBSTR.DAT
SUBSTR.SOL

abcabcdabc
bacdbca
abcd

Щасливий квиток
Квиток на планеті Олімпія містить шестизначний номер. Жителі планети трохи незвично визначають, чи є квиток щасливим. Вони загадують деяке число до, а потім намагаються скласти з номера це число за допомогою наступних правил.
1. Спочатку номер розбивають на цифри, і певні сусідні цифри об'єднують в числа.
2. Між отриманих чисел розташовують дужки і знаки операцій: плюс, мінус, помножити, розділити по математичних правилах. Також дозволяється використовувати унарний мінус.
3. Не можна міняти місцями цифри.
4. Якщо удається скласти таке вираження, яке після обчислення дорівнює шуканому числу до, то квиток вважається за щасливий.
Операцію «розділити» можна використовувати лише у випадках, коли унаслідок ділення буде отримано ціле число.
Розгледимо квиток номер: 182836. Покладемо k=840. Розіб'ємо число на чотири: 1, 8, 2, 836. Число до можна отримати, наприклад, таким чином: 1*(8/2+836)=840.
Завдання
Напишіть програму LUCKY, яка по номеру квитка і числу до визначить, чи є цей номер щасливим, і знайде один з варіантів розбиття номера на послідовність чисел, між якими можна розташувати математичні операції і дужки для отримання шуканого числа до.
Вхідні дані
Єдиний рядок вхідного файлу LUCKY.DAT містить два числа: ціле до (1?k?1000) і номер квитка. Номер квитка складається з шести цифр, і може зачинатися з 0.
Вихідні дані
Єдиний рядок вихідного файлу LUCKY.SOL повинна містити будь-який з можливих наборів чисел, на які може бути розбитий номер квитка для отримання числа до. Якщо число не може бути отримане, то єдиний рядок вихідного файлу повинен містити цифру 0 (нуль).
Приклади вхідних і вихідних даних
LUCKY.DAT
LUCKY.SOL

840 182836 1 8 2 836
120 000001 0
Відстань
На плоскості своїми координатами задане N крапок. Розгледимо набір прямих, проведених через всі різні пари крапок. Необхідно визначити найбільшу можливу відстань від будь-якої заданої точки, до будь-якої прямої побудованою по двох іншим крапкам.
Завдання
Напишіть програму DIST, яка по набору точок плоскості обчислює максимальну відстань від крапки до прямої.
Вхідні дані
Перший рядок вхідного файлу DIST.DAT містить цілу однину – кількість точок N
(3?N?700) заданих на плоскості. Далі слідує N рядків, кожна з яких задає точку плоскості у форматі “x в” (-5000?x, в?5000), x і в – цілі числа. Жодні дві крапки не мають однакових координат.
Вихідні дані
Єдиний рядок вихідного файлу DIST.SOL повинна містити найбільшу відстань від однієї із заданих точок, до прямої, побудованої на двох інших крапках, з точністю до 10-6. Відповідь має бути записаний у форматі з крапкою (<ціла частка>.<дробная частка>)
Приклад вхідних і вихідних даних
DIST.DAT
DIST.SOL

5
1 4
2 0
2 4
3 5
4 4 4.242641