Хотелось бы узнать решения задач ↵
↵
http://acm.timus.ru/problem.aspx?space=1&num=1890\n↵
↵
http://acm.timus.ru/problem.aspx?space=1&num=1839\n↵
↵
http://acm.timus.ru/problem.aspx?space=1&num=2022\n↵
↵
http://acm.timus.ru/problem.aspx?space=1&num=1655\n↵
↵
↵
везде имею WA↵
↵
↵
1890 решаю так: строю HLD; имею 2 дерева отрезков: ↵
для суммы прибавок в департаментах (до корня) ↵
(с запросами изменить значение элемента и найти сумму на отрезке) ↵
и для суммы всех индивидуальных прибавок сотрудникам в корне с заданной вершиной ↵
(с запросами найти суммарную прибавку в элементе и прибавить значение на отрезок).↵
есть подозрения, что плохо считываю данные или имею переполнение типов↵
код(WA2):↵
https://ideone.com/fork/hprg2R↵
↵
↵
↵
↵
1839 решаю так: перебираю дуги и для каждой ищу рожицы: ↵
во-первых отсеим все неподходящие точки без условия 4);↵
получим претендентов Pret; теперь проблема только с условием 4).↵
Рассмотрим очередную точку Х из Pret; ↵
для неё нужно найти все такие Y из Pret, ↵
что cos(YRP)<cos(XRP) и cos(YPR)>cos(XPR); ↵
это можно сделать за логарифм для каждой точки Х с помощью ДО.↵
Код(WA3):↵
https://ideone.com/fork/HmAhfk↵
↵
↵
↵
2022 решаю так:пусть T-момент прыжка; до него движение описывается так:↵
x(t)=vx * t, y(t)=vy * t — g*t*t/2;↵
чтобы прыжок можно было совершить, необходимы условия: x(T)<L, y(T)>0, T>0, откуда получаем интервал для T;↵
далее полёт описывается так: x(t')=x(T) + (vx+ux) * t', y(t')=y(T) + (vy-g*T+uy)*t' — g*t'*t'/2; ↵
теперь необходимые условия пролёта через дырку выглядят так: ↵
в момент пролёта t1 через стену (т.е. когда x(t1)=x(T)+(vx+ux)*t1=L) в т. L нужно h<y(t1)<h+d,↵
в момент пролёта t2 через стену (т.е. когда x(t2)=x(T)+(vx+ux)*t2=L+l) в т. L+l нужно h<y(t2)<h+d,↵
(3) а также если максимальная высота ф-ии y(t') достигается на [t1, t2], то max(t')<h+d.↵
В итоге получаем некоторые интервалы решений (возникающие при решении неравенств), их пересекаем; потом (если выполняется (3), то некоторые из них обрезаем. Ответ=середина интервала длины не меньше 0.000001↵
Код(WA3) : писать не буду, т.к. сдавал без (3), а с (3) даже инпут не прохожу.↵
↵
↵
↵
1655 решаю так: пишу ДП: dp[i][j][0]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции i (где находится i корабль), dp[i][j][1]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции j (где находится j корабль). Особо пояснять нечего. Единственное, в реализации вместо делений на скорость я все числа умножал на неё.↵
Код (WA8):↵
https://ideone.com/GPQRO8
↵
http://acm.timus.ru/problem.aspx?space=1&num=1890
↵
http://acm.timus.ru/problem.aspx?space=1&num=1839
↵
http://acm.timus.ru/problem.aspx?space=1&num=2022
↵
http://acm.timus.ru/problem.aspx?space=1&num=1655
↵
↵
везде имею WA↵
↵
↵
1890 решаю так: строю HLD; имею 2 дерева отрезков: ↵
для суммы прибавок в департаментах (до корня) ↵
(с запросами изменить значение элемента и найти сумму на отрезке) ↵
и для суммы всех индивидуальных прибавок сотрудникам в корне с заданной вершиной ↵
(с запросами найти суммарную прибавку в элементе и прибавить значение на отрезок).↵
есть подозрения, что плохо считываю данные или имею переполнение типов↵
код(WA2):
↵
↵
↵
↵
1839 решаю так: перебираю дуги и для каждой ищу рожицы: ↵
во-первых отсеим все неподходящие точки без условия 4);↵
получим претендентов Pret; теперь проблема только с условием 4).↵
Рассмотрим очередную точку Х из Pret; ↵
для неё нужно найти все такие Y из Pret, ↵
что cos(YRP)<cos(XRP) и cos(YPR)>cos(XPR); ↵
это можно сделать за логарифм для каждой точки Х с помощью ДО.↵
Код(WA3):
↵
↵
↵
2022 решаю так:пусть T-момент прыжка; до него движение описывается так:↵
x(t)=vx * t, y(t)=vy * t — g*t*t/2;↵
чтобы прыжок можно было совершить, необходимы условия: x(T)<L, y(T)>0, T>0, откуда получаем интервал для T;↵
далее полёт описывается так: x(t')=x(T) + (vx+ux) * t', y(t')=y(T) + (vy-g*T+uy)*t' — g*t'*t'/2; ↵
теперь необходимые условия пролёта через дырку выглядят так: ↵
в момент пролёта t1 через стену (т.е. когда x(t1)=x(T)+(vx+ux)*t1=L) в т. L нужно h<y(t1)<h+d,↵
в момент пролёта t2 через стену (т.е. когда x(t2)=x(T)+(vx+ux)*t2=L+l) в т. L+l нужно h<y(t2)<h+d,↵
(3) а также если максимальная высота ф-ии y(t') достигается на [t1, t2], то max(t')<h+d.↵
В итоге получаем некоторые интервалы решений (возникающие при решении неравенств), их пересекаем; потом (если выполняется (3), то некоторые из них обрезаем. Ответ=середина интервала длины не меньше 0.000001↵
Код(WA3) : писать не буду, т.к. сдавал без (3), а с (3) даже инпут не прохожу.↵
↵
↵
↵
1655 решаю так: пишу ДП: dp[i][j][0]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции i (где находится i корабль), dp[i][j][1]-минимальное время уничтожения кораблей на [i,j], если мы находимся в позиции j (где находится j корабль). Особо пояснять нечего. Единственное, в реализации вместо делений на скорость я все числа умножал на неё.↵
Код (WA8):
