| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 44 | 24 | 13 | 52.000% |
Albert는 $N$ 대의 컴퓨터로 구성된 클러스터를 갖고 있는데, 현재 모든 컴퓨터는 malware 에 감염된 상태이다 (편의상 컴퓨터는 1,ドル 2, \dots, N$ 으로 번호가 붙어있다).
현재 총 $M$ 쌍의 컴퓨터가 방화벽 없는 "연결망"을 통해 연결되어있는데, 이를 통해 malware 가 계속 전파될 수 있다. 구체적으로, $X, Y$ 크기가 $M$ 인 정수 배열일 때 (각 $X_i, Y_i$ 값은 컴퓨터 번호이다), 매일 저녁에 아래와 같은 일이 일어난다:
예를 들어 아래 그림은 $N = 5, M = 6,ドル $X = [5, 3, 2, 1, 5, 3],ドル $Y = [4, 2, 4, 2, 2, 1]$ 인 경우를 나타낸다.
Albert는 급조한 소프트웨어를 이용하여 모든 컴퓨터의 데이터를 스캔한 후 주기적으로 malware를 박멸해보려고 한다.
예를 들어 위와 같은 클러스터가 있고, $P = 7$ 이고 $C = [1, 4, 2, 6, 7]$ 이라 하자. 이 때 아래와 같은 순서로 소프트웨어가 동작한다.
0일
모든 컴퓨터가 이미 malware에 감염된 상태이다.
감염된 컴퓨터: 1, 2, 3, 4, 5
모든 컴퓨터가 이미 malware에 감염된 상태이다.
감염된 컴퓨터: 1, 2, 3, 4, 5
1일
$C_1 = 1$ 이므로 소프트웨어는 컴퓨터 1의 malware를 박멸한다.
감염된 컴퓨터: 2, 3, 4, 5
3ドル \to 1$ 연결망 때문에 컴퓨터 1이 다시 malware에 감염된다.
감염된 컴퓨터: 1, 2, 3, 4, 5
2일
$C_3 = 2$ 이므로 소프트웨어는 컴퓨터 3의 malware를 박멸한다.
감염된 컴퓨터: 1, 2, 4, 5
컴퓨터 3은 malware에 다시 감염되지 않는다 ($Y_i = 3$ 인 경우가 없다).
감염된 컴퓨터: 1, 2, 4, 5
3일
$C_i = 3$ 인 경우가 없으므로 박멸되는 malware 가 없다.
감염된 컴퓨터: 1, 2, 4, 5
변화 없음.
감염된 컴퓨터: 1, 2, 4, 5
4일
$C_2 = 4$ 이므로 소프트웨어는 컴퓨터 2의 malware를 박멸한다.
감염된 컴퓨터: 1, 4, 5
1ドル \to 2$ 연결망 때문에 컴퓨터 2가 다시 malware 에 감염된다.
감염된 컴퓨터: 1, 2, 4, 5
5일
$C_i = 5$ 인 경우가 없으므로 박멸되는 malware 가 없다.
감염된 컴퓨터: 1, 2, 4, 5
변화 없음.
감염된 컴퓨터: 1, 2, 4, 5
6일
$C_4 =6$ 이므로 소프트웨어는 컴퓨터 4의 malware를 박멸한다.
감염된 컴퓨터: 1, 2, 5
2ドル \to 4$ 그리고 5ドル \to 4$ 연결망 때문에 컴퓨터 4가 다시 malware에 감염된다.
감염된 컴퓨터: 1, 2, 4, 5
7일
$C_5 =7$ 이므로 소프트웨어는 컴퓨터 5의 malware를 박멸한다.
감염된 컴퓨터: 1, 2, 4
컴퓨터 5는 malware에 다시 감염되지 않는다 ($Y_i = 5$ 인 경우가 없다).
감염된 컴퓨터: 1, 2, 4
$P = 7$ 이므로, 8일째 부터는 소프트웨어가 다시 처음부터 가동됨에 유의하자.
$C_1 = 1$ 이므로 소프트웨어는 컴퓨터 1의 malware를 박멸한다.
감염된 컴퓨터: 2, 4
컴퓨터 3이 malware에 감염되지 않았으므로, 컴퓨터 1도 다시 감염되지 않는다.
감염된 컴퓨터: 2, 4
$C_3 = 2$ 이므로 소프트웨어는 컴퓨터 3을 처리한다. (이미 박멸된 상태이므로 변화가 없다.)
감염된 컴퓨터: 2, 4
변화 없음.
감염된 컴퓨터: 2, 4
변화 없음.
감염된 컴퓨터: 2, 4
변화 없음.
감염된 컴퓨터: 2, 4
$C_2 = 4$ 이므로 소프트웨어는 컴퓨터 2의 malware를 박멸한다.
감염된 컴퓨터: 4
변화 없음.
감염된 컴퓨터: 4
변화 없음.
감염된 컴퓨터: 4
변화 없음.
감염된 컴퓨터: 4
$C_4 =6$ 이므로 소프트웨어는 컴퓨터 4의 malware를 박멸한다.
감염된 컴퓨터: 없음
변화 없음.
감염된 컴퓨터: 없음
소프트웨어는 계속 작동하지만 모든 컴퓨터에서 malware가 박멸된 상태로 유지된다.
변화 없음.
Albert는 매일 밤 11시에 malware에 감염된 컴퓨터의 수를 측정하는 버릇이 있는데, $j$ 번째 날 밤 11시를 기준으로 malware에 감염된 컴퓨터의 수를 $S_j$ 라 하자. Albert는 1일째부터 $K$ 일째 밤까지 이 값을 측정하여, 그 총합인 $\sum_{1 \le j \le K} S_j$ 가 무엇인지 알고 싶다. 위의 예제에서 $K = 11$ 이라면 $S = [5, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1]$ 이 되므로 정답은 35가 된다.
입력으로 $N, M, C, X, Y, P, K$가 주어졌을 때, $\sum_{1 \le j \le K} S_j$ 값을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.
각 테스트 케이스의 첫 줄에는 $N, M, P, K$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $C$ 의 값인 $N$ 개의 정수가 공백으로 구분되어 주어진다. 다음 $M$ 줄에 걸쳐 각 줄에 한 쌍의 정수가 공백으로 구분되어 주어지는데, 이는 방화벽 없이 연결된 컴퓨터 쌍 $X_i, Y_i$ 를 나타낸다.
각 테스트 케이스의 정답인 $\sum_{1 \le j \le K} S_j$ 값을 10ドル^9 + 7$ 로 나눈 나머지를 각 줄에 출력한다.
8 5 6 7 11 1 4 2 6 7 5 4 3 2 2 4 1 2 5 2 3 1 2 2 5 8 2 4 1 2 2 1 4 4 7 15 5 1 4 3 4 3 1 3 2 1 4 1 5 5 7 20 1 2 3 4 5 1 2 2 3 3 4 4 1 3 5 5 4 7 10 4 1 2 3 5 1 2 2 3 3 4 4 5 5 4 7 10 5 1 2 4 6 1 2 2 3 3 4 4 5 3 2 7 10 2 4 6 1 2 2 3 3 2 7 10 6 4 2 1 2 2 3
35 16 16 100 37 39 9 25
예제 1: 본문에서 다루었다.
예제 2: 컴퓨터 두 대가 서로 malware를 계속 전파하므로 언제나 $S_j = 2$ 이다.
예제 3: $S = [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0]$ 이다.
예제 4: 언제나 $S_j = 5$ 이다.
예제 5-8: 추가 설명 없음