---
# System prepended metadata

title: Untitled

---

## FL5. Карточная игра

:::spoiler Подсказка 1
:::info
Воспользуйтесь бинарным поиском по ответу. Теперь карту характеризуют только $c_i$ и $p_i$.
:::

:::spoiler Подсказка 2
:::info
Не теряя общности, предположим, что есть максимум одна карта с $c_i = 1$ (если их несколько, то мы можем использовать только одну из них). Тогда простое число в сумме могут дать только два числа разной чётности.
:::

:::spoiler Подсказка 3
:::info
Построим двудольный граф, где в левой доле будут все карты с чётным $c_i$, а в правой - с нечётным. Соеденим ребром все пары вершин, у которых $c_i$ в сумме дают простое число.

Тогда мы свели задачу к нахождению в этом графе независимого множества с максимальным суммарным весом вершин (независимое множество - множество вершин такое, что любые две вершины в нём не соединены ребром).
:::

:::spoiler Решение
:::info
Создадим в исходном двудольном графе фиктивные вершины $s$ и $t$. Проведём ребра из $s$ в каждую вершину $i$ левой доли с пропускной способностью $p_i$. Аналогично проведём ребра из всех вершин правой доли в $t$. Тогда искомый максимальный вес независимого множества - это сумма всех $p_i$ минус минимальный $s - t$ разрез в получившемся графе.
:::

## FL6. Коллекционирование монет

:::spoiler Подсказка
:::info
Постройте граф потока таким образом, чтобы каждый путь от истока до стока соответствовал серии обменов монетами, у которых имеются дубликаты, начиная с Васи, отдающего один из своих дубликатов, и заканчивая тем, что он получает новую монету.
:::

:::spoiler Решение
:::info
Для каждого человека кроме Васи создадим в графе потока двудольный подграф, описывающий его монеты. Каждой вершине будет соответствовать тип монет. В левой доле будут типы монет, которых нет у этого человека, а в правой - типы монет, которых у него две и более. Пропускная способность у всех вершин левой доли будет 1, у вершин правой доли - количество монет соответствующего типа минус 1. Попарно соединим вершины левой доли с вершинами правой доли рёбрами бесконечной пропускной способности.

Пример для $[1, 1, 1, 2, 2, 5]$ и $m = 5$:

<img src="https://i.imgur.com/ynT5hwM.png" width="50%" height="50%">

Поток величины $1$, который течёт из левой доли в правую, означает обмен монеты в левой доле на монету в правой доле.

Построим аналогично двудольный подграф для Васи, но не будем соединять рёбрами вершины левой и правой доли. Создадим вершины $s$ и $t$. Проведём рёбра бесконечной пропускной способности из $s$ во все вершины правой доли и из всех вершин левой доли в $t$.

Во всём графе для каждого типа монет $x$ соединим попарно вершины правых долей, отвечающих за тип $x$ с вершинами левых долей, отвечающих за него. Ответ - максимальный поток из $s$ в $t$.
:::

## MC2. Мороженое
:::spoiler Решение
:::info
Создадим вершину $t$ и проведём рёбра из $a$ и $b$ в $t$. Назначим всем рёбрам пропускную способность $1$ и стоимость единицы потока, равную длине (у рёбер в $t$ длина $0$). Также назначим всем вершинам кроме $c$ и $t$ пропускную способность $1$. Найдём максимальный поток минимальной стоимости из $c$ в $t$. Если ответ существует, то из $a$ в $b$ через $c$ можно дойти по насыщенным рёбрам, причём этот путь будет минимальным по длине.
:::

## MT3. Домино
:::spoiler Решение
:::info
Построим граф, в котором каждая вершина будет соответствовать клетке поля, и проведём рёбра между всеми парами соседних свободных клеток. Тогда получившийся граф будет двудольным, причём в одной доле будут все клетки с чётным номером диагонали, а в другом - с нечётным (шахматный порядок). Найдём в этом графе максимальное паросочетание.
:::

## MT4. Модели компьютеров

:::spoiler Подсказка 1
:::info
Если условие $a$ вложено в условие $b$ (т. е. $l_b \le l_a \le r_a \le r_b$) и не противоречит ему, то условие $a$ можно удалить.
:::

:::spoiler Подсказка 2
:::info
Пусть есть три условия $a$, $b$, $c$, причём $l_a \le l_b \le l_c$. Тогда если $a$ не противоречит $b$ и $b$ не противоречит $c$, то и $a$ не противоречит $c$.
:::

:::spoiler Подсказка 3
:::info
Постройте граф так, чтобы каждому пути соответствовало множество условий, не противоречащих друг другу.
:::

:::spoiler Решение
:::info
Построим граф на условиях. Из условия $a$ будет ребро в условие $b$ если $l_a < l_b$ и $a$ не противоречит $b$. Очевидно, что такой граф ацикличен. Каждому пути в нём будет соответствовать множество не противоречащих друг другу условий. Тогда ответ на задачу - минимальное покрытие этого графа вершинно-непересекающимися путями.
:::
