Новости уфологии. В одной из шахт на глубине 1600 метров в пласте угля найден ржавый болт, который 350 миллионов лет назад положили на Землю пришельцы с Альфы Центавра.

Теория

После инопланетного нападения у ученых появилось много работы, особенно изучение инопланетян, их генетического кода, свойств, а также то, как их убить. Однако работник лаборатории Вася решил, что вместо уничтожения их лучше использовать в развитие человечества. Для этого нужно получить кусок генетического кода, который позволит улучшить человека. Ученый должен проанализировать код пришельца, связать информацию о свойствах пришельца и информацию из генетических цепочек. А после он установит их в себя, тем самым прокачавшись (опустим то, что это так не работает).

Каждая цепочка представляет собой последовательность из нуклеотидов. Всего нуклеотидов 5 (ДНК + РНК) - {A, G, C, U, T}. Каждое свойство кодируется тремя нуклеотидами (блоками), которые записаны подряд. Свойства записываются аналогично (подряд). Например, AUGCGUAC можно расшифровать, как {AUG, CGU} или {UGC, GUA}, или {GCG, UAC}. Как видно из примера, расшифровок много, однако троек без свойств не может быть, но не используемые нуклеотиды присутствовать могут.

Рассмотрим на примере:

Цепочка Свойства
AUGCGUAC Красные глаза
  Невыспанный взгляд
AACCGU Красные глаза
  Бессвязная речь

Разбивая на блоки первую цепочку мы получаем 3 варианта.

1 2 3
AUG UGC GCG
CGU GUA UAC

Понятно, что определить что и к какому свойству относится блок по одной цепочке, нельзя. Потому добавим еще одну цепочку. Для второй цепочки аналогично составим все возможные комбинации. После чего можно уже сделать анализ.

A1 A2 A3   B1 B2 B3
AUG UGC GCG   AAC ACC CCG
CGU GUA UAC   CGU    

Это означает, что блок CGU в первой и второй цепочках определяет Красные глаза, а AUG с AAC соответственно определяют Невыспанный взгляд и Бессвязную речь.

Дополнение

Тройки нуклеотидов идут подряд. Справа и слева от троек может быть максимум пустых 2 нуклеотида (не используемых). В данном примере используемые нуклеотиды будут обозначены 1, а не используемые - 0 (Подряд идущих трех нулей не бывает).

Length 3
111

Length 4
1110
0111

Length 5
11100
01110
00111

Length 6
111111
011100
001110

Length 7
0011100
0111111
1111110

Задача

1 часть
Дана последовательность нуклеотидов, требуется определить все возможные цепочки, которые могут хранить свойство. Результатом будет вывод количества, а после вывод всех комбинаций, цепочка в комбинации разделяется пробелом.

Input:
AUGCGUAC

Output:
3
AUG CGU
UGC GUA
GCG UAC

Input:
AUGCGU

Output:
3
AUG CGU
UGC
GCG

2 часть
Даны последовательности нуклеотидов, которые имеют одинаковое свойство. Требуется определить, какая цепочка нуклеотидов относится к обеим последовательностям. Если невозможно определить, то -1 (когда подходят одновременно несколько цепочек). На вход подается количество последовательностей, после сами последовательности. На выходе ожидается одна цепочка или -1.

Input:
2
AUGC
AAUGAС

Output:
AUG

Input:
3
AUGGС
AAUGGC
AUGGCC

Output:
-1

3 часть
Опишите алгоритм решения задачи, описанной в теории (и схожих). На вход подается количество последовательностей, после последовательность, количество свойств и сами свойства (и так для каждой последовательности). На выходе ожидается пара: цепочка и свойство. Для упрощения свойства представлены в виде чисел. Числа необязательно трехзначные, но для визуального разделения были использованы такие.

Input:
2
AUGCGUAC
2
101
102
AACCGU
2
101
103

Output:
CGU 101
AUG 102
AAC 103
На Главную