Задача Краватки (CRAVAT)

На відкритті «Турніру Чемпіонів» перед учасниками і гостями збирається виступити N членів журі. Щоб показати єдність всіх представників журі, було прийнято рішення надіти їм краватки одного кольору. Все краватки зберігаються в скрині, яка знаходиться в темній кімнаті, та кожна з них має один з M кольорів. У кімнату можна увійти тільки один раз, вийняти зі скрині деяку кількість краваток і винести їх з кімнати. Потрібно визначити мінімальну кількість краваток, яку необхідно вийняти зі скрині, щоб серед них гарантовано було не менше N краваток одного кольору.

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

Програма зчитує зі стандартного пристрою уведення два рядки. Перший рядок містить два цілих числа N та M (1≤N≤10⁶, 1≤M≤10⁴). У другому рядку задано M чисел, кожне з яких означає кількість краваток відповідного кольору. Всі числа цілі невід’ємні та не перевищують 10⁹.

Програма повинна вивести на стандартний пристрій виведення одне число – мінімальну кількість краваток, яку необхідно вийняти із скрині. Якщо гарантувати наявність N краваток одного кольору не можливо, необхідно вивести число −1.

Пример:

Задача Кодовий замок (CODELOCK)

На скарбницю із золотом дядька Скруджа недавно встановили новий кодовий замок унікальної конструкції. Зовні він виглядає як кільце, на якому розміщено 8 однакових барабанів з цифрами від 0 до 9, що рівномірно розташовані по колу. На барабанах за цифрою i (0≤i≤8) розміщена цифра i+1, за цифрою 9 наступною є цифра 0.

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

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

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

Програма зчитує зі стандартного пристрою введення два набори по 8 цифр кожен. Між цифрами всередині набору немає розділювачів, між наборами – пропуск. Перший набір цифр показує початкове положення барабанів, починаючи з верхнього. Другий – положення барабанів (починаючи з верхнього), яке відкриває замок.

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

Приклад:

Задача Станції (STATIONS)

Керівництво Дуже Великої Залізниці (ДВЗ) вирішило встановити нову систему оплати за проїзд. ДВЗ являє собою відрізок прямої, на якій послідовно розміщені N станцій. Планується розбити їх на M неперервних зон, що слідують підряд, таким чином, щоб кожна зона містила хоча б одну станцію. Оплату проїзду від станції i до станції k необхідно встановити рівною 1+|z_i−z_k|, де z_i і z_k ‑ номери зон, яким належать станції i та k відповідно.

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

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

Програма зчитує зі стандартного пристрою введення N рядків. Перший рядок містить два цілих числа N та M (1≤M≤N≤1000). Другий – одне число, що означає кількість пасажирів, що їдуть від станції 1 до станції 2. Третя – два числа, що означають кількість пасажирів, що їдуть від станції 1 до станції 3 та від станції 2 до станції 3, відповідно. І так далі. В N-ому рядку міститься N−1 число, i-е з них визначає кількість пасажирів від станції i до станції N. Кількість пасажирів для кожної пари станцій дано з урахування руху в обидві сторони. Всі числа цілі невід’ємні та не перевищують 10000.

Програма повинна вивести на стандартний пристрій виведення єдине ціле число – шукану максимальну денну виручку.

Пример: