Разбор задачи «Велогонка»

1.

Разбор задачи «Велогонка»
Автор задачи: С.Г. Волченков

2.

Подзадача 1 (20 баллов)
2 ≤ n ≤ 50, 0 ≤ xi ≤ 1000, 0 ≤ vi ≤ 1000, t ≤ 1000, t целое
T=0
Ans (T = 0)
T=1
Ans (T = 1)

3.

Подзадача 2 (20 баллов)
2 ≤ n ≤ 200.
[T1, T2]
V2
V1
D
D
V2 – V1 > 0
T1
T2
D
V2 – V1 < 0
T1
T2
D
V2 – V1 = 0
T1
T2

4.

Подзадача 2 (20 баллов)
2 ≤ n ≤ 200.
O(N2) обгонов,O(N2) интересных моментов
времени.
Ответ вычисляется за O(N)
Решение за O(N3)

5.

Подзадача 3 (30 баллов)
2 ≤ n ≤ 2000.
[T1, T2]
V1
V2
?
D
D
V2 – V1 > 0
T1
T2
D
V2 – V1 < 0
T1
T2
D
V2 – V1 = 0
T1
T2

6.

Подзадача 3 (30 баллов)
2 ≤ n ≤ 2000.
Нас интересуют обгоны лидера и аутсайдера
Каждый может стать лидером и аутсайдером 1 раз. O(N)
интересных моментов времени.
Решение за O(N2)
DT1
DT5
DT2
DT6
DT3
DT7
DT4
DT8

7.

Подзадача
баллов)
4
(30
2 ≤ n ≤ 105.
V1
V2
dX
Cкорость аутсайдера V1 убывает с каждым обгоном
Скорость лидера V2 возрастает с каждым обгоном
dV(t) = V2(t) – V1(t) - неубывает
dV(t) < 0 => dX(t) возрастает
dV(t) > 0 => dX(t) убывает
dV(t) = 0 => dX(t) постоянно

8.

dV
dV
T
dX
T
dX
T
T