GCJ/2017/Qualification/A/main.go

package main

import (
	"fmt"
)

func main() {
	var T, K int
	fmt.Scan(&T)
	for cid := 1; cid <= T; cid++ {
		var S string
		fmt.Scan(&S)
		fmt.Scan(&K)
		n := len(S)
		happy := make([]bool, n)
		for i, c := range S {
			happy[i] = c == '+'
		}
		flip := 0
		for i := 0; i < n-K+1; i++ { // O(nK)
			if happy[i] == false { // The only way to flip the leftmost pancake is to flip it from its position.
				flip++
				for j := 0; j < K; j++ {
					happy[i+j] = !happy[i+j]
				}
			}
		}
		for i := n - K; i < n; i++ {
			if happy[i] == false {
				flip = -1
				break
			}
		}
		fmt.Printf("Case #%d: ", cid)
		if flip == -1 {
			fmt.Printf("IMPOSSIBLE\n")
		} else {
			fmt.Printf("%d\n", flip)
		}
	}
}