Задача 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...
"Пройдемся по частицам слева направо, при этом будем запоминать самую правую точку, до которой долетела частица, которая летит направо. Тогда если мы встретим частицу, которая летит налево и которая залетела левее этой точки, ты мы нашли пару частиц, которые столкнулись в момент времени меньше 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 !!!