Вообще, там нужно пользоваться тем, что ни одна дробь не превосходит 1, но строго больше нуля. Считая в лоб мы можем натолкнуться на последовательность с 100000 простыми числами, где ни сокращение дробей, ни длинная арифметика уже не помогут.

В I есть решение без потока динамикой за O(nm)

Во втором дивизионе по I зашло такое: найдём кратчайший путь до одной пары, удалим все рёбра этого пути, найдём кратчайший до другой пары. Если не нашлось, поменяем пары вершин местами и повторим.

Вроде в первом дивизионе условие не отличается.

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

По H: Запускаем следующий рекурсивный DFS из всех смежных с вершин, смежных с нулевой: для каждой вершины считаем количество путей в нулевую вершину, кроме того, по которому мы пришли. Если количество путей больше единицы, то значит, что это вершину нужно удалить, при этом вернув 0, иначе возвращаем количество путей. Если по окончанию DFS возвращает нам 1, то нужно удалить ту вершину, из которой мы запустили DFS.

D: Воспользуемся тем, что p(A) это сумма 2^a_i. Переберём i. В ответ войдут всевозможные произведения функций с множителем 2ⁱ по множествам, в хотя бы одном из которых есть i-тый элемент. Т.е. к ответу прибавляем

H: Отметим все вершины, смежные с 0. Теперь удалим вершину номер 0. Тогда у нас останется дерево с отмеченными вершинами. Цикл появится, если будет путь между отмеченными вершинами. А это можно сделать одним обходом в глубину жадно.

В D можно очень просто сосчитать функцию . Для этого можно просто для каждого множества сосчитать сумму значений f от всех его подмножеств и сумму значений g от всех его подмножеств и перемножить. Дальше можно методом включений-исключений перейти от q к h. Вот код, чтобы понятней было: http://pastebin.com/f5LSaXZG

"Честное" решение D: Определим conv[F] как . Тогда обратный к conv оператор определяется так: .

Пусть . Рассмотрим . Значит H = conv^- 1[H'] = conv^- 1[conv[F] * conv[G]], где * — поточечное умножение.

Осталось научиться считать conv[H] (и conv^- 1[H]).

Определим , где первые k бит X — подмножество A, а остальные совпадают с A. conv₀[H] = H, conv_n[H] = conv[H].

Тогда conv_k[H](A) = conv_k - 1[H](A) если , иначе .

Аналогично, conv^- 1_k[H](A) = conv^- 1_k - 1[H](A) если , иначе .

Итого, получается решение со сложностью O(2ⁿ * n): http://pastebin.com/Y2Hw2saP.

/blog/entry/14317

Выдержка из правил

4.2.4 В спонсорский зачёт каждого Гран-При входят команды со статусом ACM, участвовавшие в данном Гран-При в соответствии с 4.2.1. и выполнившие при этом предложенные организаторами спонсорского зачёта требования. Гран-При в спонсорском зачёте считается состоявшимся, если хотя бы одна участвующая в спонсорском зачёте команда успешно решила хотя бы одну задачу.

F: у выпуклого пятиугольника всего пять триангуляций, каждая выглядит как "одна вершина, из которой торчат две диагонали". Переберем их все, для каждой проверим, что это действительно триангуляция. Я проверял так: середина каждой диагонали лежит внутри пятиугольника, диагонали не пересекают стороны и друг друга.

В J перебор для первых 2000 значений показал, что один из прямоугольников всегда имеет обе стороны не более 10. А второй, очевидно, должен иметь стороны как можно более близкие к квадрату. Ну и написать можно следующий перебор. Переберем обе стороны первого прямоугольника от 1 до 100. Одну из сторон второго прямоугольника от корня оставшейся части до этого же корня минус 10000. Оставшуюся сторону можно выразить через предыдущие три, если таковая вообще существует. Выбираем наилучший ответ и выводим.

Будем решать с конца — удалять по одному треугольнику.

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

Второе условие проверять просто: будем поддерживать количество сторон каждого треугольника, связанных с удаленными треугольниками или внешней гранью. Если оно >=1, то треугольник можно удалять и второе условие не нарушится.

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

Это всё придумали halyavin и Michael, я просто примазываюсь :)

Выше написано.

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

Play randomly until each connected component becomes small (<= 10 possible moves). After that, compute grundy function of each component in O(2^n), and xor values for all components. With high probability, result will be non-zero.

One of the solutions involves only trivial observations, but a fair bit of coding.

When we have a game position, it can be partitioned into independent regions where moves can be made. Two possible moves are immediately dependent when they share at least one cell.

We will recognize three classes of regions based on two boolean outcomes.

1. Is it possible to invalidate all possible moves in the region by a single move?

2. Is it possible to make a move such that there remains at least one possible move from the region?

An example of (1) but not (2) is a square of 2 × 2 or 3 × 3 cells. Such a region (a Type I region) requires exactly one move to disappear.

An example of both (1) and (2) is a rectangle of 2 × 4 or 3 × 4 cells. In such a region (a Type II region), we have a choice: it requires either one or two moves to disappear.

An example of (2) but not (1) is any large region. Such a region (a Type III region) requires at least two moves to disappear.

Our first goal will be to have only Type I and Type II regions left on the board. We can try to achieve a perfect grid of Type II regions (4 × 2 rectangles) by trying to place every square of the pattern shown on the left picture. Of course, Felix will mess things up, and the resulting board will look more like the right picture (result of a 16 × 20 game up to this point).

There are 8 Type I regions, 8 Type II regions and 2 Type III regions on the right picture.

In the second part of the game, we eliminate all Type III regions by detecting them and making random moves in these regions.

In the endgame, we have only X Type I regions and Y Type II regions.

• If X and Y are even, the player who makes a move loses if both play optimal: the winning strategy for the other player is to keep them both even after their turn. If we find Sophia in such position, we can make a random move and hope Felix does not follow the winning strategy.

• If X is even and Y is odd, we make by eliminating one Type II region, so that both are even after our turn.

• If X is odd and Y is even, we remove one Type I region just the same.

• Finally, if X and Y are both odd, we move in a Type II region such that it leaves a new Type I region, effectively making the new values of X and Y even: X increases by one and Y decreases by one.

The more Type II regions we had at the beginning, the more are our chances to eventually avoid the situation when X and Y are even and Sophia has to make a move. If we avoid that at least once before the game is over, we follow the above simple strategy to win.

The above strategy is a simple case of calculating and using Grundy numbers for regions, as in winger's solution: they are 1 for Type I regions and 2 for Type II regions. Still, this solution requires only knowledge of elementary game theory and invention of simple symmetric strategies.

When checked several times against the judges' test cases with different random seeds, it won at least 293 out of 300 games.

Один предмет можно брать несколько раз

Перед тем, как показывается очередная карта, все предметы ставятся на стол.

Данные по новым секторам будут высланы завтра.