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

Считать количество ячеек K и количество заявок N. Для каждой ячейки сохранить время, с которого она свободна; изначально все ячейки свободны.

Для каждой заявки с временем сдачи t и временем освобождения e просмотреть ячейки от первой к последней и выбрать первую ячейку, для которой её время доступности не позже t.$$free_i \le t$$

Представим каждую заявку как интервал [начало, окончание]. Мероприятия совместимы, если начало следующего не меньше окончания предыдущего.

Для максимизации количества мероприятий применяем жадный алгоритм: сортируем интервалы по времени окончания и выбираем очередной интервал, если он начинается не раньше окончания последнего выбранного.$$start_i \ge end_{last}$$

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

Рассмотрим две соседние в отсортированном списке занятые места $x$ и $y$. Между ними могут находиться две соседние свободные позиции, ограниченные занятыми местами слева и справа, если $y-x\geq 3$.$$y-x\geq 3$$

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

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

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

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

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

Две соседние свободные места, ограниченные занятыми местами слева и справа, имеют вид $a+1$ и $a+2$. Поэтому соседние занятые места должны иметь номера $a$ и $a+3$.$$b-a=3$$

В первом задании Петя может заменить число $9$ на сумму чисел и получить позицию $(9+S,S)$. Её сумма равна $9+2S$. Для победы одним ходом необходимо:$$9+2S\geq36$$

Получаем $2S\geq27$, то есть $S\geq13{,}5$. Так как $S$ — целое число, минимальное значение равно $14$. При замене числа $S$ условие было бы $18+S\geq36$, то есть $S\geq18$, поэтому найденное значение действительно минимально.$$S_{\min}=14$$

Сортируем все диаметры по убыванию. Для каждого выбранного коржа следующий можно взять только тогда, когда разность диаметров соседних выбранных коржей не меньше 4.$$d_i - d_{i+1} \geq 4$$

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

В задании 1а длина слова АБВГДАБВГДХ равна 11. Если Петя первым пишет букву А, дальнейшие ходы определены однозначно, и Петя получает последнюю, одиннадцатую букву. Значит, он выигрывает.$$11 \text{ — нечётное число}$$

Слово ДГВБАДГВБА имеет длину 10. Если Петя начинает с буквы Д, последнюю, десятую букву, пишет Ваня. Поэтому Петя выбирает А и использует выигрышную стратегию.

В задании 1а первое слово начинается с А, второе — с Д. Петя может выбрать любую из этих букв.

Если Петя выбирает А, дальнейшее продолжение однозначно и заканчивается словом АБВГДАБВГДХ длины 11. Последнюю, одиннадцатую, букву дописывает Петя, поэтому Петя выигрывает.

Из начальной позиции $(6,S)$ Петя может выиграть одним ходом, если после добавления камня или утраивания одной из куч сумма станет не менее 68.

Добавление одного камня в любую кучу даёт условие $7+S\geq68$, то есть $S\geq61$. Утраивание первой кучи даёт $18+S\geq68$, то есть $S\geq50$. Утраивание второй кучи даёт $6+3S\geq68$, то есть $S\geq21$.

В задании 1 из позиции $(9,S)$ Петя может получить $(9,9+S)$ с суммой $18+S$ или $(9+S,S)$ с суммой $9+2S$. Чтобы Петя не мог выиграть одним ходом, обе суммы должны быть меньше 26.$$18+S<26,\quad 9+2S<26$$

Получаем $S<8$ и $S<8{,}5$. Максимальное неотрицательное целое значение — $S=7$.

За один ход из позиции $S$ можно получить $S+1$ или $2S$. Петя выигрывает первым ходом, если один из результатов не меньше 26.

Условие $S+1 \geq 26$ даёт $S=25$, а условие $2S \geq 26$ даёт $S \geq 13$. Поэтому все значения: $13,14,\ldots,25$.

Считать все пары времени начала и окончания мероприятий.

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

Для каждого кандидата вычисляем общий результат как сумму баллов за три испытания и собеседование.$$S = b_1 + b_2 + b_3 + b_4$$

Формируем рейтинговый список по трём ключам: общий результат по убыванию, баллы за собеседование по убыванию, ID по возрастанию.

Для каждой заявки обозначим время начала через $start_i$, а время окончания — через $end_i$. Две заявки $j$ и $i$ совместимы, если мероприятие $j$ заканчивается не позднее начала мероприятия $i$.$$end_j \le start_i$$

Отсортируем все заявки по времени окончания. Для каждой заявки $i$ вычислим $dp_i$ — максимальное количество мероприятий в расписании, последним из которых является мероприятие $i$.

1а. Из начальной позиции $(5,S)$ Петя может выиграть одним ходом, если удвоение второй кучи даёт сумму не менее 75: $5+2S\geq75$. Отсюда $S\geq35$. Удвоение первой кучи требует $10+S\geq75$, то есть $S\geq65$, что уже входит в найденный…$$35\leq S\leq69$$

1б. Петя может сделать невыигрышный ход, удвоив первую кучу: $(5,S)\to(10,S)$. Ваня затем удваивает вторую кучу. Для победы Вани нужно $10+2S\geq75$, поэтому $S\geq32{,}5$. Минимальное целое значение — $S=33$.

Из начальной позиции $(7,S)$ Петя может выиграть первым ходом, если удвоение второй кучи даёт сумму не менее 77: $7+2S\geq77$, то есть $S\geq35$. Удвоение первой кучи даёт условие $14+S\geq77$, то есть $S\geq63$, которое уже входит в…

Для задания 1б достаточно взять минимальное $S$, при котором после неудачного хода Пети Ваня выигрывает сразу. При $S=18$ Петя может удвоить вторую кучу и получить позицию $(7,36)$. Ваня удваивает вторую кучу и получает $(7,72)$, сумма…

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

Для позиции (4, 27) выигрышная стратегия принадлежит Ване. После любого первого хода Пети Ваня выбирает ход, переводящий игру в позицию, из которой Петя не может гарантированно выиграть, а затем отвечает симметричным или компенсирующим…

В задании 1а слова начинаются с разных букв: А и Д. Петя выбирает букву А. После этого все ходы однозначны, и будет написано слово АБВГДАБВГДХ длины 11. Последний, 11-й ход делает Петя, поэтому Петя выигрывает. При этой стратегии возможна…

В задании 1б Петя выбирает букву Т. Далее продолжение однозначно: ТРИ повторяется 33 раза, длина слова равна 99. Последнюю букву пишет Петя, поэтому выигрышная стратегия есть у Пети.