범죄의 집 (작은 입력)

시간 제한5초메모리 제한512 MB

요약
마스크를 쓴 출입 기록에 인물을 배정해 안팎 상태가 어긋나지 않게 하고 끝에 안에 남는 최소 인원을 구합니다.
난이도

보통10점 중 6점

유형
백트래킹, 시뮬레이션
정답자
아직 제출이 없습니다

문제

경찰에서 일하다가 사람들이 범죄를 저지르러 드나드는 집을 찾아냈다. 모두 이 집을 범죄의 집이라고 부른다. 어느 날 현관문 위에 카메라를 달고, 하루 동안 그 문을 지나간 사람을 모두 녹화했다.

하루가 시작될 때 집 안에 몇 명이 있었는지는 모른다. 현관문 말고 드나들 수 있는 다른 길이 있는지도 확실하지 않다. 드나드는 사람은 범죄자라서 가면을 쓰기도 하는데, 그런 사람이 누구인지는 영상만 봐서는 알 수 없다.

가면 뒤의 사람을 짐작할 수 있을 때도 있다. 범죄자 5번이 들어가고, 가면을 쓴 사람이 나가고, 5번이 다시 들어갔다고 하자. 그러면 가면을 쓴 사람이 5번이었거나, 이 집에 다른 출구가 있다.

이미 집 안에 있는 사람은 들어갈 수 없고, 이미 집 밖에 있는 사람은 나갈 수 없다. 하루가 끝나 집이 문을 닫은 밤에 녹화를 돌려본다. 낙관적인 성격이라, 현관문이 유일한 출입구라고 해도 이 기록을 설명할 수 있는지 알고 싶다. 설명할 수 있다면, 하루가 끝난 시점에 집 안에 있을 수 있는 사람 수의 최솟값을 구한다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스의 첫째 줄에는 하루 동안 사람이 현관문을 지나간 횟수 NN이 주어진다. 이어지는 NN개 줄에는 통과 기록이 녹화된 순서대로 한 줄에 하나씩 주어진다.

각 줄은 문자 E 또는 L, 공백, 정수 idid로 이루어진다. E는 현관문으로 들어온 것을, L은 현관문으로 나간 것을 뜻한다. idid가 0보다 크면 그 번호를 가진 사람이 지나갔다. idid가 0이면 지나간 사람이 가면을 썼고, 누구인지 알 수 없다. 가면을 쓴 사람은 누구든 될 수 있고, 번호가 녹화에 한 번도 나오지 않은 사람일 수도 있다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤151 \le N \le 15
  • 0≤id≤20000 \le id \le 2000

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 현관문이 유일한 출입구인 것이 가능하면 y는 하루가 끝난 시점에 집 안에 있을 수 있는 사람 수의 최솟값이고, 불가능하면 y는 CRIME TIME이다.

예제2

  1. 예제 1

    입력
    5
3
E 5
L 0
E 5
2
L 1
L 1
4
L 1
E 0
E 0
L 1
7
L 2
E 0
E 1
E 2
E 0
E 3
L 4
13
L 4
L 1
L 2
E 0
L 1
E 0
L 2
E 0
L 2
E 0
E 0
L 1
L 4
    예상 출력
    Case #1: 1
Case #2: CRIME TIME
Case #3: 1
Case #4: 4
Case #5: 0

  2. 예제 2

    입력
    3
1
E 0
1
L 0
2
E 7
L 7
    예상 출력
    Case #1: 1
Case #2: 0
Case #3: 0