В ходе встречи были рассмотрены задачи досрочного этапа ЕГЭ, особое внимание уделили заданиям, условия которых отличны от демонстрационного варианта ФИПИ.

Кроме того учителя поделились различными способами решения задач. Что является важным для индивидуального подхода к обучающимся. Также был сделан анализ пробного ОГЭ,
Обратили внимание на решения задач ОГЭ. На новые возможные задачи EXCEL и Кумир.

Вне темы обсудили районный этап Региональной олимпиады по Информатике и Программированию для 6-8 класса. Для школ были озвучены имена победителей и призеров олимпиады.

Приведены примеры заданий, рассмотренных на МО

Задача ЕГЭ 27

В задаче ЕГЭ 27 проверяется умение составлять программу для работы с числовыми последовательностями. Задание из двух частей: файл а небольшой, можно сделать простой переборный алгоритм грубой силой, для файла б нужно применять динамическое программирование или догадываться до нетипового решения.

В 2022 году на ЕГЭ были задачи с оптимизацией перевозок по кольцевой дороге, аналогичная задача была на досрочном ЕГЭ 2024 года.

Пример задачи 27 2022 года (с сайта К.Ю. Полякова № 123:

(ЕГЭ-2022) На кольцевой автодороге с двусторонним движением находится N заправочных станций. Длина кольцевой автодороги равна K км, нулевой километр и K-й километр находятся в одной точке. Код заправочной станции совпадает с расстоянием этой станции до нулевой отметки дороги в километрах. На заправочные станции нужно ежедневно доставлять бензин из бензохранилища, которое требуется разместить рядом с одной из заправочных станций. Бензин поставляется в цистернах объёмом V м3 каждая, затраты на доставку вычисляются как произведение расстояния на количество поездок бензовоза. За один рейс бензовоз доставляет бензин только на одну заправочную станцию. Бензохранилище расположено так, чтобы суммарные затраты на доставку бензина были минимальными. Определите минимально возможные суммарные затраты на доставку бензина.

Входные данные: Даны два входных файла: файл A (27-123a.txt) и файл B (27-123b.txt), каждый из которых в первой строке содержит три числа N, K и V (1 < N ≤ 10 000 000, 1 < K ≤ 10 000 000, 1 < V ≤ 1000) – количество заправочных станций, длину кольцевой автодороги в километрах и объём цистерны. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена заправочная станция, и количество бензина, которое нужно туда доставить (все числа натуральные). Заправочные станции перечисляются в порядке их расположения на автодороге.

Пример входного файла:

5 11 3

1 8

3 7

5 6

7 5

9 3

При таких исходных данных лучше всего расположить бензохранилище около заправочной станции с кодом 3. При этом затраты на доставку бензина составят 2·3 + 2·2 + 4·2 + 5·1 = 23. Ответ: 23.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Решение.

Необходимо разработать две программы, первая будет подсчитывать стоимость перевозок в лоб. В этой программе можно продумать и отладить ввод данных. В этой программе трудно ошибиться, поэтому результат её работы будет эталоном и для более сложной программы при отладке.

Данные будем хранить в списке data из K элементов – сколько рейсов нужно сделать на каждый километр. Индекс в списке будет соответствовать километру. Начальный элемент, соответствующий километру 1, окажется в списке начальным элементом с индексом 0, поскольку в списке нумерация начинается с нуля. Если в задаче нужен будет номер километра, то при выводе придётся добавить единицу к номеру с нуля.

То есть data[i] – это необходимое количество рейсов на i-й километр. Если на i-м километре нет заправочной станции, количество рейсов будет ноль. Если на i-й километр нужно доставить q литров бензина, то количество рейсов будет

data[i] = (q – 1) // v + 1

Во входном файле первая строка не такая, как остальные, поэтому при вводе удобно открыть файл, обработать первую строку одним способом, а потом обработать все оставшиеся строки другим способом.

Получаем часть программы с вводом данных (Рис.1).

Переберём все возможные места расположения бензохранилища километр за километром. Если на i-м километре нет бензозаправочной станции, этот километр пропустим.

Для обхода по кругу удобно использовать отрицательные индексы в списках на Python. Начальный километр будет отрицательным, поэтому следующие номера можно получить добавлением числа от 0 до K-1 без выхода за границы массива.

В первую половину станций ближе ехать по часовой стрелке, а во вторую – ближе ехать против часовой стрелки. На рисунках приведены пример кольцевой дороги длиной 9 и 10 километров (Рис. 2 и 3).

Против часовой стрелки ближе ехать на последние k//2 километров и для четной и для нечетной длины кольцевой дороги. Против часовой стрелки мы поедем в станции, начиная с (k – k//2) километра.

Обозначим за j смещение от бензохранилища до станции в километрах. Для тех станций, куда мы едем по часовой стрелке, умножаем количество рейсов на j, а для тех, куда против часовой – на (k-j).

Теперь можно приступить к более сложной программе с динамическим программированием (Рис. 4). Если мы перенесем бензохранилище на один километр по часовой стрелке, то все те рейсы, которые мы делаем по часовой стрелке, сократятся на 1 км, а все те рейсы, которые против часовой стрелки – удлинятся на 1 км. Если хранить общее количество рейсов по часовой и против часовой стрелки, то очень легко скорректировать общую стоимость перевозки. Нужно скорректировать общее количество рейсов по часовой и против часовой стрелки. Тем, кто по часовой – укоротит путь на 1 км, а тем, кто против часовой – удлинить на 1км.

i – это номер километра, с которого мы уходим. Поэтому бензохранилище мы предполагаем установить на следующем километре (Рис. 5 и 6).