Задача D. Клумбы
Задачу добавил: alef
Успешно сдано решений: 101
Вдоль аллеи, по которой любит кататься Кеша, высаживают цветы в клумбы. Всего вдоль аллеи расположено n клумб. Для каждой клумбы известно, какое количество цветов на нее должно быть высажено — f1, f2, ..., fn.
Эту работу поручили бригаде из n человек. Известно, что каждый работник на высаживание одного цветка тратит ровно 2 единицы времени. Бригадир может назначить либо одного работника на одну клумбу, либо двух работников на 2 расположенные подряд клумбы.
Если работники трудятся в паре, они перейдут работать на вторую клумбу одновременно и только после того, как на первую клумбу будет высажен последний цветок.
Работа считается выполненной, когда все цветы будут высажены во все клумбы. Ваша задача — определить, за какое минимально возможное время работа может быть выполнена.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество клумб (и работников).
Во второй строке содержится n целых чисел f1, f2, ..., fn (1 ≤ fi ≤ 105, i = 1, 2, ..., n), где fi — количество цветов, которое должно быть высажено в клумбу #i. Клумбы занумерованы согласно их расположению вдоль аллеи.
В первой строке выведите минимально возможное время, спустя которое цветы могут быть высажены во все клумбы.
Во второй строке выведите последовательность, состоящую из n единиц и двоек: на месте #i должна стоять 1, если на эту клумбу назначен один работник, и 2, если на эту клумбу назначено двое работников.
Если существует несколько вариантов ответа, выведите любой.
7
6 10 3 7 5 10 4
14
1 2 2 1 1 2 2
7
3 10 8 8 6 10 5
16
2 2 1 1 2 2 1
В первой группе тестов (3 - 52) баллы начисляются за каждый пройденный тест (до 50 баллов).
Во второй группе тестов (53 - 70) баллы (50) начисляются при условии прохождения всех тестов группы.