ВКОШП: ВКОШП 2019

Различные статьи, научные тексты, и даже условия к задачам олимпиад чаще всего создаются с использованием систем вёрстки TeX и LaTeX, исходно разработанных Дональдом Кнутом и Лэсли Лампортом.

В этих системах используются специальные макросы, которые позволяют вводить специальные символы, которых нет на клавиатуре. Например, если написать несколько минусов подряд, то они преобразуются системой в тире разной длины. Из-за этого, когда необходимо получить в документе строку из нескольких минусов подряд, приходится идти на специальные ухищрения. Для того, чтобы группа подряд идущих минусов не воспринималась как макрос, используются фигурные скобки. По аналогии с многими языками программирования, например, C++, фигурные скобки используются в TeX для группировки блоков символов. Последовательность фигурных скобок должна образовывать правильную скобочную последовательность. А именно, если удалить из строки все символы кроме фигурных скобок, а затем заменить открывающую фигурную скобку « { » на \(+1\), а закрывающую « } » на \(-1\), то сумма всех элементов получившейся последовательности должна быть равна \(0\), а сумма любого префикса получившейся последовательности должна быть неотрицательна.

Чтобы последовательность минусов не заменялась на тире, между любыми двумя подряд идущими минусами должна располагаться хотя бы одна фигурная скобка.

Отметим, что группа подряд идущих плюсов, в отличие от минусов, не соответствует никакому макросу и никаких условий на два подряд идущих плюса не накладывается.

Рассмотрим строку \(s\), состоящую из плюсов и минусов. Необходимо добавить в неё минимальное количество фигурных скобок с соблюдением описанных правил, чтобы никакие два минуса не шли подряд. Будем называть полученные строки защищёнными строками для \(s\).

Например, для строки « ++-{-} » оптимальными являются пять защищённых строк: « ++-{-} », « ++-{}- », « ++{-}- », « +{+-}- », « {++-}- ».

Строки выше перечислены в лексикографическом порядке : они упорядочены по первому символу, при равном первом символе — по второму, и так далее, с учётом порядка « + »\(\strut<\strut\)« - »\(\strut<\strut\)« { »\(\strut<\strut\)« } ».

Рассмотрим все минимальные по длине строки, которые могут быть получены из \(s\) добавлением фигурных скобок, с соблюдением описанных правил. Требуется найти и вывести \(k\)-ю в лексикографическом порядке из этих строк, или сказать, что \(k\) слишком велико.