Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
A. Генетикийн инженерчлэл
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Та энэ бодлогыг шийдвэрлэж чадвал 3 оноо авна.
Манао шинэ төрлийн замгаар ашигтай түлш гаргах генетикийн код боловсруулж байна. Ялангуяа Манао нэг уураг кодлодог ДНХ-н хэсэгт анхаарлаа хандуулж байна. ДНХ-н хэсэг нь зөвхөн '$A$', '$T$', '$G$' '$C$' тэмдэгтүүдийг агуулсан тэмдэгт мөрөөр илэрхийлэгдэнэ.
Хэрвээ ДНХ-н хэсэг нь дараалан тэгш тоон урттай ижил нуклеотидуудын дараалал агуулж байгаа бол уураг эвдэрч гэмтсэн байна гэж Манао тодорхойлсон байна. Жишээлбэл: ДНХ-ийн "GTTAAAG" тэмдэгт мөрийг тодорхойлсон уураг гэж үзье. Энэ нь дараалсан ижил нуклеотидуудын дөрвөн дарааллыг агуулсан байна: "$G$", "$TT$", "$AAA$", "$G$". Уураг гэмтсэн байна учир нь "$TT$" дараалал тэгш урттай
Манао одоо түүнд байгаа уургаас нэг гэмтээгүй уураг гаргаж авахаар хичээж байна. Манао ДНХ-н хэсэг дотор нэмэлт нуклеотидууд оруулж болно. Нэмэлт нуклеотидууд бүр {'$A$', '$T$', '$G$', '$C$'} олонлогийн тэмдэгтүүд байна. Манао эвдрэлгүй уургийн ДНХ-г кодчилоход шаардлагатай хамгийн бага оруулалтын тоог тодорхойлохын хүсэж байна.
Оролт
Оролт нь $n$ $(1 ≤ n ≤ 100)$ урттай $s$ тэмдэгт мөрийг агуулсан нэг мөрөөс бүрдэнэ. $s$-н тэмдэгт бүр {'$A$', '$T$', '$G$', '$C$'} олонлогоос байна.
Энэ бодлогонд дэд бодлогууд байхгүй. Зөв танилцуулвал та 3 оноо авна.
Гаралт
Програм нь нэг мөрөнд бүх ижил тэмдэгтүүдийг сондгой урттай болгоход оролтын тэмдэгт мөрийн дараалал дотор оруулах шаардлагатай '$A$', '$T$', '$G$', '$C$' тэмдэгтүүдийн хамгийн бага тоог илэрхийлсэн нэг бүхэл тоо хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
GTTAAAG
Гаралт
1
Оролт
AACCAACCAAAAC
Гаралт
5
Тэмдэглэл
Эхний жишээнд уургийг эвдрэлгүйгээр сэргээхийн тулд дарааллын хоёр '$T$'-ийн дунд ямар ч төрлийн нэг нуклеотидыг оруулахад хангалттай.