ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Зима — 2019» > задача:


H. Макс и новогодние открытки

Тренировочный турнир сезона «Зима — 2019»

Старт: 01.янв.2019 в 00:00:00
Финиш: 31.янв.2019 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Площадь и периметр
• B. Макс и приготовление супа
• C. Макс и простая задача
• D. Макс и сооружение города
• E. Никита и интервью
• F. Макс и поиск закусочных
• G. Макс и нестандартная спираль
• H. Макс и новогодние открытки
• I. Макс и распознавание фигур
• J. Макс и муниципальная задача
• K. СириусЛяндия и страсть к оливкам
• P1. Подбор отрезков ленты для од...
• P10. Бегущие огни в диагоналях
• P2. Подбор отрезков ленты для дв...
• P3. Подбор кусков ленты для ква...
• P4. Бегущий огонь слева направо в...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и новогодние открытки
Макс и новогодние открытки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

На каждой открытке есть $$$N$$$ строк для записей. Макс хочет, чтобы поздравление выглядело красивым, а для этого нужно выполнить ряд условий:

  • Поздравление должно занимать не более $$$N$$$ строк;
  • Слова должны размещаться на строке целиком, переносить их не допускается;
  • Между словами должно быть по одному пробелу, на концах строк пробелов быть не должно;
  • Ширина самой длинной из получившихся строк должна быть как можно меньше (чтобы буквы получились большими).

Помогите Максу разбить его поздравление на строки наиболее красивым образом.

Входные данные

Первая строка содержит последовательность $$$S$$$ ($$$1 \le |S| \le 10^5$$$), состоящую из строчных латинских букв и пробелов, — текст поздравления. Текст не содержит двух пробелов подряд, не начинается и не заканчивается пробелом.

Вторая строка содержит целое число $$$N$$$ — количество строк для текста на открытках.

Выходные данные

Выведите одно целое число — минимальную ширину строк, при которой можно записать текст поздравления на открытках, не перенося слова и использовав не более $$$N$$$ строк.

Примеры

Входные данные
happy new year and merry xmas
4
Выходные данные
9
Входные данные
wish you good luck in all contests
3
Выходные данные
12

Для отправки решений необходимо выполнить вход.

www.contester.ru