bubel
На недавно упавшем метеорите ученые обнаружили живые организмы. По просьбе военных сразу начались исследования, для того, чтобы выяснить опасность этихорганизмов для жизни планеты. В первую очередь ученые начали анализировать ДНК код организма. Известно, что ДНК кодируется строкой, состоящей из заглавных латинских букв A, C, T, G. Организм оказался настолько простым, что его код описывается одной буквой. Но ученые не остановились на этом результате и вскоре определили, что обнаруженный организм склонен к эволюции. Генетики смогли определить, что каждый день с момента обнаружения, организм эволюционирует таким образом, что его код ДНК увеличивается на один символ. После дополнительных исследований удалось определить символы и порядок, в котором они добавляются. Ученые также знают, что новый символ добавляется случайным образом в начало или в конец кода. По многодневным наблюдениям известно, что более жизнеспособным является тот организм, у которого ДНК код лексикографически меньше (следует раньше) остальных вариантов. Вам требуется определить ДНК код самого жизнеспособного организма, который может получиться из обнаруженного в результате эволюции. Входные данные Первая строка входного файла содержит один из символов A, C, T, G — исходный ДНК код организма. Вторая строка содержит строковую величину E, которая состоит из символов A, C, T, G (1 ≤ |E| ≤ 1 000 000) и содержит символы, которые будут добавляться к исходному коду в заданном порядке. Выходные данные Выходной файл должен содержать одну строковую величину длиной 1+|E|, состоящую из символов A, C, T, G — ДНК код самого жизнеспособного организма, который может получиться из исходного после всех этапов эволюции. input.txt output.txt Описание C ACTG ACCTG Лексикографически наименьший код получится, если первый символ A добавить в начало кода, а символы C, T и G в конец. A CT ACT Из возможных кодов TCA, TAC, CAT, ACT строка ACT является лексикографически минимальной. T CGTA ACTGT C надо добавить в начало кода, G и T в
