Задача Краватки (CRAVAT)
На відкритті «Турніру Чемпіонів» перед учасниками і гостями збирається виступити N членів журі. Щоб показати єдність всіх представників журі, було прийнято рішення надіти їм краватки одного кольору. Все краватки зберігаються в скрині, яка знаходиться в темній кімнаті, та кожна з них має один з M кольорів. У кімнату можна увійти тільки один раз, вийняти зі скрині деяку кількість краваток і винести їх з кімнати. Потрібно визначити мінімальну кількість краваток, яку необхідно вийняти зі скрині, щоб серед них гарантовано було не менше N краваток одного кольору.
Формат введення/виведення:
Програма зчитує зі стандартного пристрою уведення два рядки. Перший рядок містить два цілих числа N та M (1≤N≤106, 1≤M≤104). У другому рядку задано M чисел, кожне з яких означає кількість краваток відповідного кольору. Всі числа цілі невід’ємні та не перевищують 109.
Програма повинна вивести на стандартний пристрій виведення одне число – мінімальну кількість краваток, яку необхідно вийняти із скрині. Якщо гарантувати наявність N краваток одного кольору не можливо, необхідно вивести число −1.
Пример:
|
Введення |
Виведення |
|
3 3 4 5 6 |
7 |
Задача Кодовий замок (CODELOCK)
На скарбницю із золотом дядька Скруджа недавно встановили новий кодовий замок унікальної конструкції. Зовні він виглядає як кільце, на якому розміщено 8 однакових барабанів з цифрами від 0 до 9, що рівномірно розташовані по колу. На барабанах за цифрою i (0≤i≤8) розміщена цифра i+1, за цифрою 9 наступною є цифра 0.
Дозволяється обертати тільки той барабан, який в даний момент знаходиться у верхній частині кільця. При цьому саме кільце можна повертати за годинниковою або проти годинникової стрілки таким чином, щоб розмістити зверху інший барабан. Замок відкривається тільки у випадку встановлення на барабанах певної послідовності цифр.
За одну секунду дядя Скрудж може повернути верхній барабан на одну позицію в будь-яку сторону (тобто перейти до наступної або попередньої цифри на цьому барабані) або повернути кільце на один барабан за годинниковою або проти годинникової стрілки для зміни барабана у верхній частині кільця. Зазвичай, дядя Скрудж прагне попасти до свого золота якомога швидше, а тому він зацікавлений відкрити замок за найменшу кількість операцій. Ваша задача полягає у тому, щоб визначити цю кількість операцій.
Формат введення/виведення:
Програма зчитує зі стандартного пристрою введення два набори по 8 цифр кожен. Між цифрами всередині набору немає розділювачів, між наборами – пропуск. Перший набір цифр показує початкове положення барабанів, починаючи з верхнього. Другий – положення барабанів (починаючи з верхнього), яке відкриває замок.
Програма повинна вивести на стандартний пристрій виведення одне число – мінімально можливу кількість операцій, що необхідні для відкриття замка. Якщо отримати друге число з першого неможливо, вивести число −1.
Приклад:
|
Введення |
Виведення |
|
12345678 23456789 |
3 |
|
12345678 11111111 |
29 |
Задача Станції (STATIONS)
Керівництво Дуже Великої Залізниці (ДВЗ) вирішило встановити нову систему оплати за проїзд. ДВЗ являє собою відрізок прямої, на якій послідовно розміщені N станцій. Планується розбити їх на M неперервних зон, що слідують підряд, таким чином, щоб кожна зона містила хоча б одну станцію. Оплату проїзду від станції i до станції k необхідно встановити рівною 1+|zi−zk|, де zi і zk ‑ номери зон, яким належать станції i та k відповідно.
Відома кількість пасажирів, які відправляються за день з кожної станції на кожну іншу. Напишіть програму, що визначає, яку максимальну денну виручку можна отримати за новою системою при оптимальному розбитті на зони.
Формат введення/виведення:
Програма зчитує зі стандартного пристрою введення N рядків. Перший рядок містить два цілих числа N та M (1≤M≤N≤1000). Другий – одне число, що означає кількість пасажирів, що їдуть від станції 1 до станції 2. Третя – два числа, що означають кількість пасажирів, що їдуть від станції 1 до станції 3 та від станції 2 до станції 3, відповідно. І так далі. В N-ому рядку міститься N−1 число, i-е з них визначає кількість пасажирів від станції i до станції N. Кількість пасажирів для кожної пари станцій дано з урахування руху в обидві сторони. Всі числа цілі невід’ємні та не перевищують 10000.
Програма повинна вивести на стандартний пристрій виведення єдине ціле число – шукану максимальну денну виручку.
Пример:
|
Введення |
Виведення |
|
3 2 200 10 20 |
440 |