Robbery

원문보기

---

인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)

About Robbery

로보스탑 형사는 화가 머리 끝까지 나 있다. 지난 밤에 은행이 털렸는데, 은행강도를 잡지 못했기 때문이다. 사고가 난 직후, 강도가 도망갈 수 없도록 도시 밖으로 나가는 도로를 차단했다. 그리고 도시에 있는 모든 사람들에게 강도를 찾아달라는 요청을 했다. 하지만 그는 강도를 못 봤다는 말밖에 들을 수 없었다.

로보스탑은 강도가 정확하게 어떤 식으로 탈출했는지 반드시 알아내기로 결심했다. 로보스탑 형사가 당신에게 그가 가진 모든 정보를 분석해서 강도가 언제 어디에 있었는지 알아낼 수 있는 프로그램을 만들어달라고 요청했다.

그 범죄가 일어난 도시는 직사각형 모양으로 생겼다. 도시 밖으로 나가는 모든 도로는 시간 t 동안 봉쇄되어 있었고, 그 동안 "강도가 시간 t_i에 직사각형 R_i에 없다"는 식의 보고가 올라왔다. 그 강도가 각 시각 단계마다 최대 한 칸만 이동할 수 있다고 가정하고, 각 시각 단계에서의 강도의 정확한 위치를 찾아내라.

Input

한 입력 파일에 여러 테스트 케이스가 있을 수 있다. 각 테스트 케이스의 첫째 줄에는 세 개의 정수 W, H, t(1 ≤ W, H, t ≤ 100)가 들어있으며, W는 도시의 너비, H는 도시의 높이고, t는 도시가 봉쇄된 시간이다.

그 다음 줄에는 n(0 ≤ n ≤ 100)이라는 정수 한 개가 입력되는데, n은 형사가 받은 메시지의 개수다. 그 밑으로는 n줄에 걸쳐서 각 줄마다 다섯 개씩의 정수 t_i,L_i,T_i,R_i,B_i가 입력된다. t_i(1 ≤ t_i ≤ t)는 메시지를 받은 시각이며, L_i,T_i,R_i,B_i는 각각 그 보고가 올라온 직사각형 영역의 왼쪽, 위쪽, 오른쪽, 아래쪽이다. (1,1)은 왼쪽 맨 위 영역이며, (W, H)는 오른쪽 맨 아래 영역이다. 그 메시지는 해당 시각 t_i에 그 직사각형 안에 강도가 없었음을 의미한다. W = H = t = 0 인 테스트 케이스가 입력되면 입력이 종료된다. 이 케이스는 처리하지 않는다.

Output

각 테스트 케이스에 대해 "Robbery #k:"라고 출력한다. 여기에서 k는 강도 사건 번호를 의미한다. 결과는 세 가지 경우로 나눌 수 있다. 강도가 도시 안에 있을 수 없는 경우에는 "The robber has escaped."라고 출력한다. 다른 경우에는 모두 강도가 여전히 도시 안에 있는 것으로 가정한다. 정확한 위치를 유추할 수 있는 경우에는 각 시간 단계에 대해 "Time step [1]: The robber has been at x,y."라고 출력한다. x와 y는 각각 시각이 [2]일 때 강도가 있는 위치의 열과 행을 나타낸다. 각 줄은 시각 [3] 순서대로 정렬해서 출력한다. 아무 결과도 유추할 수 없으면 형사가 화를 내지 않기를 기대하면서 "Nothing known."이라고 출력해야 한다. 각 테스트 케이스 사이에는 빈 줄을 출력한다.

Sample Input

4 4 5

4 1 1 1 4 3 1 1 1 3 4 4 1 1 3 4 4 4 2 4 4 10 10 3 1 2 1 1 10 10 0 0 0

Sample Output

Robbery #1:

Time step 1: The robber has been at 4,4. Time step 2: The robber has been at 4,3. Time step 3: The robber has been at 4,2. Time step 4: The robber has been at 4,1.

Robbery #2: The robber has escaped.

풀이

작성자	사용언어	개발시간	코드
조현태	C++	?	Robbery/조현태

쓰레드

---

문제분류 경시대회준비반