Информатика ЕГЭ — ФИПИ тапсырмаларының жауаптарымен шешімдері

Для каждого студента подсчитываем количество оценок, равных 2, и сумму төрт оценок.$$twos_i = \#\{j \mid grade_{ij}=2\},\quad sum_i=\sum_{j=1}^{4}grade_{ij}$$

Студенты с нулевым количеством двоек сдали сессию. Их сортируем по убыванию суммы оценок, что эквивалентно сортировке по убыванию среднего балла, а при равенстве — по возрастанию ID.

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

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

Сгруппируем занятые места по нөмірлерге рядов и отсортируем нөмір мест внутри каждого ряда.$$r \to [m_1, m_2, \ldots, m_k]$$

Два соседних свободных места, ограниченные занятыми местами слева и справа, находятся между двумя занятыми местами, номера которых отличаются на 3.$$m_{i+1}-m_i=3 \Rightarrow (m_i+1,\ m_i+2)$$

Сортируем длины сторон коробок по возрастанию. В цепочке коробки идут в порядке возрастания, а разность между соседними сторонами должна быть не меньше 9.$$a_{i_{k+1}} \geq a_{i_k}+9$$

Для каждого элемента массива справа налево вычисляем максимальную длину цепочки, начинающейся с него. Если следующего подходящего элемента нет, длина цепочки равна 1; иначе к длине цепочки после следующего элемента прибавляем 1.$$dp_i = 1 + dp_j,\quad j=\min\{k>i\mid a_k\geq a_i+9\}$$

Создаём таблицу или словарь, где каждому идентификатору клиента соответствует суммарный объём переданных им данных.$$T_C = \sum S_i$$

Из полученных сумм выбираем значения не менее 150 000 Кбайт и находим сумму двух наименьших таких значений.

Считаем все заявки из файла и сортируем их по времени начала приёма.

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

В первом наборе слова начинаются с разных букв: А и Д. Если Петя начинает с А, все последующие буквы однозначно определены, и слово АБВГДАБВГДХ получается на 11-м ходу. Нечётный номер хода означает победу Пети.$$11 \equiv 1 \pmod 2$$

Если Петя начинает с Д, слово ДГВБАДГВБА получается на 10-м ходу, поэтому победил бы Ваня. Следовательно, выигрышная стратегия Пети — первым написать А, затем каждый раз приписывать единственную возможную букву.$$10 \equiv 0 \pmod 2$$

В задании 1 при замене числа 15 на сумму чисел получится позиция $(15+S,S)$ с суммой $15+2S$. При замене числа $S$ получится позиция $(15,15+S)$ с суммой $30+S$.$$15+2S\geq 62\quad\text{или}\quad 30+S\geq 62$$

Минимальное значение определяется первым неравенством: $S\geq 23$. При $S=23$ Петя заменяет число 15 на сумму чисел и получает позицию $(38,23)$ с суммой 61 — это недостаточно. Поэтому нужно внимательно выбрать ход: заменить число $S$ на…$$15+2S\geq62\Rightarrow S\geq\frac{47}{2}\Rightarrow S\geq24$$

Два соседних свободных места, ограниченных занятыми местами слева и справа, имеют вид $x+1$ и $x+2$, если заняты места $x$ и $x+3$.$$x \text{ занят},\quad x+3 \text{ занят}$$

В ряду 40 заняты места 3 и 6, поэтому подходящая пара начинается с места 4.

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

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

Игрок может выиграть одним ходом, если из текущей позиции можно получить не менее 36 камней. При $S<18$ это невозможно, поскольку даже удвоение даёт менее 36 камней. При $18\leq S\leq35$ удвоение приводит к позиции не менее 36.$$2S\geq36\Longleftrightarrow S\geq18$$

Следовательно, в задании 1а все значения $S$ имеют вид $18\leq S\leq35$.

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

Последовательно обрабатываем запросы. Если текущий объём данных в разделе плюс объём очередного запроса превышает вместимость $K$, создаётся резервная копия текущего объёма. Время такой копии соответствует времени текущего запроса, из-за…$$V + S > K$$

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

Отсортировать заявки по времени окончания, а при необходимости при равенстве окончаний — по времени начала.

Создаём массив времени доступности ячеек, изначально равный нулю.

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

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

Слово АБВГДАБВГДХ имеет длину 11. Если Петя начинает с буквы А, все последующие буквы определяются однозначно, и на одиннадцатом ходу слово получает Петя.$$11 \equiv 1 \pmod 2$$

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

Рассмотрим ход в позицию $(1, 6)$: первый игрок увеличивает в 3 раза число камней во второй куче.

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

Для каждого ряда и каждого начала пары $j$ от 1 до $K-1$ проверьте, свободны ли места $j$ и $j+1$ в текущем ряду.

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

Если Петя пишет А, далее буквы определяются однозначно, и получается слово длины 11. Последнюю букву записывает Петя, поэтому он выигрывает.

Представим каждую заявку как интервал [начало, конец]. Условие совместимости двух последовательных мероприятий: начало следующего должно быть не меньше окончания предыдущего.$$s_{next} \ge e_{last}$$

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

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

Для фиксированной самой маленькой коробки последовательно выбираем первую подходящую коробку справа: её сторона должна быть не меньше предыдущей стороны плюс 11.$$a_j - a_i \geq 11$$