ZOJ Problem Set - 2624
popo had DPJ (a special Chinese food made of stewed chicken, potato and noodle) with his family every night during the last months of popo's undergraduate time. Along the road to the restaurant where they would have DPJ, there were many lamps. One day, popo looked at one of the lamps while waiting other members of his family, and he noticed there was a magic switch on the lampstand of each lamp, he could choose a number N and a color C in the switch, after turning the switch, the next N lamps to the right of the lamp, including the one where popo turned the switch, would turn to the same color of light that popo chose. popo was so naughty a boy that he wanted to turn the lamps to a pattern of color light to surprise his family.
For example, he would turn the lamps to the pattern red-green-blue-green-red as "RGBGR". It was easy to see that popo could turn the lamp to any pattern he liked, but he wanted to know the minimal number of switches he needed to turn to fulfill the task. It would take him three switching to achieve the above pattern. The first switching would turn the five lamps in red (RRRRR). The second switching would turn the three lamps in the middle to green to obtain the pattern (RGGGR). The final switching would make the lamp in the center blue to obtain pattern he desired (RGBGR).
The input consists of multiple test cases! Each test case begins with a number N (1 <= N <= 50) indicating the length of the pattern. Following this, there is N charaters in a line describing the pattern that popo wanted. Each charater is an uppercase letter indicating the color of lamp in the pattern. You may assume each lamp could turn to any color in the pattern, and the initial state of each lamp was off, which did not show any color. The test cases ends with an N == 0, you need not proceed this input.
For each test case, print the minimal number of switching popo needed to turn the lamps to the pattern he desired in a single line.
5 RGBGR 4 RGRG 7 ABACADA 0
3 3 4
Author: YANG, Chao
Source: ZOJ Monthly, November 2005