305A - Странное сложение

Простая задача на реализацию.

1. Если у нас есть в множестве числа 0 или 100, то обязательно возьмем их в подмножество.
2. Если у нас есть число, отличное от 0 и меньшее 10, возьмем его в подмножество.
3. Если у нас число, отличное от 0 и 100, которое делится на 10 без остатка, тоже возьмем его.
4. Если у нас есть число, отличное от чисел, описанных в пунктах 1 - 3 и в изначальном множестве нет чисел из пункта 2 и 3, то возьмем одно такое число.

Решение

305B - Цепные дроби

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

Решение

305C - Иван и степени двойки

Во-первых, выполним все возможные переносы по степеням. Более формально, если у нас пара чисел, a_i = a_j, i ≠ j, заменим ее на одно число a_i + 1. Теперь, когда все a_i различны, то ответ очевиден — max(a_i) — cnt(a_i) + 1, где max(a_i) — максимальное число в массиве, cnt(a_i) — количество чисел в массиве

Решение

305D - Оля и граф

Во-первых, удобно расположить все вершины на координатной прямой. Далее в графе обязательно нужны ребра из i -  > i + 1. Кроме этого, в граф можно добавлять ребра из i -  > i + k + 1 (ребра типа 2). Не трудно доказать, что других ребер добавлять нельзя. Сразу считаем ребра, и определим, ответ 0 или != 0 . Далее ответ 0 еще тогда, когда все ребра 2 типа не имееют общего пересечения, если рассматривать как отрезки на координатной прямой. Причем это верно почти всегда, кроме случаев когда k ≥ n - 1. В этих случаях, ответ всегда 1. Теперь ответ != 0. Из всех ребер которые у нас есть, оставим только ребра типа 2. Если ребер типа 2 нет, то прибавим к ответу 1, так как мы сейчас можем ничего не добавлять. Иначе переберем вершину i, из которой мы проведем ребро 2 типа и аккуратно прибавим к ответу величину 2^cnt, cnt — это количество вершин на промежутке от [i, min(i + k, n — k — 1)] из которых не исходят ребра. Причем важно, чтобы все имеющиеся ребра были на этом промежутке. Таким образом, это решение за O(n + m). Отмечу, что у этой задачи есть решение за O(m + log(n)). Однако, заходит и O(n + m).

Решение O(n + m) Решение O(m + log(n))

305E - Игра со строкой

Чтобы решить эту задачу, необходимы некоторые знания по теории игр. Рассмотрим некоторую подстроку строки s s[i... j], такую, что все символы с i по j являются центрами палиндромов, а символы i - 1, j + 1 уже нет. Утверждается, что такую подстроку можно рассмотреть отдельно. Каждую такую подстрочку нетрудно закодировать единственным числом: len — просто количество символов в ней. И так, будем считать grundy[len] — значение функции Гранди. Пусть мы решили удалить символ в позиции 0 ≤ i < len. Тогда нетрудно понять, что игра распадется на 2 независимых игры: У первой игры будет длина i - 1, а у второй len - i - 2, так как соседние к i символы перестанут быть центрами. Таким образом, получим решение за O(n²). Скажу, что еще есть решение за O(n), но опять таки, это уже не требовалось.

Решение