1. Сходові числа

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

Назвімо сходовими числами числа вигляду a^a⋰a, де a — натуральне число, що входить у запис щонайменше двічі, а піднесення до степеня здійснюють «згори донизу». Наприклад, числа 3³ = 27 та 2²²² = 2¹⁶ = 65 536 є сходовими. Схо­до­вим числом є й одиниця, бо 1 = 1¹. А от числа 2, 3 і 5 схо­до­ви­ми не є, бо подати їх у потрібному вигляді не­мож­ливо.

Завдання
Установити, скільки натуральних чисел, що не перевищують заданого нату­ра­­ль­­ного числа n, є сходовими.

Вхідні дані
У вхідному файлі записано лише одне натуральне число n ≤ 10⁹.

Вихідні дані
У вихідний файл вивести одне число — кількість сходових чисел у межах від 1 до n включно.

Приклад

2. Таблиця

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

Задано квадратну таблицю n×n, що складається з натуральних чисел. Роз­гля­да­ти­ме­мо шля­­­хи з лі­­­вої верхньої комірки таблиці у праву нижню, які до­ві­льним чи­ном ідуть ко­мір­ками таблиці праворуч та вниз (але ніколи ліворуч або вгору). Уз­довж кож­ного такого шляху розташовано 2n − 1 число. Якщо для пев­ного шляху даний набір чисел є «симетрич­ним», тобто читається у зворот­но­му порядку так само, як і у прямому, називати­ме­мо вибраний шлях па­лін­дро­міч­ним.

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

Вхідні дані
У першому рядку вхідного файлу вказано розмір таблиці — ціле число n: 2 ≤ n ≤ 100. У наступних n рядках файлу записано по n нату­ра­ль­них чисел, що не перевищують 10 000 та задають таблицю.

Вихідні дані
Вихідний файл повинен містити єдине число: лишок від ділення на 101 кі­ль­кості паліндромічних шляхів на заданій таблиці.

Приклади

Коментар: у першому прикладі є 4 паліндромічних шляхи:

• праворуч — праворуч — униз — униз (7–10–5–10–7);
• праворуч — униз — праворуч — униз (7–10–8–10–7);
• униз — праворуч — униз — праворуч (7–5–8–5–7);
• униз — униз — праворуч — праворуч (7–5–8–5–7).

У другому прикладі кожен з 252 можливих шляхів є паліндромічним, тож згідно з умовою потрібно вивести лишок від ділення 252 на 101 — число 50.

3. Ламана

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

Завдання
На площині позначено кілька точок. Якщо це можливо, побудуйте замк­не­ну ламану без самоперетинів, що проходить через усі ці точки і не має відмін­них від них вершин.

Вхідні дані
У першому рядку вхідного файлу задано кількість точок n, 3 ≤ n < 2017. У n наступних рядках вказано по дві координати кожної точки: абсцису та ординату відповідно. Повторення точок немає. Всі координати — цілі числа, що за модулем не перевищують 10 000.

Вихідні дані
Якщо побудувати потрібну замкнену ламану неможливо, вивести 0. інакше вивести порядок, у якому задані точки розташовано на ламаній, тобто порядок обходу всіх цих точок, починаючи з довільного місця і в довіль­ному напрямку. Нумерація точок почи­нається з одиниці. Ламаних, що задовольняють умову, може бути кілька. Достат­ньо знайти хоча б одну.

Приклад

4. Дільники

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

Завдання
Пер Ґюнт, герой п’єси норвезького письменника Генріка Ібсена, потрапив у полон короля тролів. Щоб визволитися, Пер Ґюнт повинен відповісти на питання: скількома способами дану кількість однакових діамантів можна розділити на одну чи кілька частин таким чином, щоб кількість діамантів у кожній з них була однаковою?

Вхідні дані
Єдиний рядок файлу містить десятковий запис натурального числа n, що містить не більше, ніж 32 цифри й не має багатоцифрових (більше ніж 1 цифра у десятковому записі) простих дільників. В 1/3 тестів це число не перевищує 10⁹, у 2/3 тестів це число не перевищує 10¹⁸.

Вихідні дані
Єдиний рядок файлу має містити десятковий запис кількості натуральних дільників числа n з вхідного файлу.

Приклад

5. Печери

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

Пер Ґюнт, герой п’єси норвезького письменника Генріка Ібсена, потрапив у полон короля тролів. Щоб визволитися, Пер Ґюнт повинен перемогти у грі, яку король пропонує своїм бранцям. Правила гри такі:

• є 10 печер , деякі з яких сполучені між собою;

• бранець грає протягом m днів:

  • у перший день він може вибрати собі довільну печеру;

  • кожного наступного дня він може або залишитися у печері, у якій перебуває, або перейти у будь-яку іншу печеру, до якої є хід з поточної печери;

• кожного дня король винагороджує бранця певною наперед обумовленою кількістю золотих монет, яка залежить і від печери, і від номера дня;

• якщо за всю гру бранець накопичить кількість монет, виражену одним з l «коро­лів­ських чисел», то бранця навіки залишають у полоні — він програв. Інакше його відпускають на волю з виграшем — усією накопиченою за час гри кількістю монет.

Завдання
Визначити N_w, p_max, p_min — відповідно кількість різних виграшів, найбільший і найменший виграші.

Вхідні дані
Перший рядок файлу містить десяткові записи натуральних чисел m, l, де m ≤ 60. Кожний з наступних 10 рядків містить по 10 цілих чисел — нулів або одиниць. При 1 ≤ j, k ≤ 10: якщо k-те число (j + 1)-го­ рядка файлу дорівнює 1, то з j-ої­ печери можна потрапити безпосередньо до k-ої печери і навпаки. Інакше це зробити неможливо. Кожний з наступних m рядків містить по 10 невід’ємних цілих чисел. При 1 ≤ j ≤ m і 1 ≤ k ≤ 10: k-те число (j + 11)-го рядка — кількість монет, які отримує гравець як винагороду за перебування у j­-ий день у k-ої печері. Останній (m + 12)-ий­ рядок містить у поряд­ку спадання l різних цілих невід’ємних «королів­ських чисел», кожне з яких менше від 2⁶⁴. Останнє число у цьому рядку — нуль.

Вихідні дані
Єдиний рядок файлу має містити десяткові записи трьох чисел: N_w, p_max, p_min. Якщо N_w = 0, то p_max = p_min = 0. Відомо, що p_max < 2⁶⁴, l + N_w ≤ 10⁶.

Приклад

6. Розкладна послідовність

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

Кожний елемент послідовності a₁, a₂, ..., a_n, ... є натуральним числом. Під­послі­довність a_j1, a_j2, ..., a_jn, ... називатимемо траєкторією, якщо для кожного натурального k справджується таке співвідношення: j_k+1 = j_k + a_jk. Послідовність a₁, a₂, ..., a_n, ... будемо називати розкладною, якщо її можна розділити на декілька траєкторій.

Завдання
Для періодичної послідовності a₁, a₂, ..., a_n, визначити, чи є вона розкладною. Якщо це так, знайти кількість траєкторій, з яких складається задана послідовність.

Вхідні дані
Перший рядок містить натуральне число n (1 ≤ n ≤ 100000) — кількість чисел у періоді послідовності. У наступному рядку через пробіли записано натуральні числа a₁, a₂, ..., a_n, які складають один період. Інакше кажучи, послідовність має вигляд a₁, a₂, ..., a_n, a₁, a₂, ..., a_n, a₁, a₂, ..., a_n, ... Усі члени послідовності не перевищують 100 000.

Вихідні дані
Якщо послідовність a₁, a₂, ..., a_n, a₁, a₂, ..., a_n, a₁, a₂, ..., a_n, ... є розкладною, вивести кількість її траєкторій. У протилежному випадку вивести –1.

Приклади

Коментар
У першому випадку траєкторіями є підпослідовності:
(a₁, a₆, a₇, a₁₂, a₁₃, ...),
(a₂, a₅, a₈, a₁₁, a₁₄, ...),
(a₃, a₄, a₉, a₁₀, a₁₅, ...).

У другому випадку послідовність не можна розкласти, бо a₅ має одночасно бути наступним елементом у траєкторії після a₂ та після a₄.