超大煎饼翻转器 - 問題

去年，无限煎饼屋（Infinite House of Pancakes）推出了一种新型煎饼。它的一面有巧克力豆组成的笑脸（“笑脸面”），另一面则什么都没有（“空白面”）。

你是当班的主厨。煎饼在热表面上排成一行。为了尽可能提高效率，无限煎饼屋最近给了你一个超大煎饼翻转器，它每次可以翻转恰好 $K$ 个连续的煎饼。也就是说，在选定的 $K$ 个煎饼范围内，它会将每个笑脸面朝上的煎饼变为空白面朝上，反之亦然；它不会改变这些煎饼从左到右的顺序。

你不能使用翻转器一次翻转少于 $K$ 个煎饼，即使是在这一行的两端也不行（因为烹饪表面的两侧有凸起的边缘）。例如，你可以翻转前 $K$ 个煎饼，但不能翻转前 $K-1$ 个煎饼。

你的学徒还在学习中，他刚刚用老式的单煎饼翻转器翻转了一些煎饼，然后就在顾客即将光临厨房时跑去洗手间了。你现在只剩下这个超大煎饼翻转器，你需要尽快使用它，让所有煎饼都变成笑脸面朝上，这样顾客在参观厨房时才会感到满意。

给定煎饼的当前状态，计算让所有煎饼都变成笑脸面朝上所需的最少翻转次数，或者指出无法做到。

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含一行，由一个字符串 $S$ 和一个整数 $K$ 组成。$S$ 表示煎饼的排列：每个字符要么是 +（表示煎饼初始时笑脸面朝上），要么是 -（表示煎饼初始时空白面朝上）。

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是无法让所有煎饼笑脸面朝上时的 IMPOSSIBLE，或者是完成任务所需的最少翻转次数。

$1 \le T \le 100$ $S$ 中的每个字符均为 + 或 - $2 \le K \le \text{length of } S$

小型数据集（测试集 1 - 可见） $2 \le \text{length of } S \le 10$

大型数据集（测试集 2 - 隐藏） $2 \le \text{length of } S \le 1000$

3
---+-++- 3
+++++ 4
-+-+- 4

Case #1: 3
Case #2: 0
Case #3: IMPOSSIBLE

在样例 1 中，你可以通过先翻转最左侧的 3 个煎饼（得到 ++++-++-），然后翻转最右侧的 3 个（得到 ++++---），最后翻转剩下的 3 个空白面朝上的煎饼，使所有煎饼都笑脸面朝上。虽然还有其他 3 次或更多次翻转的方法，但没有少于 3 次的方法。

在样例 2 中，所有煎饼已经笑脸面朝上，因此不需要进行任何翻转。

在样例 3 中，无法使从左往右数第二个和第三个煎饼朝向相同，因为任何翻转操作都会同时改变它们两个。因此，无法使所有煎饼都笑脸面朝上。

QOJ.ac