| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 5 | 5 | 83.333% |
건축가 제이크는 우주 배달 사업에 대하여 영감을 얻어 스타트업 스타티링크(Star-T-Link)를 창업하였다. 제이크는 우주에 $N$개의 비콘을 설치하여 $N+2$개 단말 행성 간 택배를 배달하려고 한다. 비콘과 단말 행성 간 네트워크 구성은 처음 구축할 때 고정되어 바뀌지 않는다. 편의상 모든 비콘과 단말 행성을 통틀어서 노드라 부르자. 이때 네트워크는 아래 규칙을 만족한다.
제이크는 단말 행성에는 $-(N+2)$ 이상 $-1$ 이하의 정수 번호를, 비콘에는 $0$ 이상 $N-1$ 이하의 정수 번호를 매겼다. 비콘과 단말 행성 간 네트워크 구성으로 가능한 예는 아래 그림과 같다.
우주 공간 안에 있는 $N$개의 비콘은 수시로 암흑 물질의 영향을 받아 택배 서비스의 성능이 다소 불안정해질 수 있다. 따라서 제이크는 아래와 같은 방식으로 작동하는 프로토콜을 설계하였다.
제이크는 정책 $R$을 적절히 정한다면 각 단말 행성으로 도달하는 편지의 수만 확인해도 $N$개의 비콘이 암흑 물질의 영향을 받고 있는지 확인할 수 있다고 생각하는 것 같다. 제이크의 생각이 맞는지 프로그램으로 확인해보자.
여러분은 아래 함수를 구현해야 한다.
int[][] init(int[][] C)
health_check 함수가 호출되기 전에 한 번 호출된다.int[] health_check(int[] L)
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
모든 데이터에 대해서, $1 ≤ N ≤ 100\,000$; $1 ≤ Q ≤ 10$ 을 만족한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 1 | $N ≤ 10$ |
| 2 | 1 | $N ≤ 1\,000$ |
| 3 | 1 | 추가 제약조건은 없다. |
네트워크 구성이 본문에 있는 그림과 같은 경우를 생각해보자. 맨 처음에 init([[-1, -2, 1], [0, 2, -3], [1, -4, -5]]])이 호출된다.
제이크가 init 함수에서 정책 $R$ = [[1, 2, 0], [2, 2, 1], [2, 0, 1]]을 반환했다고 하자.
$0, 1, 2$번 비콘 중 $0$번 비콘만 암흑 물질의 영향을 받고 있다면 편지는 다음과 같이 배달된다.
이런 경우 health_check([2, 1, 0, 1, 1])이 호출되며 [1, 0, 0]을 반환해야 한다.
샘플 그레이더는 첫 번째 줄에 $N$, $Q$를 입력받는다. 두 번째 줄부터 $N$개의 줄에는 $C[i][j]$에 해당하는 정수 $3$개를 입력받는다. 그 다음 줄부터 $Q$개의 줄에는 각 비콘의 상태 $H[i]$에 해당하는 $N$개의 정수를 입력받는다. 채점 프로그램은 해당 값을 이용하여 $L[i]$를 계산한 다음 health_check 함수를 호출한다.
샘플 그레이더는 health_check 함수가 올바른지 여부에 따라 Correct 또는 Wrong을 출력한다.
실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하라. 그레이더는 적응적(adaptive)으로 호출할 health_check 함수의 인자가 init 함수의 반환값에 따라 바뀔 수 있다.
Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 ST번
C++17, C++20, C++17 (Clang), C++20 (Clang)