JOI 2014/2015 예선 2- 스파이 게임 (Spy) > 문제은행 : 정보올림피아드&알고리즘




2831 : 스파이 게임 (Spy)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
27 회   
시도횟수
38 회   

문제

석환이와 N명의 친구들이 방에 모여서 스파이 게임을 한다. 사회자 석환이는 매 라운드마다 스파이를 한 명 지목한다. 스파이는 오직 석환이와 스파이 자신만 알고 있다. N명의 친구들이 5분 동안 담소의 시간을 갖다가, 시간이 지나면 N명의 친구들은 각자 스파이일 것 같은 사람 한 명을 지목한다. 자기 자신을 스파이로 지목할 수도 있기 때문에, 스파이는 당연히 자기 자신을 지목한다.

 

스파이 지목이 끝나면, 석환이는 스파이가 누구인지 말한다. 스파이를 맞춘 모든 사람(스파이 포함)은 1점을 획득하고, 스파이는 추가적으로 스파이를 못 맞춘 사람의 수만큼 점수를 더 획득한다.

 

석환이와 친구들은 이 게임을 총 M라운드 하고 잠자리에 들었다. 다음날, 석환이가 가장 점수가 높은 친구에게 아이스크림을 사 주려고 했더니, 다들 자기가 가장 점수가 높다고 한다. 기억을 더듬어 봤더니, 친구들의 점수는 기억이 안 나지만 누가 스파이를 했고 누가 누구를 지목했는지에 대해서는 어렴풋이 기억이 난다. 이 정보를 토대로 친구들의 점수를 복원하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 사람의 수 N이 주어진다. (3 ≤ N ≤ 100) 두 번째 줄에는 게임을 한 횟수 M이 주어진다. (3 ≤ M ≤ 100) 세 번째 줄에는 각 라운드에 스파이를 했던 친구의 번호 Ai가 주어진다. (1 ≤ Ai ≤ N) 네 번째 줄부터 M개의 줄에는 1~N번 친구가 스파이로 지목한 친구의 번호가 주어진다. 매 라운드의 스파이는 항상 자기 자신을 지목하고 있음에 유의하여라.

출력형식

N줄에 걸쳐, 한 줄에 하나씩 각 친구의 점수를 출력한다.

입력 예

3
4
1 2 3 2
1 1 2
3 2 2
1 1 3
2 2 2

출력 예

3
4
5

입력 예

5
3
3 3 1
2 4 3 3 3
4 3 3 3 1
1 3 4 1 1

출력 예

3
1
6
3
2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP