| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 139 | 18 | 18 | 20.455% |
한 물리 연구소에서는 암흑물질을 검출하기 위해 원형 입자가속기를 사용하고 있다. 과학자들은 편의를 위해 원주를 $N$등분하여 각 지점을 표시한 뒤, 시계 방향으로 $1$번부터 $N$번까지 번호를 붙였다. 시각 $t = 0$일 때 입자는 $1$번째 지점에 있다.
속력이 $u$인 입자는 단위 시간당 시계 방향으로 정확히 $u$개의 지점을 지난다. 즉, 음이 아닌 정수 $t_0$에 대해, $t=t_0$에 입자가 $i$번째 지점에 위치해 있고 이때의 속력을 $u$라고 하면 $t=t_0+1$에 입자는 $((i+u-1) \bmod N) + 1$번째 지점에 위치한다.
입자가속기는 입자의 속력을 단위 시간당 $a$만큼 증가시킨다. 구체적으로, 시각 $t$가 $0$ 이상 $1$ 미만일 때는 입자의 속력이 $v$로 일정하고, $1$ 이상 $2$ 미만일 때는 속력이 $v + a$로 일정하며, 일반적으로 음이 아닌 정수 $T$에 대해 $t$가 $T$ 이상 $T + 1$ 미만일 때 속력은 $v + Ta$로 일정하다.
가속기의 전체 $N$개의 지점 중 일부 지점에는 관측소가 설치되어 있다. 총 $M$개의 관측소가 설치되어 있으며, $i$번째 관측소는 $p_i$번째 지점에 설치되어 있다. $i$번째 관측소는 양의 정수 시각에서만 입자 관측을 시도할 수 있다. 이때 입자의 속력이 $s_i$ 이상이면서 위치가 관측소와 정확히 일치하는 경우에만 관측이 이루어진다. 입자 관측을 시도하면 $c_i$의 비용이 소모되며 $g_i$개의 관측 데이터를 얻을 수 있다. 그러나 장비에 부담을 주지 않기 위해 최대 $k_i$번만 관측을 시도할 수 있으며, 한 관측소에서 동시에 여러 번 입자 관측을 시도할 수는 없다. 단, 서로 다른 관측소의 위치가 같을 경우 두 개 이상의 관측소에서 동시에 입자 관측을 시도할 수 있다.
총 비용이 $B$ 이하가 되도록 관측을 시도하여 총 $G$개 이상의 관측 데이터를 얻을 수 있는 가장 이른 시각을 구하시오.
첫 번째 줄에 세 개의 정수 $N$, $a$, $v$가 공백으로 구분되어 주어진다.
두 번째 줄에 세 개의 정수 $M$, $B$, $G$가 공백으로 구분되어 주어진다.
다음 $M$개의 줄에 관측소에 대한 정보가 주어지며, 그중 $i$번째 줄에는 다섯 개의 정수 $p_i$, $s_i$, $c_i$, $g_i$, $k_i$가 공백으로 구분되어 주어진다.
첫 번째 줄에 시각 $t=T$에서 $G$개 이상의 관측 데이터를 얻을 수 있는 정수 $T$가 존재한다면 YES를, 아니라면 NO를 출력한다.
만약 그러한 $T$가 존재한다면, 두 번째 줄에 조건을 만족하는 가장 작은 정수 $T$를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $M, B \le 100$ |
| 2 | 80 | 추가 제약 조건 없음 |
2 0 0 1 1 1 2 0 1 1 1
NO
2 0 1 1 1 1 2 0 1 1 1
YES 1
9 0 1 2 5 10 2 0 1 2 5 5 0 1 2 5
YES 19
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest G번