Similar presentations:
Разбор задачи «Велогонка»
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.
dVdV
T
dX
T
dX
T
T