무한 팬케이크 가게가 새로운 팬케이크를 출시했다. 한쪽 면은 초콜릿 칩으로 만든 행복한 얼굴(면)이고 반대쪽 면은 빈 면이다. 당신은 이 가게에서 근무 중인 수석 웨이터로 주방에서는 고객에게 전달할 팬케이크를 당신에게 전달한다. 당신은 팬케이크 X-ray 능력이 있어서, 겹쳐져있는 팬케이크의 면을 전부 투시해서 볼 수 있다. 팬케이크의 모든 면이 행복한 면이 위쪽에 있도록 고객에게 전달하면, 고객은 가장 행복해한다고 한다.
당신은 팬케이크 면을 뒤집는 방법을 안다. 팬케이크 더미가 있으면 그 더미를 두 그룹으로 나눈 후, 위쪽의 그룹을 전부 뒤집는다. 그룹을 한 번에 뒤집는 거지 개별적으로 뒤집지 않는다는 것에 유의해라. 팬케이크를 각각 i, i-1, ..., 2, 1, i+1, i+2, ..., N로 번호를 매긴다면 i+1, i+2, ..., N로 이전에 올린 면이 위로 올라가게 된다(즉 그냥 반대로 됨..)
예시를 들어 +가 행복한 면, -가 빈 면이라고 하자. 위부터 시작하는 --+- 문자열인 팬케이크가 주어진다고 한다. 만약 당신이 3번째 열에서 팬케이크를 뒤집으면 -++-가 된다. 왜냐하면 --+를 뒤집으면 ++-가 되고 이를 거꾸로 두면 -++가 되기 때문에 -++-가 된다. 중간의 특정 몇 개만 뒤집는건 불가능하며, 일단 뒤집으면 0열부터 전부 뒤집힌다. 이 예제에서 최소 횟수는 -++- -> +++- -> ---- -> ++++로 총 3번이 걸린다.
모든 팬케이크 면이 행복한 면이 위로 올라갈 때까지 고객에게 서빙을 하지 않을 예정이지만, 팬케이크가 식을 수 있기 때문에 빠르게 뒤집어야한다. 모든 팬케이크 면을 행복한 면으로 올리기 위한 필요 최소 횟수는 몇 번인가?
입력 첫 번째 줄에는 테스트케이스 수인 T를 정수로 입력받는다. 그 다음 T개의 줄만큼 팬케이크 문자열인 S를 입력받는다. 각 문자는 +,-로 구성되어있으며 문자열은 왼 -> 오로 팬케이크 위 ->아래로 나타낸다.
출력 각 테스트케이스마다, Case #x: y 형식에 맞춰 테스트케이스 번호인 x와 최소 횟수인 y를 줄마다 출력한다.
wlskrla7 1년 전
무한 팬케이크 가게가 새로운 팬케이크를 출시했다. 한쪽 면은 초콜릿 칩으로 만든 행복한 얼굴(면)이고 반대쪽 면은 빈 면이다. 당신은 이 가게에서 근무 중인 수석 웨이터로 주방에서는 고객에게 전달할 팬케이크를 당신에게 전달한다. 당신은 팬케이크 X-ray 능력이 있어서, 겹쳐져있는 팬케이크의 면을 전부 투시해서 볼 수 있다. 팬케이크의 모든 면이 행복한 면이 위쪽에 있도록 고객에게 전달하면, 고객은 가장 행복해한다고 한다.
당신은 팬케이크 면을 뒤집는 방법을 안다. 팬케이크 더미가 있으면 그 더미를 두 그룹으로 나눈 후, 위쪽의 그룹을 전부 뒤집는다. 그룹을 한 번에 뒤집는 거지 개별적으로 뒤집지 않는다는 것에 유의해라. 팬케이크를 각각 i, i-1, ..., 2, 1, i+1, i+2, ..., N로 번호를 매긴다면 i+1, i+2, ..., N로 이전에 올린 면이 위로 올라가게 된다(즉 그냥 반대로 됨..)
예시를 들어 +가 행복한 면, -가 빈 면이라고 하자. 위부터 시작하는 --+- 문자열인 팬케이크가 주어진다고 한다. 만약 당신이 3번째 열에서 팬케이크를 뒤집으면 -++-가 된다. 왜냐하면 --+를 뒤집으면 ++-가 되고 이를 거꾸로 두면 -++가 되기 때문에 -++-가 된다. 중간의 특정 몇 개만 뒤집는건 불가능하며, 일단 뒤집으면 0열부터 전부 뒤집힌다. 이 예제에서 최소 횟수는 -++- -> +++- -> ---- -> ++++로 총 3번이 걸린다.
모든 팬케이크 면이 행복한 면이 위로 올라갈 때까지 고객에게 서빙을 하지 않을 예정이지만, 팬케이크가 식을 수 있기 때문에 빠르게 뒤집어야한다. 모든 팬케이크 면을 행복한 면으로 올리기 위한 필요 최소 횟수는 몇 번인가?
입력
첫 번째 줄에는 테스트케이스 수인 T를 정수로 입력받는다. 그 다음 T개의 줄만큼 팬케이크 문자열인 S를 입력받는다. 각 문자는 +,-로 구성되어있으며 문자열은 왼 -> 오로 팬케이크 위 ->아래로 나타낸다.
출력
각 테스트케이스마다, Case #x: y 형식에 맞춰 테스트케이스 번호인 x와 최소 횟수인 y를 줄마다 출력한다.