Тапсырма 26 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

Сортируем все диаметры по убыванию. Для каждого выбранного коржа следующий можно взять только тогда, когда разность диаметров соседних выбранных коржей не меньше 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. Последнюю букву пишет Петя, поэтому выигрышная стратегия есть у Пети.

Удобно хранить для каждого ряда множество занятых мест, чтобы проверять принадлежность за постоянное время.$$occupied[row] = \{\text{занятые места в ряду}\}$$

Две соседние свободные места с занятыми местами слева и справа имеют вид $x+1$ и $x+2$, при этом места $x$ и $x+3$ заняты, а $x+1$ и $x+2$ не заняты.$$x \in occupied,\quad x+1 \notin occupied,\quad x+2 \notin occupied,\quad x+3 \in occupied$$

Позиция (4, 20) выигрышна для Пети: первым ходом он утраивает вторую кучу и получает сумму 4 + 60 = 64? Нет, при правильном подсчёте после утроения второй кучи получается позиция (4, 60), сумма 64; поэтому этот ход не является немедленной…

При обратном анализе проигрышными для игрока, которому предстоит ход, являются позиции (4, 21), (7, 20), (5, 20). Поэтому в позициях (4, 21) и (7, 20) выигрышная стратегия принадлежит Ване.