시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 8 1 (12%) 1
문제
당신은 쓰레기 소각장 최고 관리자이다. 이 나라에서는 쓰레기를 총 K종류로 분류한다. 또한 소각장에는 소각기계가 S대 있는데, 각 기계가 모든 종류의 쓰레기를 소각할 수 있는 것은 아니다. 기계 $M_i$가 소각할 수 있는 쓰레기 종류의 집합이 정해져 있기 때문에, 어떤 종류의 쓰레기를 소각하기 위해서는 그에 맞는 기계를 써야만 한다. 서울->소각장을 연결하는 일방통행 직선도로를 따라 N개의 쓰레기차들이 줄지어 들어오고 있다. 각각의 쓰레기차에 실려있는 쓰레기들은 이미 분리수거가 완벽하게 된 상태로, 쓰레기차 i는 종류가 $s_i$(1$\leq s_i\leq$K)인 쓰레기만 싣고 온다. 원칙적으로는 앞에 있는 쓰레기차들부터 순서대로 처리를 해야한다.
Drawing
그러나 국가예산절약 방침에 따라 하루에 단 한 대의 소각기계 밖에 쓸 수 없게 되었다. 이에 따라 서울에서부터 쓰레기 소각장으로 연결되는 v자 모양 일방통행 우회도로를 하나 더 만들고, 처리 순서를 약간 바꾸기로 하였다. 서울에서 맨 앞에 있는 쓰레기차 한 대가 소각장으로 출발할 때는 두 가지의 경로가 있다(물론, 작동 중인 소각기계가 그 쓰레기차에 있는 종류의 쓰레기를 처리할 수 있어야 한다.): - 직선도로를 따라 쭉 가서 바로 소각을 하거나, - 우회도로로 가서 중간 주차장에서 대기를 하고 있다가 나중에 소각장에서 신호를 줄 때 남은 우회도로를 따라 가서 소각을 한다. 즉, 주차장에서 대기를 하는 동안 다른 쓰레기차들이 새로 출발할 수도 있다. 주차장에서는 쓰레기차 여러 대가 함께 대기를 하고 있을 수 있는데, stack 모양으로 생겼기 때문에 소각장으로 재출발 하는 쓰레기차는 반드시 '현재 주차장에 있는 쓰레기차들 중에 가장 늦게 들어왔던 쓰레기차'여야 한다. 쓰레기차들이 어떤 경로와 순서로 움직일 지는 철저히 소각장의 명령에 따른다. 소각장 최고 관리자인 당신에게는 3일이 주어져있고, 하루에 한 대의 소각기계만을 작동시킬 수 있다. 그러나 매일 다른 소각기계를 사용해야 하는 것은 아니다. 또한 3일이 끝난 후, 서울에는 쓰레기차가 남아있어도 되지만 우회도로의 주차장에는 단 한 대의 차도 남아있지 않도록 해야 한다. 위의 조건을 만족시키면서 3일 동안 최대한 많은 쓰레기차들을 처리하려면 어떤 순서로 소각기계를 작동시켜야 하는지 구하는 프로그램을 작성하라. 만약 3일보다 짧게 모든 쓰레기차를 처리할 수 있다면, 가장 빨리 처리하는 방법을 구하라.
입력
표준 입력에서 다음의 입력을 읽는다. 첫 줄에는 쓰레기차의 개수를 나타내는 정수 N(1 $\leq$ N $\leq$ 20,000), 쓰레기의 종류 수를 나타내는 정수 K(1 $\leq$ K $\leq$ 1,000), 소각기계의 개수를 나타내는 정수 S(1 $\leq$ S $\leq$ 1,000)이 빈 칸을 사이에 두고 주어진다. 각각의 쓰레기차들에는 1부터 N까지의 번호가, 쓰레기의 종류에는 1부터 K까지의 번호가, 그리고 소각기계에는 1부터 S까지의 번호가 붙어있다. 다음 S개의 소각기계들에 대한 정보가 주어진다. 입력의 i+1번째 줄에는 소각기계 $M_i$가 소각할 수 있는 쓰레기의 종류들이 빈 칸을 사이에 두고 주어지고, 0을 마지막으로 하여 끝난다. 마지막 줄에는 N개의 정수 $s_1, \cdots , s_N $가 주어지는데, 그 중 i번째 숫자는 i번째 쓰레기차가 싣고 있는 쓰레기의 종류 $s_i$를 나타낸다. 각각의 쓰레기 종류 x에 대하여, x를 소각 할 수 있는 소각기계는 최대 10개까지밖에 없음에 유의하라.
출력
표준 출력으로 다음을 출력한다. 첫 번째 줄에 처리될 수 있는 쓰레기차들의 최대 개수를 출력한다. 두 번째 줄에는 그렇게 하기 위해서 3일 각각에 작동시켜야 하는 소각기계의 번호 3개를 순서대로 빈 칸을 사이에 두고 출력하다. 만약 2일만에 모든 쓰레기차를 처리할 수 있다면 세 번째 숫자를 0으로 출력하라. 비슷하게 하루 만에 모두 처리할 수 있다면 두 번째, 세 번째 숫자를 0으로 출력하라. 만일 답이 여러 가지 있을 수 있다면 아무거나 출력해도 된다.
힌트
다음 항목들에 대하여 부분점수를 받을 수 있다. - 테스트 케이스의 50%에 대해서는 N $\leq$ 10,000이고 S $\leq$ 300이다. - 출력의 첫 번째 줄만 맞은 경우는 전체 점수의 40%를 받을 수 있다. #### 입력 예시 ``` 13 5 4 1 0 4 5 0 5 3 0 2 5 0 4 5 2 5 5 4 1 1 5 4 5 3 3 ``` #### 출력 예시 ``` 11 2 1 4 ```