온라인 퀴즈 시스템

시간 제한8초메모리 제한512 MB

요약

플레이어별 지연과 각 플레이어의 답안 제출 시각이 주어질 때, 폴링 프로토콜을 시뮬레이션하여 서버와 각 플레이어가 주고받은 바이트 수를 계산한다.

난이도: 어려움10점 중 8점
유형: 시뮬레이션, 구현, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

인터넷으로 진행하는 퀴즈 서비스가 있다. 서버 한 대와 플레이어 $M$ 명이 참가한다. 서버에 배정된 대역폭이 좁아서 주고받는 데이터 양을 최대한 줄여야 하고, 퀴즈가 진행되는 동안 모든 플레이어의 진행이 서로 맞아야 한다. 한 게임 동안 클라이언트와 서버가 주고받는 패킷을 시뮬레이션해서 양쪽이 보내고 받은 데이터 양을 구하라.

게임은 다음과 같이 진행한다. 참가하는 플레이어와 사용할 문제는 미리 정해져 있다. 모든 플레이어가 같은 클라이언트를 쓰고 문제 지문은 이미 내려받은 상태이므로 이 부분은 시뮬레이션하지 않는다. 게임이 시작되면 첫 번째 문제를 제시하고, 플레이어는 정해진 시간 안에 답을 제출한다. 이어서 두 번째 문제를 제시하고, 같은 방식으로 계속한다. 문제를 모두 끝내면 게임이 끝난다. 한 문제가 진행되는 동안 플레이어는 다른 플레이어의 상황을 통지받는다. 자기 답을 제출하기 전에는 누가 이미 답을 제출했는지 알 수 있고, 자기 답을 제출한 뒤에는 다른 플레이어가 어떤 답을 제출했는지도 알 수 있다.

한 문제 구간이 시작되면 서버는 모든 플레이어에게 문제 시작 동기화 패킷을 보내고 폴링을 시작한다. 폴링을 시작한 뒤 1,000밀리초마다 서버는 그 시각보다 엄격히 앞서 도착했고 아직 통지하지 않은 답이 있는지 확인한다. 그런 답이 하나라도 있으면 모든 플레이어에게 통지를 보낸다.

서버가 아직 답을 받지 못한 플레이어에게는 새로 도착한 답을 담은 통지 패킷 A형을 보낸다.
새로 도착한 답 중에 자기 답이 있는 플레이어에게는, 그 시각보다 엄격히 앞서 도착한 다른 플레이어의 답 전체, 즉 자기 답을 제외한 답 전체를 담은 통지 패킷 B형을 보낸다.
앞선 확인에서 이미 답이 통지된 플레이어에게는 새로 도착한 답을 담은 통지 패킷 B형을 보낸다.
A형이든 B형이든 통지 패킷에는 적어도 한 플레이어의 정보가 들어가야 한다. 담을 정보가 하나도 없으면 그 패킷은 보내지 않는다.

문제 시작 동기화 패킷을 보낸 뒤 20,000밀리초가 지나면 서버는 같은 확인을 마지막으로 한 번 더 하고, 필요한 통지 패킷을 보낸 다음, 모든 플레이어에게 문제 종료 동기화 패킷을 보내 그 문제를 끝낸다.

플레이어는 문제 시작 동기화 패킷을 받은 뒤부터 문제 종료 동기화 패킷을 받기 전까지 답을 제출할 수 있다. 답은 답안 패킷으로 보낸다.

플레이어 $i$ 와 서버 사이의 편도 지연은 $D_i$ 밀리초다. 서버가 시각 $t$ 에 보낸 패킷은 플레이어 $i$ 에게 시각 $t + D_i$ 에 도착하고, 플레이어 $i$ 가 시각 $t$ 에 보낸 패킷은 서버에 시각 $t + D_i$ 에 도착한다.

패킷 구조는 아래와 같고, 크기의 단위는 바이트다.

표 1: 문제 시작 동기화 패킷

항목	크기
패킷 헤더	3

표 2: 답안 패킷

항목	크기
패킷 헤더	3
플레이어 번호	1
답 데이터 크기 ( $= L$ )	1
답 데이터	$L$

표 3: 다른 플레이어의 답을 알리는 통지 패킷 A형

항목	크기
패킷 헤더	3
다른 플레이어의 답 개수 ( $= N$ )	1
아래 한 줄이 $N$ 번 반복
플레이어 번호	1

표 4: 다른 플레이어의 답을 알리는 통지 패킷 B형

항목	크기
패킷 헤더	3
다른 플레이어의 답 개수 ( $= N$ )	1
아래 세 줄이 $N$ 번 반복
플레이어 번호	1
답 데이터 크기 ( $= L_i$ )	1
답 데이터	$L_i$

표 5: 문제 종료 동기화 패킷

항목	크기
패킷 헤더	3
결과	1

따라서 A형 패킷의 크기는 $4 + N$ 바이트이고, B형 패킷의 크기는 $4 + \sum_{i=1}^{N} (2 + L_i)$ 바이트다.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 플레이어 수 $M$ 과 문제 수 $N$ 이 주어진다 ( $1 \le M, N \le 100$ ). 다음 줄에는 음이 아닌 정수 $D_0, D_1, \ldots, D_{M-1}$ 이 주어진다 ( $0 \le D_i \le 10^4$ ). $D_i$ 는 플레이어 $i$ 와 서버 사이의 편도 지연이며 단위는 밀리초다. 플레이어 번호는 $0$ 부터 $M-1$ 까지다.

그다음에는 문제를 제시하는 순서대로 $N$ 개의 블록이 온다. 각 블록의 첫 줄에는 그 문제에 답을 제출한 플레이어 수 $L$ 이 주어지고 ( $0 \le L \le M$ ), 이어서 $L$ 개의 줄이 온다. 각 줄에는 공백으로 구분된 세 값 $P$ , $T$ , $A$ 가 주어진다. $P$ 는 플레이어 번호, $T$ 는 플레이어 $P$ 가 문제 시작 동기화 패킷을 받은 순간부터 답을 제출한 순간까지 플레이어 쪽에서 흐른 시간(밀리초), $A$ 는 그 플레이어의 답으로 길이가 1 이상 9 이하인 영숫자 문자열이다. 한 블록의 $L$ 개 줄은 임의의 순서로 주어지고, 같은 플레이어가 한 블록에 두 번 나오지 않는다. 모든 답안 패킷은 문제 시작 동기화 패킷을 보낸 뒤 19,999밀리초 안에 서버에 도착한다. 즉 $T + 2 \times D_P \le 19999$ 이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스마다 $M + 1$ 개의 줄을 출력한다. 첫 줄에는 서버가 보낸 데이터 양과 받은 데이터 양을 공백으로 구분해 출력한다. 다음 $M$ 개의 줄에는 플레이어 번호가 커지는 순서로 각 플레이어가 보낸 데이터 양과 받은 데이터 양을 공백으로 구분해 출력한다. 연속한 두 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제2

예제 1

입력

3 2
1 2 10
3
0 3420 o
1 4589 o
2 4638 x
3
1 6577 SUZUMIYA
2 7644 SUZUMIYA
0 19979 YASUZUMI
4 2
150 150 150 150
4
0 1344 HOGEHOGE
1 1466 HOGEHOGE
2 1789 HOGEHOGE
3 19100 GEHO
2
2 1200 SETTEN
3 700 SETTEN
0 0

예상 출력

예제 2
입력
```
1 1
0
1
0 500 A
0 0
```
예상 출력
```
7 6
6 7
```