Клумбы
(Время: 1 сек. Память: 16 Мб Сложность: 38%)
На школьной аллее в ряд расположены N клумб. В начале лета на клумбы школьникам на-до высадить по fi цветов. На посадку каждого цветка каждому ученику требуется по 2 минуты. Для выполнения этой работы приглашены N учеников и за каждым из них закреплена клумба. Для более быстрого окончания работ двум ученикам, закреплённым за соседними клумбами, можно вначале засадить одну клумбу, потом другую. При этом вторую клумбу эти ученики начинают засаживать только после посадки всех цветов на первую клумбу. Например, если на соседние клумбы надо посадить 5 и 2 цветов, то школьникам лучше объединиться, тогда они справятся с работой за 8 минут (6 минут на первую грядку и 2 минуты на вторую). При этом первый ученик высаживает на первой клумбе 3 цветка за 6 минут, а второму остаётся 2 цветка и 2 минуты он ждёт первого. Если бы они засаживали каждый свою клумбу, то потребовалось бы 10 минут (10 первому и 4 второму).
Помогите школьникам как можно быстрее справиться с порученным заданием.
Входные данные
В первой строке входного файла INPUT.TXT записано одно натуральное число N – количество клумб и количество учеников (1 ≤ N ≤ 105). Во второй строке через пробел заданы N натуральных чисел – количество цветов на клумбах. Эти числа не превышают значения 105.
Выходные данные
В первую строку выходного файла OUTPUT.TXT нужно вывести одно натуральное число – время выполнения работы школьниками. Во вторую строку нужно вывести через пробел N чисел 1 или 2. Если i-ю грядку засаживает один ученик, то вывести 1, иначе 2. При этом количество учеников, которые засаживают по одной клумбе, должно быть максимально возможным. Если существует несколько таких решений, выведите любое.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
1 1 | 2
1 1 |
| 2 | 2
2 5 | 8
2 2 |
| 3 | 3
2 2 1 | 4
1 1 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
