Привет, мир! Это мой первый разбор. =)
C. Список
Решается массивом булей, единственная заковыка - с выводом, но вполне преодолима.
D. Карта дорог
Создаем динамическую матрицу смежности, например, массивом стеков, заполняем. Потом волновым алгоритмом из r2, пробегаясь по каждой вершине один раз, пролучаем результирующий массив.
E. Столкновения
Заведем переменную времени ct, которая вначале равна 0.
Начинаем моделировать:
Пусть dt равен t - ct, просматриваем все пары шариков, по формуле
x1 + v1 * dt = x2 + v2 * dt
dt = (x1 - x2) / (v2 - v1)
находим минимальную dt - промежуток времени, через который какие-нибудь шарики столкнуться, или время моделирования закончится.
Сдвигаем шарики на этот промежуток времени, снова просматриваем все пары, если координаты двух совпадают, меняем их скорости по формуле из условия.
Повторять, пока ct не сравняется с t.
Особое внимание стоит уделить точности, наверное на этом и подловили RAVEman'а с ACRush'ем. =)
В принятом решении я использовал double и точность сравнений 10-10.
Удачи в контестах!
A. Разведка 2
Нахождение минимума в массиве, с одим дополнительным сравнением первого и последнего элементов.B. Распродажа
Отрицательные элементы складываем в массив, сортируем, находим сумму m наибольших по модулю.C. Список
Решается массивом булей, единственная заковыка - с выводом, но вполне преодолима.D. Карта дорог
Создаем динамическую матрицу смежности, например, массивом стеков, заполняем. Потом волновым алгоритмом из r2, пробегаясь по каждой вершине один раз, пролучаем результирующий массив.E. Столкновения
Заведем переменную времени ct, которая вначале равна 0.Начинаем моделировать:
Пусть dt равен t - ct, просматриваем все пары шариков, по формуле
x1 + v1 * dt = x2 + v2 * dt
dt = (x1 - x2) / (v2 - v1)
находим минимальную dt - промежуток времени, через который какие-нибудь шарики столкнуться, или время моделирования закончится.
Сдвигаем шарики на этот промежуток времени, снова просматриваем все пары, если координаты двух совпадают, меняем их скорости по формуле из условия.
Повторять, пока ct не сравняется с t.
Особое внимание стоит уделить точности, наверное на этом и подловили RAVEman'а с ACRush'ем. =)
В принятом решении я использовал double и точность сравнений 10-10.
Удачи в контестах!
Те решения, которые проходят, похоже, сортируют точки по координате (их порядок в процессе не меняется) и потом сравнивают скорости соседних. Тогда все работает.
"некоторые не учитывали, что может быть несколько столкновений в один момент"
Ты учитываешь :)
Tutorial for CF 34D Road Map
In this problem, the root of the tree is $$$r_1$$$. Suppose you want to go to an arbitrary node $$$x$$$ from the root $$$r_1$$$ and the last city on the way to go to $$$x$$$ is $$$y$$$, then $$$y$$$ is the $$$parent$$$ of $$$x$$$. It is true because the nearest node in the way to go the $$$root$$$ from an arbitrary node is it's $$$parent$$$. But the question is how can we get the whole tree? It is possible because you are getting the $$$parents$$$ for all nodes which is enough to build a tree.
Now you can see that, the problem has became 'Change the root from $$$r_1$$$ to $$$r_2$$$ and then find the parents for all nodes.' So we can run a DFS from the new root $$$r_2$$$ to find the parents for all nodes.
Sorry for my poor English.
code for problem D Road Map` 142366754