| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 538 | 213 | 185 | 45.567% |
FuriosaAI는 데이터센터 및 고성능 엣지를 위한 AI 반도체를 개발한다. 2세대 제품 RNGD는 자체 설계한 아키텍처인 TCP(Tensor Contraction Processor) 기반의 인공지능 가속기로, PyTorch 등 주요 프레임워크와 호환되는 SDK를 제공한다.
RNGD에서 인공지능 모델의 추론을 수행하려면, 먼저 모델에서 수행하는 계산을 RNGD 명령어들의 나열로 변환하는, 즉 컴파일하는 과정이 필요하다. 실제 컴파일 과정을 단순화한 다음과 같은 상황을 가정해보자.
RNGD 연산 시간의 기본 단위는 사이클로, 모델의 실행은 총 $H$ 사이클 이내에 끝나야 한다는 제한이 있다. $H$개의 사이클을 순서대로 사이클 1ドル,ドル 사이클 2ドル,ドル $\cdots,ドル 사이클 $H$라고 부르자.
컴파일된 인공지능 모델에는 총 $N$개의 연산이 있으며, 이 중 $i$번째 연산은 사이클 $A_i$부터 사이클 $B_i$까지 실행된다. 실행되는 사이클이 서로 겹치는 연산들이 있을 수도 있다.
RNGD에서 컴파일된 모델을 실행하는 도중에 추가 연산 하나를 함께 수행해야 한다는 요청이 들어왔다. 이때 추가 연산은 기존 $N$개의 연산 중 어느 것과도 실행 사이클이 겹치면 안 되며, $H$ 사이클 이내에서 수행이 완료되어야 한다. 구체적으로,
추가 연산의 종류에 따라 소요되는 사이클 수 $T$가 달라질 수 있으므로, $Q$가지 시나리오를 미리 검토하려 한다. $i$번째 시나리오에서 추가 연산을 수행하는 데 $T_i$ 사이클이 필요한 경우, 조건을 만족하는 시작 사이클 $S$가 총 몇 개인지 빠르게 계산해보자.
각 시나리오의 추가 연산은 누적되지 않음에 유의하라.
첫째 줄에 인공지능 모델을 구성하는 연산의 수 $N,ドル 전체 사이클 수 $H$가 공백으로 구분되어 주어진다. (0ドル \leq N \leq 200,000円$; 1ドル \leq H \leq {10}^9$)
이후 $N$개의 줄에 걸쳐, 그 중 $i$번째 줄에 $i$번째 연산이 실행되는 시작 사이클과 종료 사이클을 가리키는 두 정수 $A_i, B_i$가 공백으로 구분되어 주어진다. (1ドル \leq A_i \leq B_i \leq H$)
그 다음 줄에 시나리오의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 200,000円$)
이후 $Q$개의 줄에 걸쳐, 추가 연산의 소요 사이클 수 $T_i$가 주어진다. (1ドル \leq T_i \leq H$)
$Q$개의 줄에 각 시나리오에 대한 정답을 순서대로 출력한다.
3 30 5 8 12 19 14 23 3 2 4 6
11 5 2
0 4 2 1 2
4 3
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2025 예선 D번