编程介的小学生 2017-04-27 15:24 采纳率: 20.5%
浏览 979
已采纳

Popo's Lamps

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).

Input

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.

Output

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.

Sample Input

5
RGBGR
4
RGRG
7
ABACADA
0
Sample Output

3
3
4

  • 写回答

1条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥50 汇编语言除法溢出问题
  • ¥50 C++实现删除N个数据列表共有的元素
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗