Задача A: Кольцевая
Это довольно простая задача - мы имеем цикл, можем ориентировать его в одну из 2х сторон. Осталось посчитать стоимость ориентации цикла в обе стороны и выбрать меньшую.
Есть небольшой трюк - можно посчитать стоимость только для одной ориентации. Стоимость другой - это суммарная стоимость всех ребер минус стоимость первой
Задача B: Чемпионы Формулы-1
Тоже очень простая задача - надо сделать буквально то, что просят. А именно - завести ассоциативный массив, в котором каждому пилоту соответствуют количество очков и массив из 50 элементов - количество раз, которое он занял соответствующее место. Далее осталось найти максимум по 2м критериям.
Задача C: Последовательность точек
Заметим, что последовательное отражение от 2 точек - это параллельный сдвиг на удвоенный вектор между этими 2мя точками. Таким образом M2n = M0, так как последовательность отражений превратится в последовательность сдвигов на удвоенные вектора A0A2, A2A4, ..., An - 2A0 - а они в сумме дают нулевой вектор. Таким образом можно j заменить на j' = jmod2N. Теперь можно просто симулировать j' отражений. Пусть нам надо найти M' (x', y') - отражение точки M(x, y) относительно точки A(x0, y0). Тогда x' = 2x0 - x, y' = 2y0 - y.
Задача D: Сломанный робот
Если робот находится в последнем ряду, то ответ, очевидно, 0. Пусть теперь мы для каждой клетки следующего ряда знаем матожидание числа шагов из этой клетки до последнего ряда - zi. Пусть xi - это матожидание числа шагов для i-й клетки в текущем ряду. Получаем систему уравнений:
x1 = 1 + x1 / 3 + x2 / 3 + z1 / 3
xi = 1 + xi / 4 + xi - 1 / 4 + xi + 1 / 4 + zi / 4 для i от 2 до M - 1
xM = 1 + xM / 3 + xM - 1 / 3 + zM / 3
Это трехдиагональная система, она решается методом прогонки за линейное время.
Осталось применить это решение N - i раз и взять j-й элемент ответа.
Отдельным представляется случай M = 1 - в этом случае уравнение немного меняется, но на самом деле легко заметить, что ответ 2(N - i), так как матожидание спуска на один ряд - 2.
Задача E: Берляндский коллайдер
Исключим для начала ответ -1 - ответ -1 получается только если у нас сначала идет какое-то число частиц (возможно, нулевое), движущихся влево, а затем какое-то число частиц (возможно, нулевое), движущихся вправо.
Теперь будем искать ответ бинарным поиском. Максимальный возможной ответ - 1e9 (частица с координатой -1е9 и скоростью 1 и частица с координатой 1е9 и скоростью -1). Рассмотрим чсило t. Как нам определить, ответ больше t или меньше? Пройдемся по частицам слева направо, при этом будем запоминать самую правую точку, до которой долетела частица, которая летит направо. Тогда если мы встретим частицу, которая летит налево и которая залетела левее этой точки, ты мы нашли пару частиц, которые столкнулись в момент времени меньше t. Если мы ни одной такой частицы не нашли - значит, первое столкновение произошло в момент времени больше t. Теперь надо аккуратно следить за правильным условием окончания бинарного поиска (например, while (r - l > 1e-11 * r)) и вывести потом r с 11, например, знаками после запятой
Let's define function F(a,b) which returns X where X = 1 + X * a + (1-a) * b and e[i][j] is the expected number of steps that takes for robot to reach last row when robot is initially on cell(i,j).
Here is the whole code:
for (int i=1;i<=m;i++)
e[n][i]=0;
for (int i=n-1;i>=1;i--){
if (m == 1){
e[i][1]=f(1.0/2,e[i+1][1]);
}else{
for (int count=1;count<=30;count++){
e[i][1]=f(1.0/3,(e[i+1][1]+e[i][2])/2);
e[i][m]=f(1.0/3,(e[i+1][m]+e[i][m-1])/2);
for (int j=2;j<m;j++)
e[i][j]=f(1.0/4,(e[i][j+1]+e[i][j-1]+e[i+1][j])/3);
}
}
}
Let the origin Array to be A[1..m]..represents the previous Floor..then first put all elements in B to be zero.
then create Array C where C[i]=（B[i]+B[i-1]+B[i+1]+A[i])/4+1..then Let B=C and do it for many times can also calculate a new A...
" for (int count=1;count<=30;count++) " why do you use count here?
"Пройдемся по частицам слева направо, при этом будем запоминать самую правую точку, до которой долетела частица, которая летит направо. Тогда если мы встретим частицу, которая летит налево и которая залетела левее этой точки, ты мы нашли пару частиц, которые столкнулись в момент времени меньше t"
На мой взгляд более корректно запоминать самую правую для летящих направо и самую левую для летящих налево, а потом уже делать вывод об увеличении или уменьшении t.
would you please tell why? -_-!!!
my binary search code:
int judge(double t){
double now = -1500000000;
for(int i=1;i<=n;i++){
if(node[i].type==1){
double test = node[i].x + node[i].v * t;
if(test > now) now = test;
}
else{
double test = node[i].x - node[i].v*t;
if(test<=now+epx) return 1;
}
}
return 0;
}
// in main function
double left = 1e-10, right = (node[n].x - node[1].x)/2.0 + 1;
while(aabs(left-right)>epx){
double mid = (left + right)/2;
if(judge(mid)==1) right = mid;
else left = mid;
}
Разобъем множество точек на чередующие куски подряд идущих точек из летящих только вправо или только влево. Очевидно, что первое столкновение произойдет между соседними кусками (-> X <-).
Заметим еще тот факт, что в каждый момент до столкновения в каждом "куске" ровно одна частица имеет шанс поучаствовать в первом столкновении - самая дальняя по ходу движения. Проходя по куску против хода движения, при помощи стека за один проход найдем все частицы, которые когда-либо окажутся первыми, вместе с временными отрезками, когда они ими будут.
Теперь посмотрим на два соседних "встречных" куска. Имеет смысл рассматривать только те точки из этих кусков, которые в некоторый момент окажутся первыми. После рассмотрения любой такой пары легко определить хронологически следующюю: надо всего лишь посмотреть, в каком из кусков раньше поменяется первая точка. Каждая пара кусков даст нам не более (количество точек в этих кусках) рассмотренных пар.
Если же встречных пар нет, ответ -1.
Можно поподробнее, как?
Пусть наш стек - это ответ для нескольких первых частиц (против хода движения). Скорости частиц в нем убывают от вершины. Новую частицу стоит рассматривать, только если ее скорость больше всех рассмотренных, поскольку иначе есть частица, которая дальше и (нестрого) быстрее ее. Также, новая быстрая частица всегда попадет в стек, т.к. через достаточно большое время она станет первой.
Теперь надо понять, какие частицы выкинуть. Посмотрим на частицу в вершине стека. Если наша новая частица обгоняет ее раньше, чем та становится первой (т.е. обгоняет вторую), выбрасываем ее из стека. Это действие надо повторять, пока не окажется, что частица в вершине стека некоторое время все же пребывает первой. Остальные частицы в стеке, очевидно, рассматривать не надо.
Временные отрезки определить просто - это отрезок от того момента, когда частица обгоняет следующую в стеке частицу (либо 0 для конца), до момента обгона более быстрой предыдущей (либо бесконечность для последней).
в принципе, ничего страшного, за 15 минут вбил и сдал, только вот сомневался влезет ли в long long. ибо с четным количеством точек легко получить координаты порядка 1021. а оно взяло да и зашло...))
Congrats egor !!!
I'v just found new solution for problem E and my code AC 2676662. We could use binary search on distance between two successive colliders that their sign of speed changes from positive to negative.Use this we could figure out the places that colliders could make a Big Bang. By dividing the speed of each collider into the distance from places that we calculate before , we could found the answer. another thing that this problem has very bad exact time limit so we must use printf. and sorry for my bad english :D