Форумы-->Форум для внеигровых тем-->
1|2
| Автор | Олимпиада по информатике. |
|---|
для Akron:
Я еще не приступил. | | Олимпиада - она для души.Настройся на правильный лад - и всё получиться! | Это довольно сложная задача. Попробую описать план решения.
Тебе придется по очереди восстанавливать скобки. То есть шаг алгоритма - даны первые k скобок (не обязательно ПСП), необходимо определить k+1.
Как это делается? Пытаемся пририсовать (, проверяем, верно ли, что по-прежнему существует ПСП с таким номером и началом. Если нет, приписываем ), проверяем. И так до ]. Единственный вопрос: как проверить. Для этого предлагается научиться по последовательности определять минимальный и максимальный номер продолжающего ПСП. Теперь учимся это делать. Пусть в некоторый момент есть последовательность из k скобок, известно, что все ее продолжения до ПСП имеют номера от А до В. Ясно, что тогда все номера от А до В достигаются в точности по одному разу. Когда мы припишем ( и спросим, в каких интервалах теперь лежат номера, нам всего лишь надо узнать, сколько существует ПСП с данным началом. Итак, решаем эту задачу. Для этого нам надо привести более приятное описание ПСП, что не так просто.
Понятно, что если заменить [ на ( и ] на ), получится стандартная правильная скобочная структура, у которой есть очень простое описание: на любом начинающем промежутке открывающих скобок не меньше, чем закрывающих. Вопрос в том, сколькими способами можно "покрасить" в 2 вида скобок правильную скобочную структуру, если покраска первых k скобок задана. В скобочной структуре все скобки разбиваются на пары открывающих и закрывающих, которые должны быть одного типа. Количество таких пар - ровно половина длины (известная нам величина). Далее. Несколько скобок уже открыты известным образом (так как раскраска первых k скобок дана). Поинтересуемся, сколько их: это понятно, их в точности разность между количеством открывающих и закрывающих скобок в покрашенном куске (не забудь это сделать глобальной константой и пересчитывать только раз в шаг, а не на каждом шагу считать заново). Итого мы еще несколько скобок красим однозначно. Все остальные разбились на пары, каждую пару можно покрасить 2 способами, итого способов 2^количество таких пар.
Пользуйся, учись:) | для Страус:
Ну да, только от этих рассуждений до готового решения еще очень далеко. А ТС хочет, чтобы ему дали готовый ответ. Можно было б конечно просто взять и сгенерить все возможные варианты, отсортировать их по заданному правилу, и выбрать вариант с нужным номером, только это ж для последовательности в 250 скобок это нереально. А получит сразу заданную последовательность, это уже задача не тривиальная, но на то и олимпиада | для Akron:
Алгоритм фактически приведен. Кодить точно не буду:) По времени работы должно подойти, если правильно написать. Это довольно известная задача:) | для Страус:
Благодарю | | [Сообщение удалено смотрителем дАртаньян // ] | | [Сообщение удалено смотрителем дАртаньян // ] | | [Сообщение удалено смотрителем дАртаньян // ] | для дАртаньян:
Будь добр, потри весь оффтоп. | | [Сообщение удалено смотрителем дАртаньян // ] | | Есть еще задачи, потом выложу еще одну, это самые сложные. | | Следует поднять тему. |
1|2К списку тем
|
