Codeforces Round 614 (Div. 1) |
---|
Закончено |
С новым телом наш идол Арома Белая (или лучше было сказать Каори Минамийа?) начинает восстанавливать своё потерянное прошлое через OS-пространство.
Это пространство можно представить как 2D плоскость, с бесконечным количеством устройств с данными, пронумерованных с $$$0$$$. Координаты устройств можно описать следующим образом:
Изначально Арома расположена в точке $$$(x_s, y_s)$$$. Она может находиться в OS-пространстве не более $$$t$$$ секунд, после этого ей придётся вернуться в реальный мир. Чтобы вернутся в реальный мир не требуется возвращаться в изначальную точку $$$(x_s, y_s)$$$.
Внутри OS-пространства Арома может делать следующие действия:
Арома хочет собрать как можно больше данных перед тем как вернётся назад. Помогите ей определить максимальное количество устройств с данными, которые она сможет собрать за $$$t$$$ секунд.
Первая строка содержит целые числа $$$x_0$$$, $$$y_0$$$, $$$a_x$$$, $$$a_y$$$, $$$b_x$$$, $$$b_y$$$ ($$$1 \leq x_0, y_0 \leq 10^{16}$$$, $$$2 \leq a_x, a_y \leq 100$$$, $$$0 \leq b_x, b_y \leq 10^{16}$$$), которые задают координаты устройств с данными.
Вторая строка содержит целые числа $$$x_s$$$, $$$y_s$$$, $$$t$$$ ($$$1 \leq x_s, y_s, t \leq 10^{16}$$$), изначальные координаты Аромы и доступное время.
Выведите одно целое число — максимальное количество устройств с данными которые Арома сможет собрать за $$$t$$$ секунд.
1 1 2 3 1 0 2 4 20
3
1 1 2 3 1 0 15 27 26
2
1 1 2 3 1 0 2 2 1
0
Во всех трёх примерах, координаты первых $$$5$$$ устройств равны $$$(1, 1)$$$, $$$(3, 3)$$$, $$$(7, 9)$$$, $$$(15, 27)$$$ и $$$(31, 81)$$$ (напомним, что устройства пронумерованы начиная с $$$0$$$).
В первом примере оптимальный маршрут чтобы собрать $$$3$$$ вершины выглядит следующим образом:
Во втором примере оптимальный маршрут чтобы собрать $$$2$$$ вершины выглядит следующим образом:
В третьем примере Арома не может собрать ни одного устройства. Пожалуй стоило отдохнуть, а не рваться в OS-пространство без подготовки.
Название |
---|