| Автор: | А. Кленин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt |
Марсианский журнал решил опубликовать статью о жизни на других планетах. Статья представляет собой строку из заглавных и строчных латинских букв. Пробелы и знаки препинания на Марсе не используют.
По традиции, заголовок статьи должен быть непустой подстрокой её текста. Кроме этого известно, что строчные буквы в заголовке привлекают низкорослых марсиан, а заглавные — высокорослых.
Маркетинговый отдел журнала определил, что оптимальная доля высокорослых читателей (и, следовательно, заглавных букв) составляет M процентов.
Требуется написать программу, которая по данному тексту статьи определит наилучший заголовок — то есть такую подстроку, процент заглавных букв в которой как можно ближе к M.
Если несколько заголовков одинаково подходят, следует выбрать самый короткий, а если и таких несколько — встречающийся в тексте статьи как можно раньше.
Первая строка входного файла содержит целое число M.
Вторая строка входного файла содержит текст статьи.
Выходной файл должен содержать одну строку — наилучший заголовок.
1 ≤ M ≤ 99
Длина текста составляет от 2 до 5000 символов.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|