Crime House

Trong khi làm việc cho cảnh sát, bạn đã xác định được một ngôi nhà nơi mọi người đến để thực hiện các hành vi phạm tội, được gọi là Crime House. Một ngày nọ, bạn đặt một chiếc camera trước cửa nhà và ghi lại một đoạn video.

Bạn không biết có bao nhiêu người ở trong Crime House vào đầu ngày, nhưng bạn có thể thấy mọi người ra và vào qua cửa trước. Thật không may, vì những người ra vào Crime House là tội phạm, đôi khi họ đeo mặt nạ; và bạn không chắc liệu cửa trước có phải là lối ra vào duy nhất hay không.

Đôi khi bạn có thể đoán được ai là người đeo mặt nạ. Nếu tội phạm số 5 vào nhà, sau đó một người đeo mặt nạ đi ra, rồi tội phạm số 5 lại vào nhà một lần nữa, thì hoặc người đeo mặt nạ đó là tội phạm số 5, hoặc có một lối ra khác khỏi Crime House.

Vào cuối ngày, khi Crime House đã đóng cửa đêm, bạn xem lại video của mình. Vì bạn là một người lạc quan, bạn muốn tìm hiểu xem liệu có khả năng không có lối ra vào nào khác ngoài cửa trước hay không; và nếu có, bạn muốn tìm ra số lượng người tối thiểu có thể ở trong Crime House vào cuối ngày.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\), số lần mọi người đi qua cửa trước của Crime House trong ngày. Tiếp theo là \(N\) dòng, mỗi dòng chứa thông tin về một người vào hoặc ra khỏi Crime House qua cửa trước.

Thông tin đó bao gồm một ký tự duy nhất, E (vào) hoặc L (ra), tiếp theo là một dấu cách và sau đó là một số nguyên id. Nếu ký tự đầu tiên là E, điều đó cho biết ai đó đã vào Crime House qua cửa trước; nếu là L, ai đó đã ra ngoài qua cửa trước. Nếu id lớn hơn 0, người có mã định danh đó đã vào hoặc ra khỏi Crime House. Nếu id bằng 0, thì người vào hoặc ra đó đang đeo mặt nạ và chúng ta không biết họ là ai.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1). Nếu có khả năng không có lối ra vào nào khác ngoài cửa trước, thì y phải là số lượng người tối thiểu có thể ở trong Crime House vào cuối ngày. Nếu điều đó là không thể, y phải là "CRIME TIME".

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le id \le 2000\).

Phân nhóm

• Small dataset: \(1 \le N \le 15\).
• Large dataset: \(1 \le N \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2014, Vòng 3, bài Crime House.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.