print1955. Кондукторы

printКондукторы

Ограничения: время – 300ms/600ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Каждый день на линию одного из автобусных маршрутов выходит `K` (`1\ ≤\ K\ ≤\ 50`) машин, на каждой из которых работает кондуктор. Перед началом работы кондукторы получают по рулону автобусных билетов. Все билеты пронумерованы шестизначными числами. Каждый рулон состоит из 1000 билетов с номерами от ###000 до ###999, то есть три первых цифры номера билетов из одного рулона совпадают. Кондукторы получают рулоны с последовательными номерами билетов. Например, если первый кондуктор получает рулон с билетами 000000–000999, то второй получит рулон с билетами 001000–001999, третий 002000–002999 и так далее…
Получив рулон билетов, каждый кондуктор пересчитывает, сколько из них "счастливые". "Счастливым" считается билет, у которого сумма цифр, стоящих на чётных местах, совпадает с суммой цифр, стоящих на нечётных местах. Например, билет с номером 112233 является "счастливым" (`1+2+3=1+2+3`), а билет с номером 321213 — нет (`3+1+1≠2+2+3`).
Для каждого из `K` кондукторов известно, сколько счастливых билетов он насчитал в своём рулоне. Требуется определить, какие номера билетов в рулоне у первого кондуктора.
Первая строка входного файла содержит целое число `K` — число автобусов, вышедших на маршрут. Вторая строка содержит `K` целых чисел из диапазона `[0;\ 1000]`, разделённых пробелами — количество "счастливых" билетов у кондукторов: первого, второго, …, `K`-го.
Выведите в выходной файл одно целое число — номер рулона первого кондуктора. Номером рулона будем считать первые 3 цифры номеров билетов рулона без ведущих нулей. Если решений несколько, требуется вывести минимальное из них. Если решений нет, требуется вывести число `-1`.

Пример ввода 1

3
75 75 73

Пример вывода 1

4

Пример ввода 2

4
28 36 45 55

Пример вывода 2

30

Пример ввода 3

1
0

Пример вывода 3

-1
Источник: XVI межвузовская олимпиада по программированию, Вологда, 2013
loading