Breakfast at the Hostel
A youth hostel in Puerto Rico serves a stack of pancakes. The stack is described from top to bottom by a string of signs. A + means that pancake is facing the right way; a - means it is upside down.
In one operation, take one or more pancakes from the top and flip the entire block. This reverses both the order of the selected pancakes and the sign of each one. The rest stay unchanged.
Find the minimum number of operations that makes every sign +.
Input
The first line contains T. Each of the next T lines contains a string S of + and - signs.
Output
For each case i, starting at 1, print exactly "Case #i: answer", without quotation marks.
Constraints
1 ≤ T ≤ 100; 1 ≤ length of S ≤ 100. These are the original large-dataset limits.
Ejemplo
| Entrada de Ejemplo | Salida de Ejemplo |
|---|---|
| 4 + -- +- -+- |
Case #1: 0 Case #2: 1 Case #3: 2 Case #4: 3 |
Flipping the entire stack -- turns it into ++ in one operation.
Source
Adapted for OiPR 2026. Google Code Jam 2016, Qualification Round — Revenge of the Pancakes.
Comments