Числовий многокутник (Npolygon)

Якось до Дім Дімича в гості завітав його друг Васька. Вони разом готувалися до олімпіади з усного рахунку, а тому постійно додавали всі числа, які тільки бачили. Сімка вирішила допомогти друзям та намалювала N-кутник, до кожної з вершин якого приписала число. Васька, побачивши зображення, запропонував додавати не всі числа, а тільки k (1 < k < N), що йдуть підряд за годинниковою стрілкою. Дім Дімич запропонував не всім вершинам многокутника приписувати одне й те саме число. Друзі з подивом помітили, що при цьому іноді суми отримуються однаковими для всіх вершин. Вони позначили S(i,k) як суму чисел в k послідовних вершинах, починаючи з вершини i. Друзі вирішили знайти максимальне k, при якому всі такі суми рівні.

Формат введення-виведення:

Програма Npolygon зчитує з клавіатури (стандартного пристрою введення) єдине ціле число N кількість кутів N-кутника (3 ≤ N ≤ 10¹⁵).

Програма Npolygon виводить на екран (стандартний пристрій виведення) єдине число k (1 < k < N) – максимальну кількість чисел, що розташовані підряд за годинниковою стрілкою, серед яких хоча б два різних, таких, що для всіх i S(i,k) рівні між собою. Якщо таку послідовність чисел у заданого N-кутника написати немає можливості, виведіть «-1» (без лапок).

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

Кондитерська фабрика (fixcandy)

Як і всі діти, Дім Дімич великий ласун, а тому, коли його спитали, де він хоче працювати, коли виросте, він, очевидно, відповів – виробляти цукерки. Коли ж фіксіки поцікавились, чи уявляє він, у чому буде полягати його робота, він відповів, що це не важливо, аби можна було з’їсти цукерок скільки завгодно. Сімка вирішила продемонструвати Дім Дімичу роботу на фабриці по упаковці вже готових цукерок.

Виконує упаковку фасувально-пакувальний автомат, який має N резервуарів, у кожен з яких кожну секунду потрапляє рівно одна цукерка. Цукерки пакуються рівно по k штук у коробці, а тому, як тільки в одному з резервуарів трапляється вказана кількість цукерок, вони відправляються на упаковку і резервуар стає пустим. Далі заповнення резервуару починається спочатку.

Коли Дім Дімич з’явився на фабриці, в кожному резервуарі автомата знаходилась деяка кількість цукерок. Йому доручили виготовити не менше L коробок по k цукерок, а після виконання завдання звільнити всі резервуари від цукерок, що залишилися. Сімка, почувши це, жахнулася, прекрасно розуміючи, що звільнення резервуарів перетвориться на їх поживу. А це означало, що хворі зуби Дім Дімичу забезпечені.

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

Формат введення-виведення:

Програма fixcandy спочатку зчитує з клавіатури (стандартного пристрою введення) три цілих числа N, K, L (1≤N≤10⁶, 1≤K≤10⁹, 0≤L≤10⁹). Потім зчитується N невід’ємних цілих чисел a₁, a₂ ,… a_N строго менших К – кількість цукерок у кожному з резервуарів автомата перед початком роботи.

Програма fixcandy виводить на екран (стандартний пристрій виведення) одне число – мінімальну тривалість зміни, при якій гарантовано виконано завдання і при якій Дім Дімичу доведеться з’їсти мінімальну кількість цукерок.

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

Примітка: В момент часу 0 (початок зміни) у резервуарах знаходиться (1, 1, 2) цукерок.

0 сек: (1, 1, 2)

1 сек: (2, 2, 0) => 1 упаковка

2 сек: (0, 0, 1) => 2 упаковки, всього 3

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

Пирог с фиксиками (fixpie)

Сьогодні  у Дім Дімича велике свято – матуся пече пиріг. И поки вона хазяює на кухні, Дім Дімич розважається запуском дитячого залізничного поїзда. Все було просто чудово,  аж поки не з’явився  Нолик. С його сестрою Сімкою та її подругою Шпулею знову трапилася неприємність: дівчатка розважалися на кухні і попали в пиріг, який мама вже засунула в духовку. Що робити? Потрібно ж  якось убезпечити своїх домашніх  від ковтання гвинтиків, у які перетворюються фіксики! А для того, звичайно, потрібно  з’їсти побільше пирога.

Аби  легше було ділити круглий пиріг між бажаючими поласувати, мама на пиріг нанесла N (N≤360) радіальних міток для розрізу під кутами 0.0 ≤ a₁ < a₂ < … < a_N < 360.0.  Бажаючих спробувати пиріг рівно K (2 ≤ K ≤ N).  Аби навіть у найгіршому  випадку Дім Дімич зміг з’їсти шматок побільше, йому потрібно розрізати пиріг таким чином, аби розмір самого маленького з k шматків був як можна  більшим.  Допоможіть Дім Дімичу знайти кутовий розмір L найменьшего шматка з точністю до ε = 10^-5.

Формат введення-виведення:

Програма fixpie  читає з клавіатури (стандартного пристрою введення) два цілих числа N і k – кількість відміток на пирогу  і кількість шматків, які треба отримати. Далі зчитується N чисел a₁, a₂ ,… a_N – кути, під якими нанесено радіальні мітки.

Програма fixpie виводить на екран (стандартний  пристрій виведення)  одне число – відповідь на поставлене питання.

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

Примітка: В цьому прикладі пиріг розрізали під кутами 25.5, 100.5 і 220.5, отримавши три шматка з кутовими розмірами 75.0 (шуканий шматок), 120.0 і 165.0.

Маніпулятор (manipul)

Після непорозуміння, що сталося з маніпулятором, яке налякало секретаря Лізоньку, професор Геній Євгенович вирішив його удосконалити і підключив до комп'ютера. Для управління маніпулятором він написав програму, яка представляла собою величезну таблицю А розміром NxN, що складається з нулів і одиниць, причому одиниці стояли тільки в тих комірках таблиці, у яких залишок від ділення номера рядка і номера стовпчика на деяке число М був однаковим, тобто A[row][column]=1 тільки якщо

 row% M = column% M.

Вночі в лабораторію Генія Євгеновича заглянули фіксіки і випадково пересунули на його столі магніт так, що він зіпсував практично всю інформацію на вінчестері. Дивом уціліла рівно P-1 одиниця в програмі для маніпулятора, всі інші комірки обнулились. Сімка страшенно злякалася і спробувала відновити програму. Однак їй вдалося домогтися появи всього однієї додаткової одиниці в таблиці, причому на довільному місці. Оскільки програма була безнадійно зіпсована, професор запропонував вам знайти максимальне з усіх можливих значень М для вихідної таблиці.

Формат ведення-виведення:

Програма manipul спочатку читає з клавіатури (стандартного пристрою введення) два цілих числа N і P P (2 ≤ N ≤ 10⁵; 2 ≤ P ≤ min(10⁵,N²)). Потім зчитується Р пар цілих невід'ємних чисел, що не перевищують значення N-1 - позиції збережених одиничок. Правда, невідомо, яка з цих одиниць виникла як побічний ефект після маніпуляцій Сімки.

Програма manipul виводить на екран (стандартне пристрої виведення) єдине число - максимально можливе число М для початкової таблиці. Якщо максимальне значення однозначно не визначається, необхідно вивести «-1» (без лапок). Значення М вважається можливим, якщо в програмі для маніпулятора, принаймні на Р-1 позиції, заданих у вхідних даних, буде стояти одиниця.

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

Пояснення до вхідних тестів:

У другому тесті таблиця після дії  магніту має вигляд:

10010

01010

00000

00000

00001

Для такої таблиці можливі значення М=2 и М=3. При М=3 програма має такий вигляд:

10010

01001

00100

10010

01001

Тобто одиниця в позиції 00 (1,3) була побічним ефектом.

В третьому тесті таблиця після дії  мала вигляд:

110

000

000

Для такої таблиці підходять всі цілі числа, тому відповідь «-1». Для М>1 вважається, що друга одиниця в першому  рядку – побічний ефект.