초대형 팬케이크 뒤집개 (스몰)
시간 제한5초메모리 제한512 MB
팬케이크의 상태와 한 번에 뒤집을 수 있는 개수 K가 주어졌을 때, 모든 팬케이크를 행복한 면이 위로 오게 하는 최소 뒤집기 횟수를 구하거나 불가능함을 판정한다.
문제
무한 팬케이크 하우스는 작년에 새로운 팬케이크를 내놓았다. 한쪽 면에는 초코칩으로 웃는 얼굴이 그려져 있고(웃는 면), 반대쪽 면에는 아무것도 없다(빈 면).
당신은 오늘 주방을 맡은 총괄 요리사다. 팬케이크는 뜨거운 철판 위에 한 줄로 놓여 구워진다. 효율을 끝까지 끌어올리려는 가게 방침에 따라 주방에는 최근 연속한 K개의 팬케이크를 한 번에 뒤집는 초대형 뒤집개가 들어왔다. 이 뒤집개는 범위 안에 든 K개 팬케이크에서 웃는 면은 빈 면으로, 빈 면은 웃는 면으로 바꾼다. 팬케이크의 좌우 순서는 바뀌지 않는다.
철판 양쪽에 턱이 있어서 줄의 끝에서도 K개보다 적게 뒤집을 수는 없다. 예를 들어 맨 왼쪽 K개는 뒤집을 수 있지만, 맨 왼쪽 K - 1개는 뒤집을 수 없다.
아직 일을 배우는 중인 견습 요리사가 한 개짜리 뒤집개로 팬케이크 몇 개를 제각각 뒤집어 놓고는, 손님이 주방을 둘러보러 오기 직전에 그 뒤집개를 들고 화장실로 가 버렸다. 주방에는 초대형 뒤집개만 남았다. 손님이 기분 좋게 돌아가도록 구워지는 팬케이크를 모두 웃는 면이 위로 오게 만들어야 한다.
팬케이크의 현재 상태가 주어진다. 모두 웃는 면이 위로 오게 하는 데 필요한 초대형 뒤집개 사용 횟수의 최솟값을 구하라. 그렇게 만들 방법이 없으면 불가능하다고 답하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어지고, 문자열 S와 정수 K가 공백을 사이에 두고 주어진다. S는 팬케이크가 놓인 줄을 나타낸다. S의 각 문자는 처음에 웃는 면이 위인 팬케이크를 뜻하는 +이거나, 빈 면이 위인 팬케이크를 뜻하는 -이다.
제한
- S의 모든 문자는
+또는-이다.
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. y는 모든 팬케이크를 웃는 면이 위로 오게 할 방법이 없으면 IMPOSSIBLE이고, 방법이 있으면 초대형 뒤집개를 사용해야 하는 최소 횟수다.
힌트
예제 1의 첫 번째 테스트 케이스에서는 ---+-++-의 왼쪽 3개를 먼저 뒤집어 ++++-++-를 만들고, 그다음 오른쪽 3개를 뒤집어 ++++---+를 만든 뒤, 남은 빈 면 3개를 뒤집으면 된다. 3번보다 많이 뒤집는 방법도 있지만, 3번보다 적게 뒤집는 방법은 없다.
두 번째 테스트 케이스는 이미 모든 팬케이크가 웃는 면이 위이므로 한 번도 뒤집을 필요가 없다.
세 번째 테스트 케이스에서는 어떤 방법으로 뒤집어도 왼쪽에서 두 번째와 세 번째 팬케이크가 항상 함께 뒤집힌다. 두 팬케이크의 위쪽 면을 서로 같게 만들 수 없으므로 모든 팬케이크를 웃는 면이 위로 오게 할 수 없다.