Условия: http://contests.snarknews.info/files/snws11/probs/day5.pdf
Результаты: http://contests.snarknews.info/index.cgi?data=snws11/standing5&menu=index&head=index&mod=snws11&class=snws11
Задача А.
Сначала заменим все числа на A%mod, так как понятно нас интересует только остаток, затем добавляем сначала все числа с одним остатком, затем с другим итд. Допустим, что сейчас добавляются числа с отстатком m, а до этого уже были добавлены какие-то числа с другими остатками. Поддерживаем динамику d от двух параметров, где d[v][q] = количество последовательностей из уже добавленных чисел таких, что есть ровно v пар чисел с одинаковым остатком, НЕ равным m, стоящих рядом, и q пар чисел с остатком, равным m, стоящих рядом.
Кроме того, двигаясь вправо поддерживаем: n - сколько уже вообще добавлено чисел, и r - сколько уже вообще добавлено чисел с текущим остатком. Теперь, закрепим v и q. У нас есть три опции:
1. Поставить число между двумя одинаковыми числами, не имеющими остаток m. Таких вариантов, очевидно, v, и такое действие уменьшит v
nd[v-1][q] += d[v][q] * v
2. Поставить число между или рядом с числом с остатком m. Это увеличит q. Таких вариантов, если подумать, 2*r-q:
nd[v][q+1] += d[v][q] * (r*2-q)
Наконец, поставить число в любую другую позицию. Это не изменит ни q ни v. Это все оставшиеся варианты, то есть n+1 - v - (r*2-q)
nd[v][q] += d[v][q] * ( n + 1 - v - (r*2-q) ).
Потом, когда остаток от деления меняется, добавляем числа с предыдущим остатком к старым:
nd[v+q][0] += d[v][q];
В конце ответ будет в d[0][0] - потому что не должно быть никаких чисел с равным остатком рядом.
Задача B.
Я занумеровал вершины в порядке выхода из DFS, и вывел их по убыванию этой величины.
Задача C.
Единственное ограничение, данное нам -- это то, что кратность ребер не превышает четырех. В частном слуачае, когда вес всех ребер равен единице, это будет задача на матричную теорему Кирхгофа, которая решается за N^3.
Я упускаю что-то очень важное :о)
Задача F.
Очевидно, сами числа не важны, важна только их длина. Нам надо понять, сколько битов понадобится, чтобы представить число с записью 10^K в системе счисления B. Это, если я правильно помню, равно floor( K*log(B)/log(2)+1 ).
Она и не разобрана :о)
Потому что я по-моему решение не той задачи написал.
Сейчас посмотрю в системе как я решал на самом деле...
Нет, все правильно оказалось.
В предыдущей правке мои неверные мысли и неверный код который прошел все тесты :О)
Необходимые условия для того чтобы A можно было поставить выше B в ответе:
1) несредственная связь типа A>B
2) или существует Z такой, что A>Z>B
Если мы дошли от игрока A до игрока B в DFS, то это значит только то, что существует цепочка A>X_1>X_2>...>X_n>B, при этом необязательно выполнение условий 1) или 2).
Контрпример yaro остается в силе.
Вообще такие задачи (пересечь многоугольник и окружность) решаются примерно так: находишь все точки пересечения окружности и многоугольинка, добавляешь к этому множеству те углы многоугольника, которые лежат внутри окружности, сортируешь это все по полярному углу относительно центра окружности, затем площадь нужной тебе фигуры будет суммой площадей секторов и треугольников.
Я не сдал эту задачу, потому что не смог себе ответить на два вопроса:
1. как понять, какие из треугольников брать с плюсом, а какие с минусом.
2. как понять (по двум углам) какой из двух секторов взять.
Когда-то давно я эту задачу так сдавал, сейчас не могу вспомнить как решал обе описанные проблемы. Возможно, надо сортировать не относительно центра окружности, а относительно центра масс всех выбранных точек. Тогда, видимо, будет немного сложнее считать площадь фигур, у которых одна из сторон - дуга (они больше не будут секторами), но зато многие ответы на вопросы саморазрешатся. Надо будет попробовать на дорешке сдать так.