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

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

Якось Орися з Марисею натрапили на деяке натуральне число n. Орися порахувала суму його цифр, а Марися — добуток. На подив дівчатам пораховані сума та добуток виявилися рівними одному й тому самому числу d.

Завдання
Знаючи d, відновіть найбільше можливе значення початкового числа n.

Вхідні дані
У вхідному файлі вказано натуральне число d.

• У 50% тестів d ≤ 20.
• У 50% тестів 20 < d ≤ 1 000 000.

Усі тести мають однакову вартість.

Вихідні дані
У вихідний файл виведіть найбільше можливе значення n або число 0, якщо такого значення не існує.

Приклади

Пояснення до першого прикладу
І сума, і добуток цифр числа 321 дорівнюють 6: 3 + 2 + 1 = 3 · 2 · 1 = 6. Таку саму властивість мають і числа 312, 231, 213, 132, 123, а також одноцифрове число 6, але 321 з них найбільше, тому саме його і треба вивести.

2. Черевички на підборах (автор Данило Мисак)

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

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

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

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

• У 25% тестів n ≤ 1000 і в жодної дівчини немає двох черевиків з однаковою висотою підбора.

• У 25% тестів n ≤ 1000 і принаймні в однієї з дівчат є хоча б два черевики з однаковою висотою підбора.

• У 25% тестів 1000 < n ≤ 200 000 і висоти підборів не перевищують 1000.

• У 25% тестів 1000 < n ≤ 200 000 і висота підбора принаймні на одному черевикові більша за 1000.

Усі тести мають однакову вартість.

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

Приклад

Пояснення до прикладу
З черевиків дівчат можна скласти чотири пари: пару з висотою підборів 3, пару з висотою підборів 8 і дві пари з висотою підборів 5.

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

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

В Орисі й Марисі є великий клітчастий аркуш паперу n × n. Орися дуже товстим чорним маркером накреслила на ньому межі квадрата таким чином, що вони проходять не по межах клітинок, а по самих клітинках.

З того ж боку аркуша свій квадрат тим же чорним маркером накреслила й Марися, причому її квадрат міг дотикатися, перетинатися або навіть збігатися з Орисиним. Розміри квадратів дівчат могли бути однаковими, але могли й відрізнятися. Відомо, однак, що розміри зовнішнього контуру обох квадратів не менші за 3 × 3 (тобто квадрат не вироджується в чотири чорних клітинки).

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

Вхідні дані
У першому рядку вхідного файлу вказано натуральне число n — лінійний розмір аркуша. Далі йде n рядків, у кожному з яких через пробіл задано n символів, кожен з яких є або крапкою, що позначає незафарбовану клітинку, або символом #, що позначає зафарбовану клітинку. Після останнього символу кожного рядка (крапки чи #) пробілу немає.

• У 25% тестів 3 ≤ n ≤ 10.
• У 75% тестів 10 < n ≤ 1000.

Усі тести мають однакову вартість. Остаточну оцінку за цю задачу буде отримано таким чином: сумарний бал за пройдені тести округлять униз до найближчого числа, що ділиться на 40. Наприклад, якщо ваша програма пройде 100% тестів, вона набере 200 балів; якщо ваша програма пройде 95% тестів, вона набере 160 балів; якщо програма пройде 45% тестів, вона набере 80 балів; якщо програма пройде 10% тестів, вона набере 0 балів.

Вихідні дані
Нумерація клітинок починається з лівого верхнього кута. Ліва верхня клітинка аркуша має координати (1, 1), клітинка праворуч від неї — (2, 1), клітинка знизу — (1, 2) і т. д.

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

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

Приклад

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

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

У стіну забито багато цвяхів. Орися і Марися намагаються прив’язати натягнуту нитку до двох цвяхів так, щоб отримати якомога менший, але відмінний від нуля кут нахилу її до горизонталі.

Завдання
Серед даних точок координатної площини знайти дві точки, які є кінцями відрізка з найменшим додатним кутом нахилу відносно горизонталі.

Вхідні дані
Перший рядок містить натуральне число n (2 ≤ n ≤ 100000) — кількість точок, де розташовано цвяхи. Далі ідуть n рядків, кожен з яких містить два цілих числа x_j, y_j (0 ≤ x_j, y_j ≤ 30000), що є прямокутними координатами різних точок. Число x_j задає розташування по горизонталі, а y_j — по вертикалі.

Вихідні дані
В єдиному рядку через пробіли вивести числа x_j, y_j, x_k, y_k. Тут (x_j, y_j) та (x_k, y_k) — координати двох точок з даних, які задають найпологіший схил. Інакше кажучи, при яких відношення | x_j – x_k | / | y_j – y_k | визначене і є найбільшим серед відношень такого вигляду. Точки вказати в такому порядку, щоб справджувалася нерівність y_j < y_k і:

• якщо можливих розв’язків декілька, обрати той, де y_j є найменшим;

• якщо й за цієї умови є кілька варіантів, обрати розв’язок з найменшим x_j;

• якщо й за цих умов (попарного збігу перших двох чисел) є кілька варіантів, обрати розв’язок з найменшим y_k;

• якщо й за цих умов є кілька варіантів, обрати розв’язок з найменшим x_k.

Якщо задача не має розв’язку, вивести 0.

Приклади

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

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

Марися й Орися пішли до кінотеатру. Біля каси кінотеатру m + n дітей (всього разом з Марисею та Орисею) вишикувалося у чергу за квитками, причому m з них мають лише по банкноті вартістю 20 гривень, а решта n мають лише по банкноті вартістю 10 гривень. Вартість квитка на дитячий сеанс складає 10 гривень. На початку роботи в касі є p банкнот вартістю по 10 гривень.

Завдання
Створити програму cash.*, яка визначить кількість способів надходження банкнот у касу таким чином, щоб жодна дитина не чекала на здачу, або лишок від ділення цієї кількості на певне натуральне число r.

Вхідні дані
Вхідний файл містить натуральні числа m, n і невід’ємні цілі числа p, r: m ≤ n + p; m + n ≤ 32767; p ≤ 32767; r < 10⁹.

Вихідні дані
Вихідний файл має містити лише одне число:

• при r = 0 — кількість різних послідовностей банкнот по 10 і 20 гривень, при яких жодній дитині не доведеться чекати здачі (вхідні дані гарантують, що у цьому випадку вказана кількість менша від 10¹⁸);

• при r > 0 — лишок від ділення на r такої кількості.

Приклади

Пояснення до перших двох прикладів
(10, 10, 10, 20, 20), (10, 10, 20, 10, 20), (10, 10, 20, 20, 10), (10, 20, 10, 20, 10), (10, 20, 10, 10, 20) — вичерпний перелік прийнятних послідовностей надходження банкнот у касу, у якій на початку роботи немає нічого, а біля каси зібралося 5 дітей з трьома банкнотами по 10 гривень і двома банкнотами по 20 гривень.

6. Гра (автор Олександр Рудик)

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

Марися й Орися грають у таку гру. Скінченну кількість фішок розташовано в ряд i занумеровано послідовними натуральними числами, починаючи з 1. Два гравці по черзі забирають довільну натуральну кількість фішок від 1 до певного натурального g, розташованих поруч. Інакше кажучи, номери забраних за один хід фішок — послідовні натуральні числа. Переможцем вважають того, хто зробить останній хід.

Завдання
Створіть програму game.*, яка для довільної позиції гри визначає всі виграшні ходи — такі ходи, що гарантують виграш (за умови правильного продовження гри зі свого боку) незалежно від ходів суперника.

Вхідні дані
Вхідний файл містить 2 рядки. У першому рядку — натуральне число g у межах від 2 до 9. У другому рядку записано у порядку зростання натуральні номери наявних фішок, які менші за 256 (щонайменше 7 чисел).

Вихідні дані
Вихідний файл має містити g рядків, кожний з яких закінчується ознакою кінця рядка. J-ий рядок вихідного файлу має містити у довільному порядку номери фішок, забравши які разом з наступними сусідніми (j – 1) фішкою гравець робить виграшний хід з позиції, заданої вхідними даними. Якщо таких ходів немає, то відповідний рядок вихідного файлу порожній. Зайвими пропусками при перевірці буде знехтувано.

Приклади