НачалоПодразделы
Другие разделы
Дата и время
22/11/2024 09:53:35
1587. Марсианский заголовок
Марсианский заголовок
Полный переборОлимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (03C) |
| 06/07/2011 | Лето 2011 - 3 (C) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Марсианский журнал решил опубликовать статью о жизни на других планетах.
Статья представляет собой строку из заглавных и строчных латинских букв.
Пробелы и знаки препинания на Марсе не используют.
По традиции, заголовок статьи должен быть непустой подстрокой её текста.
Кроме этого известно, что строчные буквы в заголовке привлекают низкорослых марсиан,
а заглавные – высокорослых.
Маркетинговый отдел журнала определил, что оптимальная доля
высокорослых читателей (и, следовательно, заглавных букв)
составляет `M` процентов.
Требуется написать программу, которая по данному тексту статьи определит
наилучший заголовок – то есть такую подстроку, процент заглавных
букв в которой как можно ближе к `M`.
Если несколько заголовков одинаково подходят,
следует выбрать самый короткий, а если и таких несколько – встречающийся
в тексте статьи как можно раньше.
Первая строка входного файла содержит целое число `M` (`1\ ≤\ M\ ≤\ 99`).
Вторая строка входного файла содержит текст статьи. Длина текста составляет от `2` до `5000` символов.
Выходной файл должен содержать одну строку – наилучший заголовок.
Пример ввода 1
50 aAb
Пример вывода 1
aA
Пример ввода 2
30 xxxxXXxxX
Пример вывода 2
xxxxXXx
Пример ввода 3
99 ab
Пример вывода 3
a
