АВТ
Язык:

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

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

69. Пустоты в кубе

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

Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моношрифтным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.

Назовем пустотой последовательность пробелов между соседними словами в строке, а также от начала строки до первого слова. Проблема стоящая перед жюри, состоит в том, что научный руководитель сборов Владимир Михайлович Кирюхин отказывается читать текст, если сумма кубов длин пустот по всем строкам не минимальна. Помогите жюри расположить отчет на листе бумаги так, чтобы В.М. Кирюхин согласился его прочесть и утвердить результаты сборов.

Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов и/или символов перевода строки) любой другой пробельной последовательностью.

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

Первая строка входного файла содержит целое число S (1<=S<=80) В последующих строках записан отчет, содержащий не более 500 слов. Длина каждой строки не превосходит 250 символов, а длина каждого слова не превосходит S.

Результат

Вывести в первую строку выходного файла минимально возможную сумму кубов пустот по всем строкам. В последующие строки следует вывести искомое расположение текста на листе бумаги.

Пример

Исходные данные
30
Победители летних учебно-тренировочных сборов по информатике 1997 г.: 
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров,
Андрей Лопатин.
Результат
325
     Победители     летних
учебно-тренировочных сборов по
 информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин. 

Комментарии

Заметим, что если мы решили поместить несколько слов отчетов на одной строке листа, то располагать их нужно так, чтобы размеры пустот были равны или отличались друг от друга не более чем на единицу (это утверждение легко следует из выпуклости функции ).


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Тренировки ВоГУ / Динамическое программирование /
67. Восстановление скобок 69. 68. Уравнение с пропущенными цифрами
Учебные курсы / Задачи с olympiads.ru /
775. 241 - Сжатие текста 69. 776. 249 - Шифровка 2 778. 252 - Дейкстра 779. 253 - Заправки
 
время генерации 0.141 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.