Olymp programming - Помощь студентам

Mihail0 · 14.01.2010, 18:58

Помогите, пожалуйста, решить задачу (сроки поджимают)

Скобки
Рассмотрим правильные скобочные последовательности, состоящие из трех видов скобок: круглых (), квадратных [] и угловых <>. Назовем последовательность хорошей, если между любой парой соответствующих друг другу открывающейся и закрывающейся круглых скобок не встречается квадратных скобок. Требуется подсчитать количество хороших последовательностей длины 2N (то есть состоящих из N пар скобок).
Входные данные
Во входном файле содержится одно число N (1 ≤ N ≤ 100).
Выходные данные
В выходной файл выведите искомое количество по модулю 27449.

Я не прошу код, подскажите как решать

cherw9!40k · 14.01.2010, 19:19

То есть хорошие это [<()>], [(<>)], <[()]>, ну и еще такие как [(<)>] и т.д.
Мне кажется, надо зациклить поиск посимвольно (если принять, что скобка- это символ). Я так понял, что последовательность должна включать все три вида пар скобок. Создаем три boolean переменных - каждая отвечает за свой тип скобок(изначально все true). Когда при поиске попадается открывающая скобка = true, закрывающая = false. Если все три = false, значит найдена первая последовательность. Во время поиска неплохо было бы сообразить, как фиксировать индексы начала и конца последовательности. Когда первая последовательность найдена, проверяешь, является ли она хорошей. Отражаешь подсчет в счетчике.

Mihail0 · 14.01.2010, 19:24

Да там чистая комбинаторика, не надо их даже генерировать (такое не прокатит, сложность растет экспоненциально)

cherw9!40k · 14.01.2010, 21:14

Попробуй дать более развернутое условие, напиши, что сам сделал, а то информации недостаточно - очень непонятная задача.

LeBron · 14.01.2010, 23:15

Довольно простенькая задача, мне кажется, что удобней всего ее делать именно динамикой (других простых и удобных/понятных решений и в голову не приходит).
Условие полное, можете посмотреть, это текущий заочный тур ВсеСиба.
Как раз поэтому не советовал бы писать сюда готовое полное решение, - так как задача играет роль в реальных соревнованиях, и этой помощью мы ставим участников в неравные условия.
Если говорить о способе решения - можно решать разными способами, мне больше всего нравятся динамика по подстроках и динамическое комбинирование разбиений.

14.01.2010, 18:58	#1
Mihail0 Новичок Джуниор Регистрация: 14.01.2010 Сообщений: 2	Olymp programming Помогите, пожалуйста, решить задачу (сроки поджимают) Скобки Рассмотрим правильные скобочные последовательности, состоящие из трех видов скобок: круглых (), квадратных [] и угловых <>. Назовем последовательность хорошей, если между любой парой соответствующих друг другу открывающейся и закрывающейся круглых скобок не встречается квадратных скобок. Требуется подсчитать количество хороших последовательностей длины 2N (то есть состоящих из N пар скобок). Входные данные Во входном файле содержится одно число N (1 ≤ N ≤ 100). Выходные данные В выходной файл выведите искомое количество по модулю 27449. Я не прошу код, подскажите как решать

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Runtime programming	JoanM	Общие вопросы Delphi	4	09.01.2008 11:00
Обсуждение programming... (кому не лень ответь те plize)	}{@KeRnutyi	Свободное общение	3	14.12.2006 19:50

14.01.2010, 19:19	#2
cherw9!40k Пользователь Регистрация: 20.11.2009 Сообщений: 61	То есть хорошие это [<()>], [(<>)], <[()]>, ну и еще такие как [(<)>] и т.д. Мне кажется, надо зациклить поиск посимвольно (если принять, что скобка- это символ). Я так понял, что последовательность должна включать все три вида пар скобок. Создаем три boolean переменных - каждая отвечает за свой тип скобок(изначально все true). Когда при поиске попадается открывающая скобка = true, закрывающая = false. Если все три = false, значит найдена первая последовательность. Во время поиска неплохо было бы сообразить, как фиксировать индексы начала и конца последовательности. Когда первая последовательность найдена, проверяешь, является ли она хорошей. Отражаешь подсчет в счетчике.

14.01.2010, 19:24	#3
Mihail0 Новичок Джуниор Регистрация: 14.01.2010 Сообщений: 2	Да там чистая комбинаторика, не надо их даже генерировать (такое не прокатит, сложность растет экспоненциально)

14.01.2010, 21:14	#4
cherw9!40k Пользователь Регистрация: 20.11.2009 Сообщений: 61	Попробуй дать более развернутое условие, напиши, что сам сделал, а то информации недостаточно - очень непонятная задача.

14.01.2010, 23:15	#5
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Довольно простенькая задача, мне кажется, что удобней всего ее делать именно динамикой (других простых и удобных/понятных решений и в голову не приходит). Условие полное, можете посмотреть, это текущий заочный тур ВсеСиба. Как раз поэтому не советовал бы писать сюда готовое полное решение, - так как задача играет роль в реальных соревнованиях, и этой помощью мы ставим участников в неравные условия. Если говорить о способе решения - можно решать разными способами, мне больше всего нравятся динамика по подстроках и динамическое комбинирование разбиений.