P1777 Help

Bubu’s bookshelf is a mess! Please help him. There are $n$ books on his shelf. We define the messiness as the number of segments of consecutive books that have the same height. For example, if the heights are [30, 30, 31, 31, 32], then the messiness is 3; [30, 32, 32, 31] also has messiness 3, but [31, 32, 31, 32, 31] has messiness 5, which is really messy. Bubu wants to reduce the messiness as much as possible, but he is a bit tired, so he decides to take out at most $k$ books and then place them back on the shelf arbitrarily. Can you help him?

Each input file contains at most 20 test cases. Each test case starts with two integers $n, k$ ($1 \le k \le n \le 100$), where $n$ is the number of books and at most $k$ books can be moved. The next line contains $n$ integers, the heights of the books from left to right. Each height is an integer between 25 and 32. A line with $n = k = 0$ follows the last test case, indicating the end of input.

For each test case, output the label $\text{Case}$ and the minimal possible messiness. Print a blank line after each test case.

Translated by ChatGPT 5