| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 63 | 37 | 33 | 56.897% |
연세대학교 레이싱 팀은 대회에 참가했다. 대회를 완주하기 위해서는 트랙을 $M$바퀴 돌아야 한다. 트랙은 둘레의 길이가 $L$인 원이다. 트랙에는 시작 지점이 존재하고 시작 지점에서 출발해 $L$만큼 주행하면 한 바퀴를 돈 것으로 인정된다. 트랙은 원형이므로 시작 지점에서 $L$만큼 주행하면 다시 시작 지점에 도착하게 된다.
레이싱카가 움직이기 위해서는 반드시 시작 지점에서 타이어를 장착한 후 주행해야 한다. 연세대학교 레이싱 팀은 $N$개의 타이어를 준비해 왔고 오직 순서대로만 교체할 수 있다. $i$번째 타이어로 교체하자마자 $i+1$번째 타이어로 교체하는 것도 가능하다. 그러나 $N$번째 타이어로 교체한 이후에는 더 이상 교체할 수 있는 타이어가 없으므로 더 이상 교체할 수 없다.
타이어는 매 분마다 성능이 있다. $t$분에 어떤 타이어의 성능이 $v$라면 $t+1$분까지 현재 위치에서 최대 $v$만큼 주행할 수 있다. 즉, $t$분의 레이싱카의 위치가 $x$라면 $t+1$분에는 $[x,x+v]$에 위치할 수 있다. 그러나 어떤 위치에 도착해도 $t+1$분에 도착하게 된다. 따라서 완주 및 교체는 오직 정수 시간에만 이루어질 수 있다.
타이어마다 3개의 옵션 $a_i,ドル $b_i,ドル $d_i$이 각각 주어진다. $i$번째 타이어는 교체하자마자 $a_i$의 성능을 지닌다. 이후 성능이 $b_i$에 이르기까지 매 분마다 성능이 $d_i$씩 감소한다. 따라서 $t$분의 타이어의 성능이 $v$였을때, $v=b_i$라면 $t+1$분의 성능 또한 $b_i$이고 $v > b_i$라면 $t+1$분의 성능은 $v-d_i$이다.
오직 시작 지점에서만 타이어를 교체할 수 있다. 연세대학교의 메카닉들은 매우 숙련되었기 때문에 타이어를 장착하거나 탈착하는 시간은 무시한다.
0분에 레이싱 경기가 시작한다. 맨 처음 레이싱카에는 아무런 타이어도 장착되어 있지 않다. 몇 분 만에 연세대학교 레이싱팀이 대회를 완주할 수 있는지 구해보자.
입력은 아래와 같이 주어진다.
$N M L$
$a_1$ $b_1$ $d_1$
...
$a_N$ $b_N$ $d_N$
몇 분 만에 연세대학교 레이싱 팀이 대회를 완주할 수 있는지 출력한다.
2 2 10 8 4 4 16 1 15
3
연세대학교 레이싱 팀은 다음과 같이 움직인다.
$t=0$분에 1번 타이어를 장착하고 8만큼 주행한다. $d_1=4$이므로 $t=1$분의 타이어 성능은 4가 된다.
$t=1$분에 레이싱카의 위치는 8이다. 최대 4만큼 주행할 수 있으므로 2만큼 주행해 시작 지점에 도착한다. $b_1=4$이므로 $t=2$분의 타이어 성능 또한 4이다.
$t=2$분에는 시작 지점에서 2번 타이어로 교체하고, 10만큼 주행한다. 레이싱카는 $t=3$분에 결승선을 통과하게 된다.
3 4 5 4 2 2 12 6 3 2 1 1
2
2 100 1000000000 100 100 50 10000 1 9999
1000000000
2 10 500 10000 1 9999 100 100 50
1
1 100 1000000000 1 1 2
100000000000
University > 연세대학교 > 2022 연세대학교 프로그래밍 경진대회 H번