АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

870. Куча камней - 2

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Имеется N камней разного веса.
Требуется разложить их на две кучки так, чтобы разница весов этих кучек была как можно меньше.

Исходные данные

В первой строке входного файла находится число N - количество камней (1<=N<=100).
В следующих строках располагаются N целых чисел - веса камней (в интервале от 1 до 1000). Числа разделяются пробелами и/или переводами строк.

Результат

Выведите в первой строчке одно число - минимально возможный модуль разности весов кучек.
В следующей строчке выведите через пробел N чисел 1 или 2, где 1 означает, что соответствующий камень пойдёт в 1-ю кучу, 2 - во вторую.
Если правильных решений несколько, выведите любое.

Пример

Исходные данныеРезультат
4
1 5 2 3
1
1 1 2 2

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Динамическое прогр-е, рекуррентные соотношения /
867. Куча камней - 1 870. 186. Мячик 1066. Отчёт 296. Палиндром
Задачи с соревнований / Отборочные туры ВоГУ / Отборочный тур в Рыбинск 2010 /
870. 869. Куча камней -1 (дополненная) 865. A - Число страниц в книге 866. B - Куча камней
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Динамическое программирование /
1717. 07 - Возрастающая подпоследовательность 870. 901. 09 - Коробки 10. 10 - Упаковка 2. 11 - Дерево поиска
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, сентябрь 2020 / Импульс-2020, ДП /
867. 07 - Куча камней - 1 870. 12. 09 - Быстрое питание
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.