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!

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

Робочий стіл

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

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

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

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

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

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

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

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

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

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

4. Стрілка “↓”. В цьому секторі знаходяться ярлики 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.

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

Екзамен

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

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 має містити послідовність цілих чисел впорядкованих за зростанням – список учнів, які будуть писати іспит у першій аудиторії. Якщо неможна знайти жодної пари, що зможе писати екзамен у першій аудиторії, вихідний файл повинен містити один порожній ря