Submit Ranklist
Problem : 178 - 龍使之HSNU-HOT
Problem Statistics
Solved Member:
40 Submission:
108 User Tried:
44 Statement:
生物學家發現了一種由HSNU-Hot所組成的生物，他的DNA是由HSNU與Hot所組成，為了方便敘述，我們以A簡稱HSNU，以B簡稱Hot。
一個HSNU-Hot生物的DNA是由A,B組成，神奇的是你會發現你可以把它拉直，變成一個A,B組成的序列，有頭有尾，有血有淚，生物學家HH是研究HSNU-Hot的學者，在HH的研究下發現，HSNU-HOT生物存在兩種變化。
1.改變自己某一個基因 ( A → B , B → A)
2.選定一個點K(1 ≤ K ≤ n)，對1到K的基因做相反置換 ( A → B , B → A)
當HSNU-HOT生物的基因全變為A時，他便會成為一條幼龍，此時身為龍使的HH便能使出龍契約文與他訂契約，這真是一個讓人興奮不已的事！
為了在最短的時間內讓HSNU-HOT生物進化為一條幼龍，可憐的HH只好求助於你至少需要經過幾次變化，使得HH能盡早達成願望。
Input:Output:
第一行有一個數字T ( 1 ≤ T ≤ 10 )，代表有T個HSNU-HOT生物。
對於每個HSNU-HOT生物給兩行資訊，，第一行有一個數字N ( 1 ≤ N ≤ 1000000 ) ，第二行有一長度為N的字串，皆由字母A,B所組成。
對於每一個HSNU-HOT生物輸出一個數字，表示最少要經過幾次變化進化成一條幼龍。
Sample Input:Sample Output:
3
4
ABBA
5
BBABB
12
AAABBBAAABBB
2
2
4
Source:
COCI 2011/2012 #5
Problem Setter
hanhan0912 Testdata:
| Test | Time | Memory | Score |
|---|
| 0 | 1000ms | 65536kb | |
| 1 | 1000ms | 65536kb | 20 |
| 2 | 1000ms | 65536kb | 20 |
| 3 | 1000ms | 65536kb | 20 |
| 4 | 1000ms | 65536kb | 20 |
| 5 | 1000ms | 65536kb | 20 |