Задача Галстуки (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.

Программа должна вывести на стандартное устройство вывода единственное целое число ‑ искомую максимальную дневную выручку.

Пример: