print1587. Марсианский заголовок

printМарсианский заголовок

Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Источник: http://imcs.dvgu.ru/cats/ Весенний турнир, 2011
loading