Задача G. Моделирование вторичной структуры РНК

Автор:Бойко   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:Стандартный выход  

Условие

Дана нуклеотидная последовательность РНК длины L. Требуется написать программу, моделирующую вторичную структуру РНК с помощью алгоритма Нуссинов (при обратном проходе последовательность возможных ходов по матрице не менять местами! См. стр. 13 из 4-й лекции). Длина петель должна быть не менее 3 нуклеотидов, при ветвлении между шпильками должно быть не менее 2 нуклеотидов. Учитывать лишь Уотсон-Криковские пары G-C, A-T и обратные им.

Формат входного файла

Во входном файле содержится одна строка.

Формат выходных данных

Выходной файл должен содержать число комплементарных пар нуклеотидов, образующих шпильки и саму структуру, где спаренные нуклеотиды обозначены знаком < или >, а неспаренные точками. Например последовательность GGGAAAATCC будет записана как .<<<...>>>.

Ограничения

L < 100.

Примеры тестов

Входной файл (input.txt) Стандартный выход
1
GGGAAAAUCC
3 .>>>...<<<
2
GGGAAAAUCCCCUAUGCGAUAA
6 .>>>...<<<..>>>...<<<.
3
GGAAAAUCCCCUAUGCGAUAAAAAAGCGUUU
9 >>>...<<<..>>>...<<<..>>>...<<<

0.126s 0.017s 15