Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:32 MB

#239. 特殊的DNA片段

Statistics
本题由南山鲍安其原创!在此感谢!


众所周知,DNA含有四种含氮碱基,分别为腺嘌呤(Adenine)、胞嘧啶(Cytosine)、鸟嘌呤(Guanine)、胸腺嘧啶(Thymine),所以一个DNA片段可以用字母ACGT的组合来表示。而有一些片段在形式上是比较特别的,相当具有研究价值,例如P-Special片段。
我们这样定义P-Special片段:
•空片段为P-Special片段(当然空片段是没有意义的,这只是为了定义方便);
•如果片段S是P-Special片段,则以下片段也是P-Special片段:AST,TSA,GSC,CSG;
•如果片段S1、S2都是P-Speacial片段,则S1S2也是P-Special片段。
举例来讲,以下片段都是P-Special片段:ATGC,AAATTT,ATGTAC
而以下片段不是P-Special片段:ACA,AACCGG,AGTC
现代生物技术的发展让我们可以修改一个DNA片段,所以如果要研究携带含有P-Special片段的DNA的生物的特征,我们不必去寻找一个DNA内含有P-Speacial片段的生物样本,而可以将某个现成的片段修改为P-Special片段。
出于技术原因,我们只有一种修改方法:在某个位置插入一个新的含氮碱基。
然而这样的修改看起来简单,实际操作却难度并不算低,所以我们当然希望能够通过尽量少的修改来制作一个P-Special片段。
读入一个DNA片段,输出以最小的修改代价修改后的片段。如果对于给定的输入存在多种可行解均能使代价最小,你可以输出任意一个。


【输入格式】
仅一行,一个只包含半角英文大写"A""T""G""C"的字符串,表示需要修改的DNA片段。


【输出格式】
仅一行,一个只包含半角英文大写"A""T""G""C"的字符串,表示修改之后的DNA片段。


【样例输入】
AGTC


【样例输出】
ATGTAC


【数据规模】
对于20%的数据,保证输入文件不大于10B;
对于100%的数据,保证输入文件不大于300B。