ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Отборочный турнир сезона «Весна — 2023» > задача:


C. Макс и ДНК

Отборочный турнир сезона «Весна — 2023»

Старт: 06.мая.2023 в 10:00:00
Финиш: 14.мая.2023 в 23:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (4)

Задачи турнира

• A. Макс и термометр
• B. Макс и ключ
• C. Макс и ДНК
• D. Макс и объединение результатов
• E. Макс и дни рождения великих
• F. Макс и аттракционы
• G. Макс и математические часы
• H. Макс и формирование букета
• I. Макс и номера телефонов
• J. Макс и кубик Рубика 2x2x2

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и ДНК
Макс и ДНК
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Макс узнал, что одной из областей, где в настоящее время активно применяются эффективные вычислительные алгоритмы, является молекулярная биология и генетика. Макс заинтересовался этой сферой и решил больше выяснить о том, как кодируется ДНК — основа всего живого.

Спираль ДНК формируется из азотистых оснований — аденина (A), цитозина (C), гуанина (G) и тимина (T). Примечательно, что связи образуют только пары аденин–тимин и цитозин–гуанин. Участок двойной спирали может выглядеть, например, так:


AAGCACTC
||||||||
TTCGTGAG

Так как по одной половине спирали всегда можно однозначно восстановить другую, для кодирования данного участка достаточно строки AAGCACTC или TTCGTGAG. При этом участок может читаться как слева направо, так и справа налево, поэтому также возможна запись CTCACGAA или GAGTGCTT.

Макс только что получил строку, описывающую неизвестный участок генома. Чтобы определить, какому организму принадлежит этот участок, Максу нужно найти соответствующую строку в базе образцов ДНК. Хранящиеся в базе строки можно заменять на эквивалентные по описанным выше правилам.

Помогите Максу найти в базе запись об имеющемся у него участке ДНК.

Входные данные

Первая строка содержит последовательность $$$S$$$ ($$$1 \le |S| \le 30$$$), состоящую из букв A, C, G и T, — образец ДНК, полученный Максом.

Вторая строка содержит целое число $$$N$$$ ($$$1 \le N \le 30$$$) — количество образцов ДНК, хранящихся в базе.

Следующие $$$N$$$ описывают образцы ДНК, хранящиеся в базе. Каждая из них содержит последовательность $$$R_i$$$ ($$$1 \le |R_i| \le 30$$$), состоящую из букв A, C, G и T, — образец ДНК.

Выходные данные

Выведите одно целое число — номер распознанного образца, соответствующего имеющемуся у Макса. Гарантируется, что такой образец существует.

Распознанные образцы нумеруются от 1 до $$$N$$$ в порядке описания во входных данных.

Примеры

Входные данные
AAGC
3
TTAG
TCG
TTCG
Выходные данные
3
Входные данные
CGTAGAG
6
CAAAGCT
AAAGTAG
CGTATTG
GAGATGC
TCTCCAA
GGAGACA
Выходные данные
4

Для отправки решений необходимо выполнить вход.

www.contester.ru