B. Берландад Женоме бүтээх

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландын эрдэмтэд маш чухал асуудалтай тулгарчээ. Тэдэнд богино DNA-ын хэлтэрхийнүүдийн хэсэг өгөгдсөн ба үлэг гүрвэлийн DNA-г сэргээх ёстой юм! Берландын Женоме үлэг гүрвэл нь бидэнд урьд нь байсан женоме-уудтай ижил зүйл огт байхгүй. Түүнд $26$ ширхэг ялгаатай төрлийн нуклеотид байдаг бөгөөд нуклеотид болгон нь хамгийн ихдээ нэг ширхэг байх юм. Хэрэв бид ялгаатай Англи үсгүүдээр бүх нуклеотид-уудыг тэмдэглэвэл Берландын Женоме үлэг гүрвэлийг Англи жижиг үсгүүдээс тогтох хоосон биш тэмдэгт мөрөөр илэрхийлж болох ба уг тэмдэгт мөрд үсэг тус бүр нь хамгийн ихдээ 1 ширхэг байх юм.

Эрдэмтэн нарт дэд тэмдэгт мөрөөр (дараалсан нуклеотид-уудын хоосон биш дараалал) илэрхийлэгдэх хайж буй женоме-ын $n$ ширхэг женоме-ын хэлтэрхийнүүд байгаа юм.

Та дараах асуудалтай тулгарав: эрдэмтэн нарт үлэг гүрвэл женоме-ыг сэргээхэд тусална уу. Оролтод ямар нэгэн зөрчилтэй зүйл байхгүй ба дор хаяж нэг тохиромжтой мөр оршин байна. Эрдэмтэд таныг мундаг программист гэдгийг олж мэдмэгцээ танаас нэмэлтээр хамгийн бага урттай женоме-ыг сэргээж өгөхийг хүсжээ. Хэрэв хамгийн бага урттай тэмдэгт мөрүүд олон байвал алийг нь ч сонгосон болно.

Оролт

Эхний мөрөнд женоме-ын хэлтэрхийнүүдийн тоо болох эерэг бүхэл $n$ ($1 ≤ n ≤ 100$) тоо өгөгдөнө.

Дараагийн мөрүүдийн мөр болгонд нэг хэлтэрхийнүүдийн тайлбар өгөгдөнө. Хэлтэрхий болгон нь ялгаатай Англи жижиг үсгүүдээс тогтох хоосон биш тэмдэгт мөр байна. Өгөгдсөн хэлтэрхийнүүд нь ялгаатай байх албагүй. Хэлтэрхийнүүд нь дурын байдлаар давхацсан байж болох ба нэг хэлтэрхий нь өөр нэг хэлтэрхийнүүдийн дэд тэмдэгт мөр байж болно.

Мөн өгөгдсөн бүх хэлтэрхийнүүдийг өөртөө дэд тэмдэгт мөр хэлбэртэйгээр агуулах ялгаатай үсгүүдийн тэмдэгт мөр оршин байхгүй байна.

Гаралт

Ганц мөрөнд бүх өгөгдсөн хэсгүүдийг өөртөө агуулах хамгийн бага урттай женоме-ыг хэвлэнэ. Женоме-дахь бүх нуклеотид-ууд нь ялгаатай байх ёстой. Хэрэв олон тохиромжтой тэмдэгт мөрүүд байвал хамгийн бага урттайг нь хэвлэнэ үү. Хэрэв хамгийн бага урттай олон тэмдэгт мөр байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3
bcd
ab
cdef
Гаралт
abcdef
Оролт
4
x
y
z
w
Гаралт
xyzw
Сэтгэгдлүүдийг ачааллаж байна...