1. Хеш-функція (автор Дмитро Кордубан)

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

Нехай X = x₁ x₂ … x_n — послідовність символів довжини n, що складається з малих літер латиниці. Позначимо через X_ij = x_i x_{i + 1} … x_j підпослідовність, що містить усі її символи з i-го по j-ий.

Довільну таку послідовність символів X можна ототожнити із числом, використавши запис у системі числення з основою 26:

Тут N(a) = 0, N(b) = 1, N(c) = 2, ... , N(d) = 25 — порядковий номер літери в латиниці, починаючи з нуля. Для довільних X — не порожньої послідовності і h — натурального числа означимо таку функцію: HF(X, h) — це остача від ділення N(X) на h. Вам потрібно дослідити поведінку функції HF.

Завдання
Дано послідовність X довжини n, що містить лише малі літери латиниці, та натуральне число h. Розглянемо всі можливі (у сенсі різних індексів i та j) її непорожні підпослідовності X_ij і значення HF(X_ij, h), що їх набуває функція на цих підпослідовностях. Вам потрібно визначити, скільки разів функція HF набула значення 0, скільки разів набула значення 1, … , скільки разів набула значення h – 1.

Вхідні дані
Перший рядок вхідного файлу містить ціле число n (0 ≤ n ≤ 5000) і натуральне число h (h ≤ 10000), розділені пропуском.

Другий рядок містить X — послідовність n малих літер латиниці. Жодних інших символів у другому рядку немає (крім ознаки кінця рядка).

У 30% вхідних файлів n ≤ 100.

Вихідні дані
Вам потрібно вивести до вихідного файлу h чисел. Першим виведіть кількість підпослідовностей X, на яких функція HF(X, h) набуває значення 0. Другим — кількість підпослідовностей X, на яких функція HF(X, h) набуває значення 1. Аналогічно, k-им — кількість підпослідовностей X, на яких функція HF(X, h) набуває значення k – 1.

Приклад

Пояснення до прикладу
В прикладі підпослідовності X₁₁ та X₂₂ вважають різними, бо вони починаються з різних індексів, і враховуються окремо, незважаючи на їхній збіг як рядків.

HF(X₁₁, 5) = 1,
HF(X₂₂, 5) = 1,
HF(X₃₃, 5) = 2,
HF(X₁₂, 5) = 2,
HF(X₂₃, 5) = 3,
HF(X₁₃, 5) = 4.

2. Кур’єри (автор Андрій Гриненко)

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

У місті Х є пряма вулиця Товстунів. Всі її мешканці, за дивним збігом обставин, дуже люблять добряче попоїсти. Компанія ННС («Нагодуємо навіть слона») вирішила заробити на цьому гроші. Вона розгорнула широку мережу доставки їжі замовникам. На вулиці одночасно й постійно перебувають N кур'єрів. Після отримання замовлення компанією продукти доставляє кур’єр, що перебував у момент отримання замовлення найближче до будинку замовника. Вважати, що такий кур'єр завжди єдиний і доставка ним замовлення відбувається миттєво. Надалі кур'єр залишається чекати наступного замовлення вже на цьому новому місці.

Завдання
Визначити сумарну відстань, яку пройдуть усі кур'єри при виконанні всіх замовлень.

Вхідні дані
Перший рядок містить два цілих числа:
N (2 ≤ N ≤ 100 000) — кількість кур'єрів;
M (0 ≤ M ≤ 100 000) — кількість замовлень.

Другий рядок містить N натуральних чисел X₁, X₂, … , X_N. Тут X_i — координата почат­кового положення i-го кур'єра на вулиці Товстунів, 1 ≤ X_i ≤ 1 000 000 000.

Третій рядок містить M натуральних чисел Y₁, Y₂, ... , Y_M. Тут Y_j — координата будинку j-го замовника з вулиці Товстунів, 1 ≤ Y_j ≤ 1 000 000 000.

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

Приклади

3. Робочий календар (автор Володимир Ткачук)

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

На планеті Олімпія місяць триває N тижнів, а в кожному тижні M днів. Пересічний мешканець Олімпії сам формує свій робочий графік, але у зв’язку з магнітними бурями одні дні сприятливі для його роботи, а інші ні. У мешканця є календар на місяць, у якому для кожного дня написано «число сприятливості». Це число вказує на те, наскільки відповідний день сприятливий для роботи.

Робочий графік складається з довільної кількості дводенних змін. Другий день кожної зміни завжди за календарем або наступний після першого дня, або саме через тиждень після першого дня. Можна розпочинати нову робочу зміну, не закінчивши попередні. Кожен день місяця може належати не більше, ніж одній зміні. Всі зміни потрібно завершити до кінця місяця.

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

Вхідні дані
В першому рядку вхідного файла записано два натуральних числа через прогалину: N і М (1 ≤ N ≤ 100, 1 ≤ M ≤ 10). Далі у файлі записано календар: N рядків по M цілих чисел у кожному рядку. i-е число j-го рядка — це число сприятливості i-го дня j-го тижня календаря. Кожне таке число є цілим і за абсолютним значенням (модулем) не перевищує 100.

Вихідні дані
Вихідний файл має містити лише одне ціле число — максимально можливе сумарне число сприятливості для робочих днів жителя планети Олімпія.

Приклад

Пояснення до прикладу
Найкращий робочий графік виглядає так: перша робоча зміна — перший день першого тижня і перший день другого тижня, друга робоча зміна — другий і третій дні першого тижня, третя робоча зміна — четвертий день другого тижня і перший день третього тижня. Сумарне число сприятливості дорівнює 1 + 2 + 3 + 3 + 5 + (–3) = 11.

4. Симетричні послідовності (автор Юрій Знов’як)

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

Останнім часом Петрик захопився послідовностями. Петрику дуже хочеться отримати з заданої послідовності симетричну послідовність. Послідовність (a₁, a₂, …, a_N) називають симетричною, якщо a_j = a_{N – j + 1} при всіх j = 1, 2, 3 , …, N. Наприклад, послідовність (10, 20, 30) — не симетрична, а послідовності (10, 20, 10) і (10, 20, 20, 10) — симетричні. Послідовність з одного елементу завжди симетрична.

За один хід Петрик може замінити два суміжні числа на їхню суму. Інакше кажучи, за один хід з послідовності: (a₁, a₂, … , a_i – 1, a_i, a_i + 1, a_{i + 2}, …, a_N), можна отримати послідовність (a₁, a₂, … , a_i – 1, a_i + a_i + 1, a_{i + 2}, …, a_N).

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

Завдання
Для заданої початкової послідовності знайдіть найменшу кількість ходів, якими можна дану послідовність перетворити на симетричну.

Вхідні дані
У першому рядку файлу symmetry.in задано натуральне число N — кількість чисел у початковій послідовності (N ≤ 200 000).

Другий рядок містить послідовність N натуральних чисел — члени цієї послідовності. Сума всіх членів послідовності не перевищує 2 000 000 000.

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

Приклади

Пояснення до прикладів
У першому тесті нам задано набір (1, 2, 2, 4, 5). Існує послідовність з 2-х ходів, якою можна цей набір перевести в симетричний набір: (1, 2, 2, 4, 5) → (1, 4, 4, 5) → (5, 4, 5). Але не існує коротшої послідовності, якою можна було б отримати симетричний набір.

У другому тесті нам задано уже симетричний набір, тому відповідь 0.

У третьому тесті за 1 хід можна об’єднати другий і третій елементи, отримавши симетричну послідовність (1, 7, 7, 1).

5. Садок вишневий (автор Данило Мисак)

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

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

Вхідні дані
Перший рядок вхідного файлу містить натуральне число n (1 ≤ n ≤ 10 000) — кількість дерев у садку Генд-Альфа.

Другий рядок містить 2n чисел — n пар координат дерев відносно певної точки площини садка. Всі координати — цілі числа, що за модулем не перевищують 10 000. Кожне дерево у вхідному файлі описується рівно один раз, і два різних дерева не можуть рости в одному і тому самому місці.

Вихідні дані
Єдиний рядок вихідного файлу має містити чотири числа:

• перші два — координати точки A;

• останні два — координати точки B, відмінної від A, такі, що пряма AB (як паркан) задовольняє умові задачі.

Всі координати мають бути цілими числами, що за модулем не перевищують 2 000 000 000.

Якщо неможливо знайти дві такі різні точки A та B, необхідно вивести рядок, що містить чотири нулі: «0 0 0 0».

Приклади

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

6. Острови (автор Юрій Знов’як)

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

Далеко в океані знаходиться держава, розташована на архіпелагу з N островів, (N ≤ 100 000). Між деякими з островів збудовано мости. Між довільними двома островами існує не більше одного маршруту, в якому кожен міст проходять лише один раз вздовж цього маршруту. Геологічні дослідження виявили, що майже усі острови здатні приносити чималий зиск від видобутку кольорових металів у копальнях. На жаль, інженерні обрахунки показали, що міст може зруйнуватись, якщо він сполучає острови, на яких одночасно працюють шахти. Отже, якщо по обидва боки мосту працюють копальні, то цей міст необхідно буде закрити. Закриття мостів створює багато незручностей, тому держава виділяє кошти, щоб упоратися з незадоволенням мешканців.

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

Вхідні дані
Перший рядок файлу islands.in містить два натуральних числа: N — кількість островів і M — кількість мостів.

Другий рядок містить послідовність N натуральних чисел: j-те число — прибуток, який буде приносити шахта на острові j.

В наступних M рядках задано опис мостів. В кожному з цих рядків — три числа — номери островів, які з’єднуються цим мостом (острови нумерують натуральними числами від 1 до N), а також штраф за закриття даного мосту. Прибуток від шахти і штраф за закриття мосту — натуральні числа, що не перевищують 10 000.

Вихідні дані
Сформуйте відповідь до задачі у файл islands.out за таким принципом:

• у перший рядок файлу виведіть максимальний зиск;

• у другий рядок виведіть K — кількість островів у вашому наборі. Після чого виведіть K номерів островів без повторення, на яких Ви радите почати видобуток цінних металів.

Оцінювання
За правильну величину зиску вам буде зараховано 30% балів за відповідний тест. Якщо ваш набір островів виявиться одним з оптимальних, то вам буде зараховано 70% балів за відповідний тест. Бали за обидві частини задачі нараховують незалежно. Не менш, ніж у 40% тестів N ≤ 1 000.

Приклади