Abra's blog

By Abra, 13 years ago, translation, In English
Привет, мир! Это мой первый разбор, просьба сильно не пинать. =)
A. Разведка 2
Нахождение минимума в массиве, с одим дополнительным сравнением первого и последнего элементов.
B. Распродажа
Отрицательные элементы складываем в массив, сортируем, находим сумму m наибольших по модулю.
C. Список
Решается массивом булей, единственная заковыка - с выводом, но вполне преодолима.
D. Карта дорог
Создаем динамическую матрицу смежности, например, массивом стеков, заполняем. Потом волновым алгоритмом из r2, пробегаясь по каждой вершине один раз, пролучаем результирующий массив.
E. Столкновения
Заведем переменную времени ct, которая вначале равна 0.
Начинаем моделировать:
Пусть dt равен t - ct, просматриваем все пары шариков, по формуле 
x1 + v* dt = x2 + v2 * dt
dt = (x1 - x2) / (v2 - v1)
находим минимальную dt - промежуток времени, через который какие-нибудь шарики столкнуться, или время моделирования закончится.
Сдвигаем шарики на этот промежуток времени, снова просматриваем все пары, если координаты двух совпадают, меняем их скорости по формуле из условия.
Повторять, пока ct не сравняется с t.
Особое внимание стоит уделить точности, наверное на этом и подловили RAVEman'а с ACRush'ем. =)
В принятом решении я использовал double и точность сравнений 10-10.

Удачи в контестах!
  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Tutorial for CF 34D Road Map

Spoiler
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

code for problem D Road Map` 142366754