[1] 대탈주

[시간제한]

10 개의 테스트 케이스를 합쳐 1초

[메모리제한]
512MB

[문제]
절대로 탈출할 수 없다고 알려진 감옥에서 죄수들이 탈출했다. 이들은 감옥 근처에 세워져 있던 차를 훔쳐서 도주하고 있으며, 총 N대의 차량을 이용하고 있다. 이 차량들에 대한 정보라고는 각각의 차량의 색상 뿐이다. 즉, 빨간 차는 몇 대, 파란 차는 몇 대, … 와 같다.

죄수를 추적하던 경찰은 다음과 같은 가정을 하게 되었다.

• 죄수들은 차량을 이용하여 수도로 이동할 것이다. 그런데, 감옥에서 수도로 이동하려면 반드시 특정한 톨게이트를 지나야 한다.
• 이들은 도로 정보를 잘 모르기 때문에, 사이에 다른 차가 끼면 뒤의 차는 앞 차를 놓치고 길을 잃게 된다. 따라서 반드시 이들은 한 줄로 붙어서 이동할 것이다. 죄수들의 차량간 순서는 알 수 없다.

따라서 경찰은 해당 톨게이트를 조사하여, 이 날 이 톨게이트를 통과한 모든 차량에 대한 정보를 얻을 수 있었다. 이 상황에 대한 예를 들어보자. 차량의 색상은 1~9 사이의 숫자로 주어지고, 죄수들이 타고 있는 차량은 1번 색상 2대, 3번 색상 1대, 7번 색상 1대이다. 한 편 이 날 톨게이트를 통과한 차량은 모두 N=10 대이며, 통과한 순서대로 차량의 색상을 보면 다음과 같다.

1 2 8 7 1 3 1 1 2 5

이를 보면, 4번째부터 7번째 차량들의 색상이 각각 7, 1, 3, 1이므로 죄수들이 타고 있는 차량의 색상과 수와 일치한다. 즉 죄수들은 이미 이 톨게이트를 통과했다고 생각할 수 있다.

죄수들이 톨게이트를 통과했는지 여부를 구하는 프로그램을 작성하시오.

[제한 조건]
톨게이트를 통과한 차량의 수 : N
존재할 수 있는 차량의 색상 수 : M
라고 할 때 10개의 입력에 대한 제한 조건은 다음과 같다.

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 50
• M ≤ N

[입력]
첫 줄에 테스트 케이스의 개수 T가 주어지고 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 3개의 줄로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 정수 N과 M이 공백으로 구분되어 차례로 주어지며 그 다음줄에 M개의 정수가 공백으로 구분되어 주어지는데 이 M개의 정수는 차례대로 죄수들이 타고 있는 차량의 개수를 나타내는데 입력받는 순서대로 1번 색상의 차량 개수, 2번 색상의 차량 개수, … , M번 색상의 차량 개수 를 의미한다. 그 다음줄에는 N개의 정수가 공백으로 구분되어 주어지는데, 각각 차례대로 톨게이트를 통과한 차량의 색상을 나타낸다.

[출력]
총 T 개의 줄이 출력된다. 각 줄은 #x로 시작하고 (x는 테스트 케이스 번호, 1부터 시작) 공백을 하나 둔 다음, 조건을 만족하는 죄수들의 차량이 몇 번째 차량부터인지 출력한다. 이 떄 톨게이트를 맨 처음 통과한 차량을 1번째로 한다.(0번째가 아니다.) 만약 죄수들이 톨게이트를 통과하지 않았다면 0을 출력한다.

[입출력 예]

(입력 )

3                                   
10 9                                 
2 0 1 0 0 0 1 0 0                       
1 2 8 7 1 3 1 1 2 5      
10 3       
2 2 2              
1 1 2 2 3 1 1 2 3 3              
3 3            
3 0 0             
1 2 3          

(출력)

#1 4                                     
#2 4                                        
#3 0

==========================================================================================

[Idea]

해당 문제는 색깔을 가지고 있는 차의 배열을 저장해놓은 뒤에 톨게이트에 있는 차들의 배열 인덱스를 1씩 증가시키면서 특정 값의 색깔 num을 -1씩 감소시켰다. 이후 모든 배열이 0미만이 되는 겂이나 0초과 되는 값이 없이, 즉, 모든 범인 차량의 색깔을 저장하고 있는 배열들의 값이 모두 0인 경우가 해당 톨게이트 내 도둑들의 배열이므로 해당 인덱스를 답으로 저장해서 출력하도록 했다. 

[Codes]