Codeforces Beta Round 64 |
---|
Закончено |
Маленький морж Клычок, как и все современные моржи, любит общаться с помощью SMS. Однажды он столкнулся с проблемой, что при отправке больших текстов они разделяются на части по n символов (размер одного SMS сообщения), и разрываются целые предложения или даже слова!
Клычку это не понравилось, и перед ним встала задача разбить текст на сообщения самостоятельно таким образом, чтобы ни одно предложение не было разбито на части при отправке, и количество SMS сообщений для отправки было бы минимальным. Если два подряд идущих предложения находятся в разных сообщениях, то пробел между ними можно не учитывать (Клычок этот пробел не набирает).
Текст маленького моржа имеет следующий вид:
TEXT ::= SENTENCE | SENTENCE SPACE TEXT
SENTENCE ::= WORD SPACE SENTENCE | WORD END
END ::= {'.', '?', '!'}
WORD ::= LETTER | LETTER WORD
LETTER ::= {'a'..'z', 'A'..'Z'}
SPACE ::= ' '
Под SPACE следует подразумевать символ пробела.
Сколько же сообщений отправил Клычок?
В первой строке задается целое число n — размер одного сообщения (2 ≤ n ≤ 255). В следующей строке находится сам текст. Длина текста не превышает 104 символов. Гарантируется, что текст удовлетворяет описанному выше формату. В частности, из этого следует, что текст не пуст.
В первой и единственной строке выведите количество SMS сообщений, которое потребуется Клычку. Если разбить текст невозможно, выведите "Impossible" без кавычек.
25
Hello. I am a little walrus.
2
2
How are you?
Impossible
19
Hello! Do you like fish? Why?
3
Рассмотрим третий пример. Текст будет разбит на 3 сообщения: "Hello!", "Do you like fish?" и "Why?".
Название |
---|