Wataru

Попробуйте читать через scanf.

Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.

У вас, фактически, задано дерево. Каждая вершина - это элемент на каком-то уровне в массиве. Его свойство SUB - это дети дерева.

Вам надо получить список всех вершин, т.е. обойти дерево. Тут есть 2 стандартных решения - обход в ширину и обход в глубину. В глубину - это рекурсивная функция. В ширину, это будет итеративное решение, но нужна очередь.

Рекурсивное решение пишется легче всего, как мне кажется.

Во-первых, перенесите центр системы координат в центр элипса - вычтите его из всех координат точек касания. В самом конце надо будет сделать обратный переход и подставить x=x-x0, y=y-y0 в уравнение.

При выборе правильной системы координат, эллипс становится окружностью, ведь его уравнение x^2/a^2+y^2/b^2=1. Все остальное - это от переноса центра координат и поворота эллипса.

Давайте переобразуем нашу систему координат, повернув на какой-то угол и сжав вдоль оси X, чтобы получить круг.

с- cos(угол), s=sin(угол) k- коэффициент сжатия.

Тогда новая система координат - {kc,ks}, {s,-c}. Преобразуем в эту систему координат тички касания и вектора касательных. Они так и останутся касающимися нашего эллипса, ведь преобразования поворота и сжатия оставит прямые прямыми, а эллипс - эллипсом (или кругом).

Если x1,y1 - точка касания, а {xv, yv} - вектор касательной, то:

x1' = x1*kc+y1*ks

y1' = x1*s-y1*c

xv' = xv*kc+yv*ks

yv' = xv*s-yv*c

Это просто формулы перобразования между системами координат. Аналогично можно сделать для x2', y2', xw,' yw'.

Теперь составим уравнения. Мы же хотим найти преобразование, в котором наш эллипс будет окружностью. Во-первых, расстояния до точек касания должны быть одинаковыми. Во-вторых, касательные вектора должны быть перпендикулярны векторам из начала координат к точкам касания.

Если аккуратно расписать x1'*x1'+y1'*y1'-x2'*x2'-y2'*y2' = 0, и заменить c^2=1-s^2, то будет:

(y1*y1-y2*y2-x1*x1+x2*x2)*kkss + (2*x1*y1-2*x2*y2)kkcs + (x1*x1-x2*x2-y1*y1+y2*y2)ss +(2*x2*y2-2*x1*y1)*cs +(x1*x1-x2*x2)*kk+(y1*y1-y2*y2)=0

Советую не верить мне тут с коэффициентами, а пепроверить их самостоятельно.

Аналогичные уравнения для касательных x1'*xv'+y1'*yv' = 0:
(y1*yv-x1*xv)*kkss + (x1*yv+y1*xv)kkcs + (x1*xv-y1*yv)ss +(-x1*yv-y1*xv)*cs +(x1*xv)*kk-y1*yv=0

Важно заметить, что у нас тут 3 уравнения вида:

A*kkss+B*kkcs-Ass-Bcs+Ckk+D=0, где константые коэффициенты A,B,C,D (разные в трех уравнениях) и 3 переменные k,s,c. Еще есть дополнительное условие s*s+c*c=1, это же синусы/косинусы угла, и k!=0. k может быть и отрицательным, это означало бы отражение и сжатие системы координат. Под наши цели подходит.

Обратите внимание, 3-е и 4-ое слагаемые идут с теми же коээфициентами, что и 1-е и 2-е, но с обратными знаками. Можно подобрать такие коээфициенты для первых двух уравнений, что если их прибавить к тертьему уравнению, то коэффициенты перед kkss,kkcs,ss,cs - все станут равны нулю. Это надо решить систему из двух линейных уравнений.
Пусть коээфициенты в уравнениях A1,A2,A3,B1,B2,B3,C1 и т.д. (напоминаю, это константы, вычеслимые через заданные координаты точек и векторов касания). Введем 2 переменные x, y - коээфециенты, с какими прибавлять первые 2 уравнения к тертьему. Условия: A1*x+A2*y+A3=0, B1*x+B2*y+B3=0. Решив эту систему уравнений, найдя коээфициенты и прибавив первые 2 уравнения к тертьему, вы получите уравнение вида

C4*k*k+D4=0

Элементарно решив его, вы найдете k. Подставив его в 2 предыдущих уравнения вы получите 2 уравнения вида:

A4*ss+B4*cs + D4 = 0

Это тригонометрическое уравнение можно решить, дописав множитель cc+ss к D4, получив уравнение вида:

(A4+D4)*ss+B5*cs+D4*cc = 0.

Теперь осталось поделить обе части на с^2 и решить квадратное уровнение для tan(). Еще, правда, надо рассмотреть подходит ли c=0,s=1 (s=-1 рассматривать не надо, Ведь без разницы, в какую сторону вращать на 90 градусов - все равно ось сжатия будет одна и та же).

Теперь зная тангенс найдите косинус и синус (школьные тригонометрические формулы, вроде c=sqrt(1/(1+t^2)).

Все, мы знаем k,c,s. Подставив их в формулы для x1',y1' мы узнаем радиус окрудности (расстояние до нуля). Пусть радиус будет r.

Теперь уравнение эллипса x'^2+y'^2 = r^2.

Подставляем преобразование:

x'=x*k*s+y*k*c, y' = x*s-y*c. Потом не забываем сделать замену x<-x-x0, y<-y-y0, чтобы верунть центр эллипса в заданное место.

Все эти замены надо аккуратно подставить и раскрыть скобки в уравнении x'^2+y'^2 = r^2 и получить ваши коээфициенты в уравнении Ax2+ Bxy + Cy2 + Dx + Ey = F. Потом поделите обе части на F.

Это решение невозможно расписать аналитически на бумаге до конца, потому что слишком много подставлений и этапов - будут просто монсрячные формулы. Но, в алгоритме, делая по шагам, вводя переменные и коэффициенты это не сложно сделать.

Edit:

Тут есть потенциальная проблема - надо решить систему линейных уравнений и 2 квадратных уравнения в процессе решения. Я не могу доказать, но верю всей душой, что, если эллипс существует, то все эти уравнения будут решатся в вещественных числах, без делений на 0 и квадратных корней из отрицательных чисел.

Из обсуждения под вопросом стало понятно, что нужно, чтобы окружности в узоре касались, т.е. образовывали связную структуру. Для этого надо, во первых, чтобы исходные окружности касались и, во вторых, чтобы преобразование оставляло точки касания на месте. Можно подобрать множество таких преобразований, но подойдет например преобразование инверсии, которое оставляет на месте сами окружности целиком.

Делайте рекурсивную функцию, которая решает вашу задачу. Если символ на входе 1 - просто его и возвращает. Если входных символов несколько - то откусывает последний символ и вызывается рекурсивно, потом к возвращенному массиву к каждому элементу дописывает последний символ и точку-последний символ (новый массив с удвоенным количеством элементов).

Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].

Получите 2 вектора вдоль этих прямых (если прямые заданы параметрически - вы их уже знаете, если Ax+By+C=0, то это {-B,A}). Теперь угол между двумя векторами a и b - ваш искомый угол. Тут надо вспомнить, что векторное произведение - это |a|*|b|*sin x, а скалярное - |a|*|b|*cos x. Теперь вы знаете sin и cos искомого угла (поделив скалярное/векторное произведение на длины векторов). Можно скормить эти значения atan или еще какой-то обратной тригонометрической функции. Но на практике сам угол редко нужен, нужны в вычеслениях его sin и cos, а их вы уже знаете.

Большинство решений, уже предложенных тут, работают за квадрат и уже для n=10000 amount=5000 будут работать заметно долго. Конечно, вряд ли такое большое количество данных будет на клиенте, но даже при n=100, если функция выполняется часто, зачем ее делать в ~50 раз медленнее?

Решение, предложенное Павел - самое лучшее. Работает быстро и, как и многие алгоритмически правильные решения, оно гораздо короче и читабельнее остальных решений.

Если хотите без splice(), то надо завести новый массив и потом скопировать в него элементы n-amount..n-1 в начало одним циклом, потом вторым циклом скопировать дальше элементы 0..n-amount-1.

Зафиксированный вами интерфейс предполагает использование нового массива для результатов каждый раз. Но можно было бы сделать без использования много дополнительной памяти, тусуя сам массив на месте, если допустить изменение интерфейса.

Правда, splice уже нельзя было бы использовать. Еще надо было бы знать теорию перестановок немного. Короче, вот решение, которое работает за линию и перемешивает массив на месте:

function gcd(a,b) {
 if (a>b) return gcd(b,a);
 return a == 0? b : gcd(b%a, a);
}

function next(i, k) {
  return i >= k ? i-k : i+n-k
}

function moveToStartInPlace(arr, k) {
  n = arr.length;
  num_cycles = gcd(k,n)
  for (i=0; i < num_cycles; ++i) {
   saved_value = arr[i];
   j = i;
   nxt = next(j, k);
   while (nxt != i) { 
     arr[j] = arr[nxt];
     j = nxt;
     nxt = next(j, k);
   }
   arr[j] = saved_value;
  }
}

Возможно, это не лучшая реализация - я не специалист по JS. Суть этого решения в том, что мы берем какой-то элемент и ставим на его место нужный элемент после перестановки. На освободившееся место ставим следующий элемент и так далее, пока не вернемся к начальной позиции (а мы всегда вернемся, потому что перестановки только так и работают).

Функция next() возвращает, какой элемент должен встать на место i-ого в итоговом массиве.
Если немного подумать, то станет понятно, что в перестановке ровно gcd(n,k) циклов, потому что в ней все прыжки делаются на +(n-k) или -k. Т,е. фактически делаются только прыжки -k(mod n). А это уже известный факт: если прыгать по массиву на +k, оборачиваясь из конца в начало, то мы вернемся в ту же точку, с которой начали и всего таких циклов будет gcd(n,k).

Проверка на малых числах не всегда работает. там фибоначи, квадрат и черт знает что похожи.

Если у вас там что-то вроде for "i=1...n do for j = i..n do" или каике-то еще 2 вложенных цикла, где внутренняя переменная бежит от или до внешней переменной, то точное количество итераций будет n(n+1)/2, что есть O(N^2).

Ваше последнее суждение - верно.

Если у вас задача - что в выбраных наугад картах есть хотя бы один туз и хотя бы одна черва, то надо найти Count(>0 червей И >0 тузов). Можно это инвертировать, считая все плохие варианты, вычев их из всех вариантов:

Count(>0 червей И >0 тузов) = Count() - Count(0 червей ИЛИ 0 тузов)

Дальше, COUNT(A или B) можно разложить на Count(A) + Count(B) - count(A И B).

Финальная формула для ответа:

Count() - Count(0 червей) - Count(0 тузов) + Count(0 червей И 0 тузов)

Фактически, это форомула включения-исключения. Но в итоговой формеле все просто счиатать:

Count() = C(5,36) - все варинты: сочетания по 5 из 36.

Count(0 тузов) = С(5, 32) - нельзя брать тузы

Count(0 червей) = С(5, 27) - нельзя брать 9 червей

Count(0 червей И 0 тузов) = С(5, 24) - нельзя брать 9 червей и 3 оставшихся туза.

Подсчитайте через фаториалы и сложите с правильными знаками.

Если же задача - ровно один туз и ровно одна черва, то тут 2 варианта. Или туз-черва взят, или это две разные карты.

В первом случае оставшиеся 4 карты - любые из 24 карт не-тузов-не-черв, т.е. эта часть - C(4,24). Во втором случае, вы берете какой-то из 3 тузов, какой-то из 8 черв и оставльные 3 карты из не-тузов-не-червей, т.е. ответ 3*8*C(3,24). Обе части просуммируйте.

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
У вас неправильное решение задачи.

Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

Дальше надо посмотреть на паттерн на маленьких числах и составить решение, потому что вся эта динамика у вас по времени не зайдет для данных ограничений.

Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.

У вас неправильно в коде - надо считать count() не на всем массиве, а только между low и high.

Тогда сложность всего алгоритма будет O(n log n). То, что у вас сейчас сделано будет иметь сложность O(n^2).

Избавиться от подсчета в данном решении никак нельзя.

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.

Детали зависят от конкретной реализации, но обычно все основано на leaky bucket.

В целом, роутер считает, сколько байт он пропустил, и если видит, что байт слишком много в еденицу времени, лишние пакеты просто дропаются (отбрасываются без пересылки их дальше). А дальше уже источник трафика как-то подстраивается. Если трафик TCP - то отправитель замечая потери будет снижать скорость отправления пока потери не прекратятся. Если же используется UDP, и приложение не надстроило над ним каких-то rate-control механизмов, то так и будет посылать лишние пакеты, которые будут уничтожатся роутером. До него трафик будет без ограничения скорости, а дальше пойдет уже ограниченный.

Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

R-дерево (по той же ссылке) дает гарантию по времени выполнения и знимает сравнительно мало памяти, но его долго пересчитывать, если точки двигаются или добавляются/удаляются.

Просто для справки, если вам важно гарантировать время выполнения (не сильно больше чем нужно для обхода только точек в прямоугольнике) и точки могут менятся, то тут подходит моя любимая структура данных - дерево отрезков деревьев поиска.

Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.

Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?
Если вам только тесты надо делать, то можно сначала создать весь мир, а потом поспрашивать его о статусах домов. При чем сами вычисления (обход графа) можно сделать только один раз, получить данные по всем домам и потом их проверить.

В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

Если же вам обязательно надо узнавать статус домов после каждого изменения графа, то можно делать все тоже самое, но это будет медленно, ведь после каждого изменения вы будете обходить весь граф.

Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

При запросе на статус дома возьмите счетчик активных станций для его множества и проверьте, что он положителен. При выключении/включении электростанции измените счетчик соответствующего множества на +1 или на -1.

Это решение будет фактически работать за O(1) при каждом запросе и добавлении ребра (если использовать эвристику сжатия путей).
Наивное же решение с полным обходом графа каждый раз было бы O(1) при добавлении ребра и O(n) при запросе.