Информатика ЕГЭ — решения заданий ФИПИ с ответами

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

Для каждой коробки определите максимальную длину цепочки, заканчивающейся этой коробкой. Предыдущая коробка должна иметь длину стороны не более $a_i - 13$.

Петя может выиграть за один ход, если после одного из разрешённых действий в куче будет не менее 68 камней. Условия $S+1 \geq 68$ и $S+4 \geq 68$ дают только значения, уже входящие в диапазон $14 \leq S \leq 67$, а условие $5S \geq 68$…$$S \in \{14,15,\ldots,67\}$$

Для задания 1б подходит $S=2$. Петя не может выиграть одним ходом: после его ходов получится 3, 6 или 10 камней. Из каждой из этих позиций Ваня выигрывает своим первым ходом: соответственно, умножением на 5 получает 15, 30 или 50? Нет…

Создаём массив времени освобождения ячеек. Изначально все ячейки свободны; это можно обозначить временем освобождения 0.

Заявки обрабатываются в порядке, указанном во входном файле. Для заявки с временем сдачи багажа t просматриваем ячейки по возрастанию номеров.

Рассмотрим позиции $(6, 27)$ и $(8, 26)$. Из позиции $(6, 27)$ возможны переходы в $(7, 27)$, $(12, 27)$, $(6, 28)$ и $(6, 54)$. В первых трёх позициях удвоение второй кучи приводит к сумме не менее 61, а из $(6, 54)$ соперник может сразу…$$6+27=33$$

Аналогично позиция $(8, 26)$ является проигрышной для игрока, делающего ход: любой его ход переводит игру в позицию, из которой следующий игрок может завершить игру или перейти к проигрышной для соперника позиции.

Сначала отсортируем все длины сторон коробок по возрастанию. Одинаковые коробки нельзя использовать последовательно, так как разность их сторон меньше 6.$$a_1 \leqslant a_2 \leqslant \dots \leqslant a_N$$

Будем просматривать отсортированный массив слева направо. Первую выбранную коробку включаем в цепочку, а следующую включаем только при выполнении условия размещения.$$a_i-a_{\text{last}}\geqslant 6$$

Считаем мероприятия совместимыми, если начало следующего мероприятия не меньше окончания предыдущего.

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

Петя может выиграть первым ходом, если после одного из разрешённых действий сумма камней станет не менее 63. Из позиции $(5,S)$ удвоение второй кучи даёт сумму $5+2S$, поэтому требуется $5+2S \geq 63$, то есть $S \geq 29$. При $S \geq 29$…$$5+2S\geq 63\Longleftrightarrow S\geq 29$$

Следовательно, в задании 1а подходят все значения $S$ от 29 до 57 включительно.

Для каждой записи накапливаем сумму цен и количество товаров. Средняя цена вычисляется как сумма всех цен, делённая на $N$.$$\overline{p}=\frac{\sum_{i=1}^{N}p_i}{N}$$

Для каждого артикула подсчитываем число проданных товаров $sold$, число оставшихся товаров $left$ и сохраняем цену артикула.

Сгруппируем занятые места по номерам рядов и отсортируем номера мест внутри каждого ряда.

Для двух соседних занятых мест с номерами $a$ и $b$ количество свободных мест между ними равно $b-a-1$. Если первое занятое место в ряду имеет номер $b$, перед ним свободно $b-1$ кресел.$$free=b-a-1$$

Сгруппировать занятые места по номерам рядов.

Для каждого ряда упорядочить номера занятых мест по возрастанию.

Считаем все длины сторон коробок и сортируем их по возрастанию.$$a_1 \leq a_2 \leq \dots \leq a_N$$

Последовательно строим цепочку. Очередную коробку можно добавить, если её сторона отличается от стороны последней выбранной коробки не менее чем на 3.$$a_i-a_{last}\geq 3$$

Из исходной позиции $(3,2)$ первый игрок может получить только четыре различные позиции: $(9,2)$, $(6,2)$, $(3,6)$ или $(3,5)$.

Если первый игрок получил позицию $(9,2)$, второй игрок умножает число камней в первой куче на 3 и получает $27$ камней. Если получена позиция $(3,6)$, второй игрок умножает вторую кучку на 3 и получает $18$ камней, а затем анализ…

Считаем, что коробки вложены от меньшей к большей. Для соседних выбранных коробок должно выполняться условие разности сторон не менее 10.$$a_{i+1} - a_i \geq 10$$

Отсортируем все длины сторон по возрастанию.

Для решения необходимо получить пары сроков хранения из прилагаемого входного файла и объединить все $2N$ значений в один список с указанием продукта и типа срока.

Значения следует обрабатывать по возрастанию. Если первым ещё не обработанным значением является срок хранения продукта, его место определяется слева; если это срок годности после вскрытия, его место определяется справа.

Для каждого продукта создаём две записи: срок хранения с момента изготовления и срок годности после вскрытия. Каждой записи сопоставляем номер продукта и тип срока.

Сортируем все записи по возрастанию значения срока. Так как все исходные числа различны, порядок обработки однозначен.

Игрок выигрывает одним ходом, если после прибавления одного камня или удвоения количество камней становится не менее 65. При $S \geq 33$ достаточно удвоения. При $S=64$ можно также прибавить один камень.$$2S \geq 65 \Rightarrow S \geq 33; \qquad S+1 \geq 65 \Rightarrow S=64$$

Для задания 1б подходит $S=32$: Петя не может выиграть сразу, но после его хода получаются позиции $33$ или $64$, из которых Ваня выигрывает одним ходом.

Для каждой позиции рассматриваются четыре возможных хода: (a+1,b), (3a,b), (a,b+1), (a,3b). Если после хода сумма не менее 74, ход является немедленно выигрышным.

В позициях (4,23) и (7,22) выигрышная стратегия есть у Вани. После любого хода Пети Ваня получает возможность закончить игру или перевести её в позицию, из которой Петя вынужден открыть Ване немедленную победу.$$W(4,23)=W(7,22)=\text{Ваня}$$

Сгруппируем занятые места по номерам рядов и для каждого ряда определим максимальный номер занятого места.

В ряду с максимальным занятым номером $q$ подходящая пара может начинаться только после этого места. Поэтому проверяем места $q+1$ и $q+2$: если они существуют, то пара $q+1$, $q+2$ свободна, а перед ними нет занятых мест.

Задание 1. Из позиции $(14,S)$ можно получить либо $(14+S,S)$ с суммой $14+2S$, либо $(14,14+S)$ с суммой $28+S$.$$14+2S\ge 65 \quad\text{или}\quad 28+S\ge 65$$

Первое неравенство даёт $S\ge 25{,}5$, поэтому при целом $S$ получаем $S\ge 26$. Второе даёт $S\ge 37$. Минимальное подходящее значение — $S=26$; Петя получает позицию $(40,26)$ с суммой 66.$$14+2\cdot 26=66$$

Для максимального количества контейнеров выгодно выбирать самые лёгкие контейнеры: замена любого выбранного контейнера на более лёгкий не увеличивает суммарную массу.

Отсортируем массив масс по возрастанию.$$m_1 \leq m_2 \leq \dots \leq m_N$$