Задача на технику программирования. Надо найти на каких позициях находятся кузнечик и насекомое. Если разность позиций не делится на k, то ответ — NO. В обратном случаи надо проверять позиции pos+k, pos+2k, ... , где pos — это минимальная из позиций кузнечика и насекомого. Если где-то есть препятствие, то ответ — NO, в обратном случаи — YES.
Во первых, надо заметить, что n1+n2 "избранные" должны быть люди с top (n1+n2) коэффициентами. Во вторых, если человек с интеллектом C будет в первом городе, то он будет добавить к суммарному коэффициенту IQ C/n1 баллов. Так что, если n1<n2, то top-n1 рейтингов надо "запихнуть" в маленький город, а из остальных top-n2 — в большой.
Давайте решать обратную задачу: сколько участников как минимум должен участвовать, если чемпион будет провести ровно n матчей. Тогда очевидно есть такая рекуррентая связь: f(n+1)=f(n)+f(n-1) (Сделаем сетку так, чтобы тот, кто победил в последнем матче до этого играл n матчей, а тот кто проиграл — сыграл (n-1) матчей). Значит, задача сводится к тому, чтобы найти индекс наибольшего числа Фибуначчи, не превосходящую число, данное в вводе.
Первый очевидный факт — для простых чисел ответ — 1 (Этот случай надо проифать в первую очередь). Если число не простое — то ответ по крайней мере — 2. А когда это возможно? Это возможно в двух случаях — когда число сумма двух простых или самый большой делитель числа — 2. Но если 2 делитель, то и n/2 тоже делитель отличные от n (n/2<=2 => n<=4 => n=4 — n не простое). По Гипотезе Гольбаха, которое проверено для чисел не превосходящих 10^9, каждое четное число является суммой двух простых чисел. А нечетное число может быть суммой двух простых чисел, если оно имеет вид 2+p, где p — простое. В обратное случаи, ответ равен — 3 (n=3+(n-3), (n-3) является суммой двух простых, так как оно четное).
Во-первых хочу сказать спасибо albert96 и GlebsHP за то, что помогли. Во-вторых, хочу извиниться за опоздание.
Задача решается методом динамического программирования. Пусть dp[v][i][j] будет количество покрасить поддерево вершины v так, чтобы ближайшая черная вершина была на глубине i, а ближайшая белая — на глубине j (еще и смотрим dp[v][-1][j] и dp[v][i][-1] — случаи где нету черных и белых вершин в диапазоне k в поддереве v соответственно). Чтобы объединить две поддеревья, надо перебирать все пары (i,j) в обеих поддеревьев. Пусть имеем пары (a,c) в первом поддереве и (b,d) — во втором. Если min(a,c)+max(b,d)<=k, то обновляем значение в нынешней вершине.
Сложность алгоритма O(n*k^4), что вполне достаточно для данной задачи (n — количество вершин, k^4 перебор всех пар (a,b); (c,d))
Эта задача состоит из трех идей. Идея 1: четность этого количества равна четности определителю матрицы, которая имеет 1 в позициях (ai,bi) и 0 — в других позициях (это — согласно определению). Идея 2: Если заменить одну единицу на нолик, но определитель будет меняться на величину, равную к алгебраического дополнения. То есть, если мы будем считать обратную матрицу то она будет отражать четности дополнений (B(m,n)=A'(n,m)/detA, мы знаем, что detA — нечетное). Идея 3: обратную матрицу можно найти за O(n^3), что медленно. Для этого мы будем перейти в алгебру по модулю 2, где мы умеем складывать числа с помощью XOR. Для этого мы в одном переменном храним не одно число а 32 — каждый бит один переменный. Тогда наша асимптотика будет O((n/32)^3), что вполне нормально.
Допустим у нас есть множество (a1,a2,...,am) (уже дополненный список в неубывающем порядке). Тогда — оно является валидным, если множество {2m-2, 2m-4, 2m-6, ..., 0} мажорирует
множество {a1,a2,...,am}. Необходимость: top-n (n<=m) участников между собой играют n(n-1)/2 партий, в котором суммарно собирают 2 балла. В матчах с остальными они суммарно могут набирать 2*n(m-n) баллов (всего игр верхней части против нижней части 2n(m-n)). То есть баллов у них вместе взято будет не больше чем 2*(n(n-1)/2+n(m-n))=2*((m-1)+(m-2)+...+(m-n)) (легко проверить). Достаточность, конструкция примера: Давайте решим как играл чемпион, а потом опустим рекурсию (математически применяем метод математической индукции). Если количество баллов у чемпиона четно (например 2*(m-n) то мы допускаем, что он проиграл у участников занявшие места 2,3,4,...,n и выиграл у остальных). Если у чемпиона количество баллов нечетно (2*(m-n)-1, для некоторого n), то тогда мы предполагаем то же самое, только предполагая, что он играл вничью с (n+1)-ым. Легко проверять, что мажорация сохранится, то есть мы и в конце будем (в случаи n=1) будем иметь множество которая мажорируется множеством {0}, то есть {0} и задача будет решена. То есть алгоритм такой: Сначала доводим наше множество из n элементов к множеству из m элементов. Если это невозможно, то ответ — NO. В обратном случаи — ответ YES и надо конструктировать пример как описано. Асимптотика: O(m^2logm) (m раз мы вызываем рекурсию, каждый раз сортируем (это нам нужна потому что мы можем менять очередь из-за того, что результат игрока первого места может влиять на последовательность),и проходим на него линейно).
