레이팅 미적용베시는 길이 \(K\)(\(1\le K\le 10^9\))미터의 경주를 뛰고 있다. 베시는 초속 0미터의 속력으로 달리기 시작한다. 매초마다 속력을 초속 1미터만큼 늘리거나, 그대로 유지하거나, 초속 1미터만큼 줄일 수 있다. 예를 들어 첫 1초 동안 속력을 초속 1미터로 늘려 1미터를 달릴 수도 있고, 초속 0미터를 유지하여 0미터를 달릴 수도 있다. 베시의 속력은 절대 0 아래로 떨어질 수 없다.
베시는 항상 결승선을 향해 달리며, 정수 초가 지난 후에 완주하고 싶다(이 정수 시각에 결승선에 정확히 도달하거나 지나쳐서 끝난다). 게다가 결승선에서 너무 빠르게 달리고 있고 싶지는 않다. 베시가 \(K\)미터를 완주하는 그 순간, 방금까지 달리던 속력이 초속 \(X\)(\(1 \leq X \leq 10^5\))미터 이하이기를 바란다. 베시는 \(N\)(\(1 \leq N \leq 1000\))개의 서로 다른 \(X\) 값에 대해 얼마나 빨리 경주를 마칠 수 있는지 알고 싶다.
문제 제공: Nick Wu
점수 배점
- 테스트 케이스 2-4는 \(N=X=1\)을 만족한다.
- 테스트 케이스 5-10은 추가 제약이 없다.
문제 제공: Nick Wu
첫째 줄에 두 정수 \(K\)와 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 각각 정수 \(X\)가 하나씩 주어진다.
\(N\)개의 줄을 출력한다. 각 줄에는 베시가 \(X\) 이하의 속력으로 끝나도록 \(K\)미터를 달리는 데 필요한 최소 시간을 나타내는 정수를 하나씩 출력한다.
race.in · 출력을 쓸 파일 race.out10 5
1
2
3
4
56
5
5
4
4When \(X = 1\), an optimal solution is:
- Increase speed to 1 m/s, travel 1 meter
- Increase speed to 2 m/s, travel 2 meters, for a total of 3 meters
- Keep speed at 2 m/s, travel 5 meters total
- Keep speed at 2 m/s, travel 7 meters total
- Keep speed at 2 m/s, travel 9 meters total
- Decrease speed to 1 m/s, travel 10 meters total
When \(X = 3\), an optimal solution is:
- Increase speed to 1 m/s, travel 1 meter
- Increase speed to 2 m/s, travel 3 meters total
- Increase speed to 3 m/s, travel 6 meters total
- Keep speed at 3 m/s, travel 9 meters total
- Keep speed at 3 m/s, travel 12 meters total
Note that the following is illegal when \(X = 3\):
- Increase speed to 1 m/s, travel 1 meter
- Increase speed to 2 m/s, travel 3 meters total
- Increase speed to 3 m/s, travel 6 meters total
- Increase speed to 4 m/s, travel 10 meters total
This is because at the instant when Bessie has finished running 10 meters, her
speed is 4 m/s.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > January > Bronze