1. Числа (автор Данило Мисак)

Максимальна оцінка: 200 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: numbers.in
Вихідний файл: numbers.out
Програма: numbers.*

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

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

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

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

Приклади

Пояснення до першого прикладу
Є рівно два числа, що в сукупності з числами 5 і 15 утворюють дружню трійку: це число 3 (бо 3 ∙ 5 ділиться на 15, 3 ∙ 15 ділиться на 5, а 5 ∙ 15 ділиться на 3), а також число 75 (бо 5 ∙ 15 ділиться на 75, 5 ∙ 75 ділиться на 15, а 15 ∙ 75 ділиться на 5).

2. Трикутник (автор Данило Мисак)

Максимальна оцінка: 200 балів
Обмеження на час: 2,5 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: triangle.in
Вихідний файл: triangle.out
Програма: triangle.*

Задано деякий набір відрізків цілих довжин.

Завдання
З відрізків заданого набору побудуйте трикутник із найбільшим або найменшим можливим периметром.

Вхідні дані
У першому рядку вхідного файлу вказано число n — кількість відрізків; ця кількість не менша за 4 і не перевищує 10⁶. У другому рядку міститься n натуральних чисел, менших за 10⁹, — довжини відрізків. У третьому рядку записано три латинських літери, що утворюють або слово max, або слово min: вони відповідають задачам пошуку найбільшого та найменшого периметра трикутника відповідно.

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

Приклади

3. Граф (автор Данило Мисак)

Максимальна оцінка: 200 балів
Обмеження на час: 1,5 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: graph.in
Вихідний файл: graph.out
Програма: graph.*

У цій задачі ми говоримо про неорієнтовані графи.

Неорієнтований граф — це множина, що містить елементи двох типів:

• вершини графа — елементи довільної природи;

• ребра графа — неупорядковані пари вершин графа.

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

Інформацію про графи можна зберігати в пам’яті комп’ютера багатьма різними способами. Наприклад — простим переліком ребер, тобто пар номерів сполучених між собою вершин. Або з допомогою так званих списків суміжності: для кожної вершини зберігаємо в окремому масиві номери вершин, сполучених із даною вершиною ребром (тобто суміжних вершин).

Одержати з першого варіанта подання графа (переліку ребер) другий (списки суміжності) нескладно:

1. Запровадимо для кожної вершини окремий масив суміжних вершин, який спершу є порожнім.

2. Перебираючи ребра від першого до останнього, робимо таке: якщо на даному кроці ми розглядаємо ребро між вершинами A та B, то до списку суміжності вершини A додаємо вершину B, а до списку суміжності вершини B додаємо вершину A.

3. Закінчивши перебір ребер, матимемо подання графа списками суміжності.

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

Вхідні дані
У першому рядку вхідного файлу вказано натуральне число n, що не перевищує 1000, — кількість вершин графа. Вершини занумеровано натуральними числами від 1 до n. Далі йдуть n рядків: у k-му з них перераховано без повторів номери вершин, суміжних з k-ю. Усі такі номери відмінні від самого числа k. Відомо також, що кожна вершина сполучена принаймні з однією іншою і якщо у списку суміжності вершини k є вершина l, то і у списку суміжності вершини l є вершина k.

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

Приклад

4. Табори (автор Олександр Рудик)

Максимальна оцінка: 200 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: camps.in
Вихідний файл: camps.out
Програма: camps.*

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

Завдання
Визначити, скількома способами можна встановити n таборів для ночівлі й відпочинку за умови, що і s — довжина стежки, і s₁, s₂, …, s_n — відстані від старту до точок розташування таборів (у певних одиницях вимірювання довжини) можна подати різними натуральними числами, 0 < s₁ < s₂ < … < s_n < s.

Вхідні дані
Вхідний файл містить у вказаному порядку два натуральні числа:
s — довжина стежки;
n — кількість таборів, n < s < 200 000.

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

Приклади

5. Дороги (автор Олександр Рудик)

Максимальна оцінка: 200 балів
Обмеження на час: 20 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: roads.in
Вихідний файл: roads.out
Програма: roads.*

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

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

• якщо населені пункти сполучено дорогою, то вона єдина;
• рух кожною дорогою — двосторонній.

Вхідні дані
Перший рядок вхідного файлу містить у вказаному порядку два натуральні числа:

• n — кількість населених пунктів, занумерованих натуральними числами від 1 до n включно, 3 ≤ n ≤ 4096;

• m — кількість усіх доріг, 3 ≤ m ≤ 8 386 560.

Кожний з наступних m рядків містить опис певної дороги за допомогою трьох натуральних чисел:

• j, k — номери населених пунктів, сполучених дорогою, 1 ≤ j, k ≤ n, j ≠ k;

• v — вартість утримання дороги в солідах (римських золотих монетах), 1 ≤ v ≤ 65432.

Вихідні дані

Єдиний рядок вихідного файлу містить номери доріг у порядку зчитування, що утворюють потрібний набір. Порядок цих номерів — довільний. Вхідні дані гарантують існування розв’язку. Якщо розв’язків кілька, потрібно записати будь-який, але лише один.

Приклад

6. Парасолька

Максимальна оцінка: 200 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: umbrella.in
Вихідний файл: umbrella.out
Програма: umbrella.*

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

Завдання
Визначити кількість різних видів розфарбувань купола парасольки.

Вхідні дані

Вхідний файл містить у вказаному порядку такі натуральні числа:

• n — кількість секторів купола парасолі, 2 ≤ n ≤ 19;
• m — кількість можливих кольорів, 2 ≤ m ≤ 19.

У 55% тестів n ≤ 6. У 70% тестів m ≤ 6.

Вихідні дані
Вихідний файл має містити одне натуральне число — шукану кількість різних способів розфарбування куполу парасолі. Вхідні дані гарантують, що добуток n і цієї шуканої кількості не перевищує 10¹⁹.

Приклади