XIX Всеукраїнська олімпіада з інформатики
Перший тур
Дільники
За заданим натуральним числом N необхідно обчислити кількість натуральних чисел, які є дільниками N! (факторіалу числа N). Наприклад, при N=4, N!=4·3·2·1=24. Це число має такі дільники: 1, 2, 3, 4, 6, 8, 12, 24. Таким чином шукана кількість дорівнює 8.
Завдання
Напишіть програму DIVISOR, що за натуральним N, знаходить кількість дільників його факторіалу.
Вхідні дані
Єдиний рядок вхідного файлу DIVISOR.DAT містить одне ціле число N (1≤N≤45).
Вихідні дані
Єдиний рядок вихідного файлу DIVISOR.SOL має містити одне ціле число – знайдену кількість дільників числа N!
Приклад вхідних та вихідних даних
|
DIVISOR.DAT |
DIVISOR.SOL |
|
4 |
8 |
Робочий стіл
На робочому столі операційної системи розташовано N ярликів, кожен з яких заданий цілими координатами x та y, а також назвою. Назва ярлику складається з маленьких символів латинського алфавіту (a-z). Необхідно перейти (тобто перемістити виділення) з виділеного ярлика S до ярлика F, за допомогою клавіатури, використавши найменшу можливу кількість натискань. Перехід здійснюється за допомогою натискань на клавіші з літерами a-z, або на стрілки “↑”,“↓”,“←” та “→”.
При натисканні на клавіші з літерами перехід відбувається за такими правилами:
-
Якщо на робочому столі є ярлики, назва яких починається на натиснуту літеру, та виділено однин з них, то перехід відбувається на ярлик, з назвою наступною у лексикографічному порядку серед тих, які починаються на цю букву (після останнього, виділення переходить на перший). Тобто, якщо є ярлики a, ab, b, то при натисканні a виділення буде переходити лише між a та ab.
-
Якщо назва поточного ярлика не починається на обрану літеру, то виділення переходить на лексикографічно найменший ярлик, що починається на натиснуту літеру.
-
Якщо на робочому столі немає ярликів, назва яких починається на натиснуту літеру, перехід не відбувається.
При натисканні на стрілку перехід відбувається на найближчий у звичайному геометричному розумінні ярлик, що лежить в секторі стрілки. Визначимо сектор стрілки як прямий кут з вершиною у виділеному ярлику, бісектрисою якого є промінь, що відповідає стрілці. Якщо ярлик лежить на границі сектору, то він відноситься до верхнього або нижнього сектору (а не до лівого, або правого). Якщо у певному секторі немає жодного ярлику, то перехід не відбувається. Якщо найближчих ярликів декілька, то обирається ярлик з найменшою x координатою, а якщо і таких декілька, то обирається з найменшою y-координатою.
Наприклад, якщо виділено ярлик a (див. рисунок), то при натисканні стрілок можуть відбутись такі переходи:
-
Стрілка “←”. Виділення переходить на ярлик b, оскільки він є найближчим у секторі цієї стрілки. При наступному натисканні “←” виділення перейде на c.
-
Стрілка “↑”. В секторі стрілки знаходяться ярлики d та e. Виділення перейде на d – цей ярлик ближче.
-
Стрілка “→”. В секторі “→” знаходиться тільки ярлик g, який і буде виділено.
-
Стрілка “↓”. В цьому секторі знаходяться ярлики 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≤106), а текст складається з не більш ніж 50, та не менше ніж з одного маленького символу латинського алфавіту a-z.
Жодні два ярлика не мають однакових координат, або ж однакових назв. Координатна сітка – стандартна, тобто “↑” збільшується y-координата, а “→” x-координата.
Вихідні дані
Єдиний рядок вихідного файлу DESKTOP.SOL має містити одне ціле число – мінімальну кількість натискань на клавіатуру що дозволять перейти з ярлика S до ярлика F.
Приклад вхідних та вихідних даних
|
DESKTOP.DAT |
DESKTOP.SOL |
|
8 1 4 5 4 a 2 3 b 3 2 h 0 3 c 4 6 d 7 6 e 7 2 f 9 6 g |
1
|
Екзамен
Вчитель має своє ноу-хау що до запобігання списування на екзамені. Він проводить екзамен у двох аудиторіях, в першій з яких ймовірність списування низка, а в іншій – висока, та потрібно дуже уважно стежити за учнями. Першу аудиторію він формує за такими положеннями:
-
Кожен хлопець повинен сидіти за однією партою з дівчиною. Кількість хлопців повинна дорівнювати кількості дівчат.
-
У результаті спостережень вчитель знає які пари хлопців та дівчат не дозволяють одне одному списувати. Тільки такі пари можуть сидіти за однією партою.
-
Кількість учнів, що сидітимуть у першій аудиторії має бути найбільша можлива.
Кожен учень має свій порядковий номер у списку класу, який включає хлопчиків і дівчат. Варіант вибору учнів у першу аудиторію можна задати як впорядковану за зростанням послідовність номерів учнів. Для визначеності, знайдемо лексикографічно найменший серед варіантів вибору учнів у першу аудиторію.
Розглянемо приклад класу з п’яти учнів. Нехай вчитель знає, що хлопця 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 має містити послідовність цілих чисел впорядкованих за зростанням – список учнів, які будуть писати іспит у першій аудиторії. Якщо неможна знайти жодної пари, що зможе писати екзамен у першій аудиторії, вихідний файл повинен містити один порожній ря