| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 87 | 67 | 55 | 82.090% |
Давным-давно, в далекой-далекой галактике учились в одной школе два закадычных друга --- Вася и Петя. Они были верными товарищами, не раз выручавшими друг друга в трудную минуту из самых безвыходных ситуаций. Однако речь сейчас пойдет не об этом, а о редчайшем случае --- ссоре между двумя героями нашего повествования.
В конце седьмого класса Вася увлекся программированием и написал свой текстовый редактор. Естественно, Петя тут же захотел его испытать. Несложно представить насколько велико было его разочарование, когда обнаружилось, что Васина программа корректно работает только при использовании экрана с тем же разрешением, как и у него дома. Вася оправдывал это тем, что оптимальный вывод текста на экран --- штука сложная, поэтому универсальным образом сделать это невозможно. Петя же заявил, что хоть программист он и никудышный, но легко решит эту задачу.
К сожалению, программирует Петя действительно из рук вон плохо, поэтому он просит вас помочь ему в написании решения.
На вход дан текст. Назовем словом последовательность символов, ограниченную пробелами, началом или концом текста. Обратите внимание, что в данной задаче знаки препинания считаются частью слова. Требуется разбить текст на строки так, чтобы длина каждой из них была не более $k$ символов, при этом их общее количество было минимальным. Порядок слов и сами слова менять запрещено.
Первая строка входного файла содержит натуральное число $k$ --- максимально допустимая длина строки (1ドル \le k \le 100$). Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов <<,>> (запятая), <<.>> (точка), <<!>> (восклицательный знак) и <<?>> (вопросительный знак). Размер входного файла не превышает 50000ドル$ байтов.
Выведите заданный во входном файле текст так, чтобы длина каждой строки была не более $k$ символов, а количество строк было минимально возможным. Гарантируется, что задача имеет решение. В случае если решение не единственно, выведите любое из них.
Слова в выходном файле должны быть отделены друг от друга пробелами и/или переводами строк.
22 This is a sample text!
This is a sample text!
12 This is a sample text!
This is a sample text!