В этой задаче, нужно было просто посчитать номер лифта, который подходит для каждого участника, а потом прибавить время поездки на этом лифте к времени прибытия лифта. Рассмотрим отдельно три случая.
- s = f, ans = t.
- s < f, нужно найти минимальное неотрицательное k такое, что t ≤ (s - 1) + 2(m - 1)k. ans = s - 1 + 2(m - 1)k + (f - s).
- s > f, аналогично, нужно найти минимальное неотрицательное k такое, что t ≤ 2(m - 1) - (s - 1) + 2(m - 1)k. ans = 2(m - 1) - (s - 1) + 2(m - 1)k + (s - f).
Находить k, можно любым разумным способом, например пользуясь формулами целочисленного деления.
Предположим, что первый сходил числом x ≤ a, тогда рассмотрим остаток rem = x· 109%mod. Очевидно, что если (mod - rem)%mod ≤ b, то второй игрок сможет выиграть. Таким образом нужно перебрать все актуальные значения x (нам не нужно перебирать больше чем mod значений) и посмотреть может ли выиграть второй игрок. Если есть ход проигрышный для второго, то выиграл первый, иначе второй. Т.к. мы перебираем все актуальные ходы первого, то вывести первый выигрышный ход первого (если такой, конечно, существует) не составляет никакого труда.
Утверждение. Если в графе турнире есть хотя бы один цикл, то есть и цикл длины три.
Проведем конструктивное доказательство. Найдем любой цикл в турнире каким-нибудь стандартным алгоритмом, например поиском в глубину. Если цикл не нашелся ответ -1, иначе выберем любые три последовательные вершины цикла v1 v2 v3 (Av1, v2 = Av2, v3 = 1). Так как данный граф является турниром, то либо есть ребро (v3, v1), либо есть ребро (v1, v3). В первом из этих двух случаев, мы сразу находим цикл длины три из вершин v1 v2 v3, во втором мы можем сократить длину уже найденного цикла на одну вершину (просто выкинув вершину v2).
Будем сокращать длину найденного цикла до тех пор пока не найдем цикл длины три.
Эту задачу можно было решать многими разными методами. Я расскажу решение, которое быстро пишется и быстро работает. Представим дерево рекурсии нашего преобразования F. Это дерево бинарное. Напишем на ребрах, ведущих в левое поддерево, нолик, а на ребрах, ведущих в правое, единичку. Теперь рассмотрим путь некоторого числа a (здесь и далее, будем считать, что мы вычли из всех чисел в массиве, над которым делаем преобразование, единичку). Путь начинается в корне и заканчивается в некотором листе, при этом цифры записанные на ребрах пути в точности произносят битовую запись числа a в порядке от младшего бита к старшему.
Будем решать задачу рекурсивной функцией по дереву, наподобие того как мы выполняем запрос к дереву отрезков. Вот прототип этой функции.
Функция возвращает ответ, для запроса (l, r, u, v), если рассматриваем только поддерево с позициями [tl, tr], при этом на пути от корня до этого поддерева написано число idx. Внутри функции, если l ≤ tl ≤ tr ≤ r, то ответ считается по формуле, иначе делим отрезок и суммируем результат от левой и правой части.
Как было написано выше, ответ для целого поддерева считается по формуле. Здесь нужно воспользоваться тем, что все числа в поддереве имеют вид k· 2depth + idx, где depth глубина поддерева. Нужно найти такие k, что u ≤ k· 2depth + idx ≤ v и потом просуммировать соответствующие им числа.
Асимптотика этого решения O(m· log(n)· (ответдляподдерева)). Ответ для поддерева можно считать за O(logn) можно за O(1).
В данной задаче предполагалось решение с использованием heavy light декомпозиции. Граф, заданный в условии, представляет собой цикл, на который подвешены деревья. Для каждого дерева заведем структуру (heavy light + дерево отрезков), которая будет уметь делать change на пути от вершины к какому нибудь её предку, а также поддерживать сумму единичек. Такую же структуру заведем для цикла.
Предположим, что цикла вообще нет, т.е. есть просто набор деревьев. Тогда общее количество ребер однозначно определяет количество компонент связности (Каждое включенное ребро делает на одну компоненту меньше).
Предположим, что есть только цикл. Тогда, по аналогии, общее количество включенных ребер однозначно определяет количество компонент связности.
Будем поддерживать количество включенных ребер в цикле и во всех поддеревьях. Тогда ответ на задачу это Compscicle + Compstrees - CntCicle, где Compscicle - количество компонент в цикле, Compstrees - количество компонент суммарно во всех деревьях, CntCicle - количество вершин в цикле.
Осталось только описать структуру для выполнения запросов и поддержания количества включенных ребер. Я ограничусь только ссылкой на соответствующий ресурс emaxx.ru.
Are you just translate your editorial (Russian version) into English Version by Google Translate?All right, I saw your tags anyway :)
#include <stdio.h>
#include <conio.h>
int main()
{
FILE* fin;
fin=fopen("f.in", "r");
int n, m;
fscanf(fin, "%d%d", &n, &m);
int mas1[100000];
int mas2[100000];
int mas3[100000];
for(int i=0; i<n; i++)
fscanf(fin, "%d%d%d", &mas1[i], &mas2[i], &mas3[i]);
for(int i=0; i<n; i++)
{
if(mas1[i]==mas2[i]){
printf("0\n");
continue;
}
int k = mas3[i]/(m-1);
int l = mas3[i]%(m-1);
int r;
if((mas1[i]<mas2[i] && l>mas1[i]-1 && k%2==0) ||
(mas1[i]>mas2[i] && l>m-mas1[i] && k%2==1))
k+=2;
if((mas1[i]>mas2[i] && k%2==0) ||
(mas1[i]<mas2[i] && k%2==1))
k++;
if(k%2==0) printf("%d\n", k*(m-1)+(mas2[i]-1));
else printf("%d\n", k*(m-1)+(m-mas2[i]));
}
//printf("%d %d", n, m);
fclose(fin);
getch();
return 0;
}
если с ожиданием.
rem = x· 109%mod
why 109 is used?? why its particularly 109?
Not that it matters here, but link-cut trees give you a running time of O(n log n) instead of the O(n log^2 n) solution described here. I also think they're rather elegant, if I do say so my self.
---Danny Sleator
I think, I should try to solve this problem in this way, the truth, when I first tried to read this article, I found it quite difficult, I hope I will be able to overpower her at this time.
With great respect,
This, combined with looking at the code, should make it a lot easier to understand.
---Danny
In the link operation, shouldn't we update the counts? Edit: it's done in
expose.I am probably misunderstanding something, but in link, shouldn't one of q's children be made q? If this isn't the case, then how does one construct a link/cut tree to represent a whole tree (using your implementation)?
A legend in this thread!
I think it boils down to proving this fact:
If there's an edge from i to j and out[j] >= out[i] then certainly there's a cycle i -> j -> k -> i for some node k (where out[u] is the number of outgoing edges from node u).
Another solution for problem C. let us consider the vertex with the biggest outcoming degree. if the degree is equal to n-1 we could ignore it ans solve the problem for remaining graph. otherwise we could name this vertex as a (( King )) of digraph. we know that every vertex could achieve from king with distance at most 2.so because of what we say before there is vertex like V that the edge between king and V is (( V -> king )). and we just need the path from king to V and we could find the middle vertex easily that we name it U. so the answer to the problem is (( king , U , V )).
Need help for Div 2 C. Getting the Wrong Answer for test case #34. According to my solution, I do dfs on vertexes and store their levels with respect to vertex 1(level 0). As soon as I add a vertex to stack I check whether the difference between its old level(only if that vertex had been visited before, else its level will be -1 by default) and new level (obtained by 1+current level of the top vertex of the stack)is equal to 3 or not. If it is, then I store current top vertex and the vertex whose difference in levels was 3. Now I only need to find the last vertex such that there is an edge from first to second and second to third and third to first.
My Solution
Can anyone explain why getting wrong answer or give a short test case?????
THANKS