Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Апрель 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП)


Информационный Канал Subscribe.Ru
Логотип Школьный КОМП
КОМП Призёры Зачем? Поддержите! Юмор Игры Статьи Контакты
Школьникам Задача Результаты

Весенняя олимпиада школьников 2003 года.
Задача третьего тура

Генетика на чужой планете

На планете Красивый Фингал, открытой петербургскими космонавтами, генетический код определяется тридцатью одним кодоном. Два из них определяют структуру гена и обозначаются ( и ). Три из них определяют преобразования генетического кода и обозначаются I, K и S. Все остальные, как обычно, порождают организм. Они обозначаются малыми латинскими буквами. Вначале геном некоторое время преобразуется, а затем начинает расти организм, поэтому, например, у свинофингала может родиться собакофингал, а то и дубофингал. Правила преобразований следующие. 

((X)Y) в (XY), (1)
(XY) в ((X)Y), (2)
(IA) в A,
(KAB) в A,
(SABC) в ((AC)(BC)).

Здесь A, B, C -- либо кодоны, либо последовательность кодонов, сбалансированная по скобкам и заключенная в скобки, X и Y -- произвольные сбалансированные по скобкам непустые последовательности кодонов. Если к некоторому фрагменту было применено преобразование (1), то к нему уже не может быть применено преобразование (2), и наоборот.

Генетический код называется стабильным, если он не может преобразовываться, кроме как по правилам (1) и (2).

Если генетический код превысит в длину 250 символов, развитие зародыша прекращается. Точно так же оно прекращается, если код преобразуется более 100 шагов.

Задание.

Даны два входных файла. Species.txt содержит пары строк, описывающих геномы некоторых стабильных видов на планете. Первая, третья и так далее строки -- имена видов, вторая строка -- геном первого вида, четвертая -- второго и так далее. Количество видов не более 8, длина каждой строки до 80 символов. Конец ввода -- пустая строка. Биологи, как им и положено, пишут названия видов на варварской латыни, так что в строках могут быть лишь латинские буквы.

Пример файла. 

Swintus Fingalae
(swintuS)
Canis Fingali
((((ca)n)I)s)
Chimera Baldina
(SSSSS)

Embrion.txt состоит из одной строки c генетическим кодом эмбриона. Для эмбриона нужно вывести историю преобразования и определить, какому виду он принадлежит. Пример файла. 

(SKKs(SKIw)(IIIi)(KnK)tu)S

В файл output.txt нужно вывести результат, какому виду принадлежит эмбрион, либо квалификацию генетического кода. Квалификация может иметь следующие формы:

  1. Новый вид, когда преобразование заканчивается, но получившийся геном принадлежит не описанному стабильному виду.
  2. Опасный, когда преобразование приводит к слишком длинному коду или может продолжаться более 100 шагов.
  3. Фатальный, когда преобразование приводит к печальному исходу с гарантией, по Вашему мнению.

Ваш вывод должен быть обоснован предъявленным преобразованием.

Файл заканчивается пустой строкой.

Пример выходного файла для данного случая. 

Swintus Fingalae
((SKKs(SKIw)(IIIi)(KnK)tu)S)
(((SKKs)(SKIw)(IIIi)(KnK)tu)S)
((((Ks)(Ks))(SKIw)(IIIi)(KnK)tu)S)
(((Ks(Ks))(SKIw)(IIIi)(KnK)tu)S)
((s(SKIw)(IIIi)(KnK)tu)S)
(s(SKIw)(IIIi)(KnK)tuS)
(s(SKIw)(IIIi)ntuS)
(s(SKIw)((II)Ii)ntuS)
(s(SKIw)(IIi)ntuS)
(s(SKIw)((II)i)ntuS)
(s(SKIw)(Ii)ntuS)
(s(SKIw)intuS)
(s((Kw)(Iw))intuS)
(s(Kw(Iw))intuS)
(swintuS)

Внимание! Биологи, изучавшие планету, не очень грамотны в математике и программировании. Поэтому некоторые виды могут быть описаны неправильно, соответствующие геномы нестабильны. Поэтому для таких геномов нужно вывести в файл output.txt ошибку, написав строчки вида: 

Геном Chimera Baldina неверен
(SSSSS)
((SSSS)S)
(((SS)(SS))S)
***

указав неверный геном и его возможное преобразование. Диагностика ошибки в описаниях видов заканчивается строкой с тремя звездочками и не отменяет задачи распознавания эмбриона. Так что полное решение для приведенного теста получается сочленением диагностики ошибок и преобразования генома. Если Вы не продиагностировали ошибку в описании вида, то количество очков за тест снижается, но не до нуля.

Дополнительное задание. Можно получить поощрительные очки, прислав заодно с программой собственный тест (один файл Species.txt и файл Embrions.txt, содержащий не более четырех строк). Он сначала будет оценен содержательно, а затем на нем, если он пройдет предварительную проверку, будут проверяться программы Ваших друзей-соперников. Тест, пройденный лишь Вашей программой либо всеми программами, прошедшими не менее двух тестов жюри, принесет Вам лишь одно поощрительное очко. Если тест пройдет примерно половина из работающих программ, он принесет максимум поощрительных очков. Так что старайтесь подобрать тест средней сложности, но с хитростями. Конечно же, Ваша программа должна проходить все варианты Вашего теста.




Автор задачи: Н. Н. Непейвода


Последний день присылать решения задачи -- 30 апреля 2003 года.

Последний день задавать вопросы по условию задачи -- 23 апреля 2003 года.


Copyright © КОМП  
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное