Pro.ID21619 TitleGene Reprogram Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21619 AC0 Submit0 Ratio- 时间&空间限制描述As a gene engineer of a gene engineering project, Enigma encountered a puzzle about gene recombination. It is well known that a gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Enigma has gotten a gene, such as "ATCC" for example. And he wants to reorder this gene to a new one, "CTCA" for instance. He can use two kinds of operations: (1) exchange the first two letters, or (2) move the first letter to end of the gene. For example, "ATCC" can be changed to "TCCA" by operation two, and then "TCCA" can be changed to "CTCA" by operation one. Your task is to make a program to help Enigma to find out the minimum number of operations to reorder the gene. 输入The input contains several test cases. The first line of a test case contains one integer N indicating the length of the gene ( 1 ≤ N ≤ 12 ). The second line contains a string indicating the initial gene. The third line contains another string which Enigma wants. For each kind of letter, the two strings have the same number of it. Input is terminated by one line contains one zero. 输出Description As a gene engineer of a gene engineering project, Enigma encountered a puzzle about gene recombination. It is well known that a gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Enigma has gotten a gene, such as "ATCC" for example. And he wants to reorder this gene to a new one, "CTCA" for instance. He can use two kinds of operations: (1) exchange the first two letters, or (2) move the first letter to end of the gene. For example, "ATCC" can be changed to "TCCA" by operation two, and then "TCCA" can be changed to "CTCA" by operation one. Your task is to make a program to help Enigma to find out the minimum number of operations to reorder the gene. Input The input contains several test cases. The first line of a test case contains one integer N indicating the length of the gene ( 1 ≤ N ≤ 12 ). The second line contains a string indicating the initial gene. The third line contains another string which Enigma wants. For each kind of letter, the two strings have the same number of it. Input is terminated by one line contains one zero. Output For each test case, output the minimum number of operations. Sample Input 4 Sample Output 2 Source 样例输入4 样例输出2 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 11:59 , Processed in 0.034839 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
