C :: RNA Molecules
Time Limit: 10 Seconds Memory Limit: 131072 KB
The RNA molecule is a sequence of four nucleotides A, C, G, and U. Due to the chemical structure of nucleotides, there could be hydrogen bonds established between any pair of (A,U), (U,A), (G,C) or (C,G) nucleotides, but not for the other cases (i.e. for instance A can’t make a hydrogen bond with either C or G). Every nucleotide can have hydrogen bond with at most one other nucleotide, and there could not be any hydrogen bond between two nucleotides that are adjacent in the RNA sequence as there is already a covalent interaction between them.
In the living cells, RNA will fold and there would be many hydrogen bonds established. But the hydrogen bonds can’t cross each other, i.e. if there is a bond from nucleotide i to nucleotide j (i<j), the nucleotides i+1,…,j-1 can have bonds only between themselves, and can’t have any bonds to either 1,…,i-1 or j+1,…,n where n is the number of nucleotides in the RNA.
The real case for RNA is more complicated, but we are not going to face you so much complexities in this competition, making your life easier.
Your task is to find the maximum possible bonds for a set of given RNA molecules.
Input
There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers 0≤n≤500. The second line of each test case contains a string (RNA molecule) of size n consisting of characters A, C, G, and U. The input terminates with “0” which should not be processed.
Output
For each test case, output the maximum number of hydrogen bonds for the given RNA molecule.
Sample Input
2 AU 4 AGCU 4 AGUC 0
Sample Output
0 1 1Submit
Source: 11th Iran Nationwide Internet Contest