Задания ЕГЭ по информатике: разбор с педагогом

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

ЕГЭ по информатике, или, по-другому, КЕГЭ (компьютерный ЕГЭ), проходит только с использованием компьютера. Интернетом, разумеется, воспользоваться не получится. Всего есть 27 заданий с одним кратким ответом. Из них 11 заданий имеют базовый уровень сложности, 11 — повышенный и 5 — высокий. Задания №1-25 позволяют набрать по 1 первичному баллу. Задания № 26 и 27 дают по 2 первичных балла. Таким образом, максимум первичных баллов, которые можно получить за решение всех заданий, — 29.

Изменения ЕГЭ по информатике в 2024

В структуре КИМ ЕГЭ по информатике 2024 года нововведения отсутствуют. Однако задание № 13 претерпевает изменения традиционно каждый год, и 2024 не исключение. В этот раз «чёртова дюжина» будет проверять умение использовать маску подсети при адресации в соответствии с протоколом IP. 

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем, с некоторого разряда, – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.

Какие типы заданий есть на ЕГЭ по информатике

Всего в работу, как и в 2023 году, входит 27 заданий, охватывавших следующие содержательные разделы курса информатики: 

• информация и её кодирование; 
• моделирование и компьютерный эксперимент; 
• системы счисления; 
• логика и алгоритмы; 
• элементы теории алгоритмов; 
• программирование; 
• обработка числовой информации; 
• технологии поиска и хранения информации.

Задания: 

1. Анализ информационных моделей
2. Построение таблиц истинности логических выражений
3. Поиск информации в реляционных базах данных
4. Кодирование и декодирование информации
5. Анализ и построение алгоритмов для исполнителей
6. Определение результатов работы простейших алгоритмов
7. Кодирование и декодирование информации. Передача информации
8. Перебор слов и системы счисления
9. Работа с таблицами
10. Поиск символов в текстовом редакторе
11. Вычисление количества информации
12. Выполнение алгоритмов для исполнителей
13. Организация компьютерных сетей. Адресация
14. Кодирование чисел. Системы счисления
15. Преобразование логических выражений
16. Рекурсивные алгоритмы
17. Обработки числовой последовательности
18. Робот-сборщик монет
19. Выигрышная стратегия. Задание 1
20. Выигрышная стратегия. Задание 2
21. Выигрышная стратегия. Задание 3
22. Многопроцессорные системы
23. Оператор присваивания и ветвления. Перебор вариантов, построение дерева
24. Обработка символьных строк
25. Обработка целочисленной информации
26. Обработка целочисленной информации
27. Программирование

С чего начинать решение варианта ЕГЭ по информатике

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

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

Для набора от 80 баллов на ЕГЭ по информатике важно следовать стратегии. Вот несколько рекомендаций:

1. Прочтите все задания на варианте, оцените их сложность и начните с самых простых.
2. Сосредоточьтесь на задачах, в которых уверены и которые можете решить быстро.
3. Постарайтесь решить каждую задачу методом исключения, если не находите ответ сразу.
4. При решении задачи обращайте внимание на подсказки в условии, они могут вести к правильному ответу.
5. Не тратьте время на задачи, которые слишком сложны для вас. Можно вернуться к ним в конце экзамена, если останется время.
6. Проверьте свои ответы перед сдачей работы, исправьте ошибки и удостоверьтесь, что вы решили все задачи.
7. Не зацикливайтесь на задаче, если не получается ее решить. Переходите к следующей и вернитесь к затруднительной позже.

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

Самые частые ошибки по информатике и как их не сделать

Приведём анализ выполнения заданий от ФИПИ:

У участников ЕГЭ 2023 г. возникли затруднения при выполнении заданий повышенного и высокого уровней сложности, проверяющих следующие знания и умения: 

• знание основных понятий и законов математической логики; 
• умение анализировать результаты исполнения алгоритма; 
• умение обрабатывать целочисленную информацию с использованием сортировки; 
• умение создавать собственные программы (20–40 строк) для обработки целочисленной информации.

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

Особое внимание стоит уделить теме логики, так как на ней подростки часто теряют баллы из-за спешки или невнимательности. Из года в год ошибки допускаются в переводе чисел в различные системы исчисления. Тем не менее, разработчики КИМ считают, что решающими факторами, позволяющим ученикам набрать больше баллов в сравнении с другими, становятся уверенные навыки программирования и свободное владение математическими основами информатики.

Все ошибки можно разделить на 2 блока:

• по незнанию;
• по невнимательности.

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

Разберём некоторые структуры и типичные ошибки которые могут сделать выпускники.

Задание 12. Выполнение алгоритмов для исполнителей (≈6-8 мин)

Тема: Выполнение алгоритмов для исполнителей.

Что проверяется: умение анализировать результат исполнения алгоритма. 

Что нужно знать: 

• правила выполнения линейных, разветвляющихся и циклических алгоритмов;
• основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну);
• исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды;
• в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз;
• запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1.

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

Задание 13. Организация компьютерных сетей. Адресация (≈3-4 мин)

Тема: Компьютерные сети. Адресация в Интернете. 

Что нужно знать:

1. адрес документа в Интернете (URL = Uniform Resource Locator) состоит из следующих частей: 

• протокол, чаще всего http (для Web-страниц) или ftp (для файловых архивов);
• знаки ://, отделяющие протокол от остальной части адреса;
• доменное имя (или IP-адрес) сайта;
• каталог на сервере, где находится файл;
• имя файла.

2. принято разделять каталоги не обратным слэшем «\» (как в Windows), а прямым «/», как в системе UNIX и ее «родственниках», например, в Linux;

3. если два узла относятся к одной сети, то адрес сети у них одинаковый;

4. задачи на IP-адреса можно решать с помощью программы; для языка Python есть модуль ipaddress.

Возможные проблемы:

• ошибки с допустимым диапазоном 0..255;
• путаница с доменоми первого уровня и второго уровня;
• риск ошибиться при кодировании букв.

Задание 14. Преобразование логических выражений (≈3-4 мин)

Тема: Позиционные системы счисления.

Что проверяется: знание позиционных систем счисления. 

Что нужно знать: принципы кодирования чисел в позиционных системах счисления.

В этом задании возможны промахи при переводе чисел из одной системы в другую.

Разбор сложных заданий по информатике

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

Задание 6. Определение результатов работы простейших алгоритмов (≈4-5 мин)

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

Что проверяется: 

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

Что нужно знать и уметь: 

• выполнять ручную прокрутку программы для исполнителя, в которой используется цикл;
• строить на координатной плоскости фигуру, которую нарисует Черепаха (при ее известном начальном положении).

Задача:

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует три команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, и Налево m (где m — целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

Запись Повтори k [Команда1 Команда2 . . . Команда S] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:

Повтори 2 [Вперёд 9 Направо 90 Вперёд 15 Направо 90]

Поднять хвост

Вперёд 12 Направо 90

Опустить хвост

Повтори 2 [Вперёд 6 Направо 90 Вперёд 12 Направо 90]

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

Источник: ЕГЭ по информатике 20.06.2023. Основная волна. Дальний Восток

Решение.

Приведём решение на языке «КуМир»

Выберите масштаб сетки равным 1, запустите программу для исполнителя Черепаха.

использовать Черепаха 

алг

нач

опустить хвост 

нц 2 раз

вперед (9)

вправо (90)

вперед (15)

вправо (90)

кц

поднять хвост

вперед (12)

вправо (90)

опустить хвост

нц 2 раз

вперед (6)

вправо (90)

вперед (12)

вправо (90)

кц

кон

После выполнения программы считаем количество точек с целочисленными координатами внутри объединения фигур, ограниченных заданными алгоритмом линиями, не включая точки на линиях.

Получаем 127.

Задание 9. Работа с таблицами (≈6-8 мин)

Тема: Встроенные функции в электронных таблицах 

Что проверяется: 

• умение обрабатывать числовую информацию в электронных таблицах;
• использование инструментов решения статистических и расчётно-графических задач;
• умение представлять и анализировать табличную информацию в виде графиков и диаграмм. 

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

Задача:

Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Приведём здесь пример части таблицы из файла:

Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия: 

— в строке есть два числа, каждое из которых повторяется дважды, остальные числа различны;

— среднее арифметическое всех повторяющихся чисел строки меньше среднего арифметического всех её чисел.

Источник: Демонстрационная версия ЕГЭ−2024 по информатике

Решение.

Для начала, найдём количество повторений каждого числа. Для этого в ячейку H1 впишем =СЧЁТЕСЛИ($A1:$G1;A1), протянем до ячейки N1 и потом вниз до конца таблицы. Теперь найдем количество строк, удовлетворяющих первому условию, для этого впишем =ЕСЛИ(И(МАКС(H1:N1)<3;СУММ(H1:N1)=11);1;0) в ячейку O1 и протянем вниз до конца таблицы.

Теперь выпишем отдельно повторяющиеся числа. В ячейку P1 впишем =ЕСЛИ(H1=2;A1;" ") и протянем до V1 и вниз до конца таблицы. 

Наконец, найдем искомую величину. В ячейку W1 впишем =ЕСЛИ(O1=1;ЕСЛИ(СРЗНАЧ(P1:V1)<СРЗНАЧ(A1:G1);1;0);0) и протянем вниз до конца таблицы. 

Теперь в ячейку X1 впишем =СУММ(AD:AD) и получим ответ  — 83.

Примечание. Если писать код, к примеру, на Python, то файл требуется сохранить в формате txt.

Задание 17. Обработки числовой последовательности (≈15-18 мин)

Тема: Перебор последовательности целых чисел. Проверка делимости. 

Что проверяется: 

• умение создавать собственные программы (20–40 строк) для обработки целочисленной информации;
• основные конструкции языка программирования, система программирования;
• умение создавать программы на языке программирования по их описанию. 

Что нужно знать:

• в известных задачах этого типа (не олимпиадных) нет ограничения на время выполнения, по крайней мере, оно несущественно для отрезков, заданных для перебора; поэтому можно использовать простой перебор без оптимизации; 

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

Задача:

В файле содержится последовательность натуральных чисел, каждое из которых не превышает 100 000. Определите количество троек элементов последовательности, в которых ровно два из трёх элементов являются трёхзначными числами, а сумма элементов тройки не больше максимального элемента последовательности, оканчивающегося на 13. Гарантируется, что в последовательности есть хотя бы одно число, оканчивающееся на 13. В ответе запишите количество найденных троек чисел, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Источник: Демонстрационная версия ЕГЭ−2024 по информатике

Приведём пример части чисел из файла:

6633 4838 33100 55 86 95340 9008 6786 99 81 4889 989 49498 8751 66…

Решение.

Приведём решение на языке Python.

f = open('17_2024.txt')

s = f.readlines()

for i in range(len(s)):

    s[i] = int(s[i])

count = 0

maxi = 0

maxsum = 0

for i in range(len(s)):

    if abs(s[i]) % 100 == 13:

        maxi = max(maxi, s[i])

for i in range(2, len(s)):

    k1 = 0

    k2 = 0

    k3 = 0

    c1 = abs(s[i-2])

    c2 = abs(s[i-1])

    c3 = abs(s[i])

    while c1 > 0:

        k1 += 1

        c1 //= 10

    while c2 > 0:

        k2 += 1

        c2 //= 10

    while c3 > 0:

        k3 += 1

        c3 //= 10

    if (k1 == 3 and k2 == 3 and k3 != 3) or (k1 == 3 and k2 != 3 and k3 == 3) or (k1 != 3 and k2 == 3 and k3 == 3):

        if s[i-2] + s[i-1] + s[i] <= maxi:

            count += 1

            maxsum = max(maxsum, s[i-2] + s[i-1] + s[i])

print(count, maxsum)

В результате работы данного алгоритма при вводе данных из файла ответ — 959 97471.

Ответ: 959 97471

Задание 18. Робот-сборщик монет (≈6-8 мин)

Тема: Динамическое программирование.

Что проверяется:

• умение обрабатывать вещественные выражения в электронных таблицах;
• использование инструментов решения статистических и расчётно-графических задач;
• умение представлять и анализировать табличную информацию в виде графиков и диаграмм.

Что нужно знать:

• в задачах, которые предлагаются в этом задании КИМ, нужно найти оптимальный путь для Робота, который перемещается на клетчатом поле (Робот может на каждом шаге выбирать одно из двух направлений движения, например, только вправо и вниз);
• в каждой клетке Робот получает некоторую награду («берёт монету»), и нужно найти такой путь, при котором общая награда будет наибольшая (или наименьшая, если это не награда, а штраф);
• теоретически можно решить такую задачу полным перебором вариантов: рассмотреть все возможные пути и выбрать лучший. (однако количество возможных путей для полей даже не очень большого размера слишком велико для того, чтобы решить эту задачу за время проведения ЕГЭ, даже если вам удастся безошибочно написать программу для такого перебора); 
• эта задача быстро решается с помощью динамического программирования – метода оптимизации, предложенный американским математиком Ричардом Беллманом, который сформулировал очень простой принцип оптимальности пути: любая часть оптимального пути оптимальна.

Задача:

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо и вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз - в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

В ответе укажите два числа сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.

Пример входных данных:

Для данных из примера ответ: 34 22.

Источник: ЕГЭ по информатике 06.04.2023. Досрочная волна

Решение.

Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. Для каждой ячейки верхней строки это будет сумма всех ячеек слева от текущей. Для каждой ячейки левого столбца это будет сумма всех ячеек сверху от текущей. В ячейку A22 запишем формулу =СУММ($A$1:A1). Скопируем эту формулу во все ячейки в диапазоне B22:T22 и в диапазоне A23:A41.

Для ячеек С30:С34, E25:E38, Q29:Q33 и S24:S38, поскольку слева от них имеется внутренняя стенка, максимальная денежная сумма вычисляется как сумма текущей ячейки и суммы сверху, в ячейку C30 запишем формулу =C29+C9 и скопируем её во все ячейки диапазона С30:С34. Аналогично поступаем для всех ячеек диапазонов E25:E38, Q29:Q33 и S24:S38.

Для ячеек F24:J24, I27:M27, K30:O30, K33:O33, I36:M36 и F40:J40, поскольку сверху от них имеется внутренняя стенка, максимальная денежная сумма вычисляется как сумма текущей ячейки и суммы слева, в ячейку F24 запишем формулу =E24+F3 и скопируем её во все ячейки диапазона F24:J24. Аналогично поступаем для всех ячеек диапазонов I27:M27, K30:O30, K33:O33, I36:M36 и F40:J40.

Для остальных ячеек будем сравнивать значение ячейки слева и значение ячейки сверху и присваивать текущей ячейке значение суммы той ячейки, в которой значение больше, и текущей ячейки. В B23 запишем формулу =МАКС(A23+B2;B22+B2) и скопируем эту формулу во все оставшиеся ячейки диапазона B23:T41. Таким образом, в ячейке T41 получим значение максимальной денежной суммы  — 1102.

Аналогичным образом найдём значение минимальной денежной суммы. В B23 запишем формулу =МИН(A23+B2;B22+B2) и скопируем эту формулу во все оставшиеся ячейки диапазона B23:T41. Таким образом, в ячейке T41 получим значение минимальной денежной суммы  — 1029.

Ответ: 1102 1029.

Задание 21. Выигрышная стратегия (≈11-12 мин)

Тема: Теория игр. Поиск выигрышной стратегии.

Что проверяется:

• умение анализировать алгоритм логической игры;
• умение найти выигрышную стратегию игры;
• умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию;
• цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности;
• умение строить информационные модели объектов, систем и процессов в виде алгоритмов.

Что нужно знать:

• в простых играх можно найти выигрышную стратегию, просто перебрав все возможные варианты ходов соперников;
• теория и навык построения «дерева игры».

Задача:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 18 или 30 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 47.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Источник: ЕГЭ по информатике 20.06.2023. Основная волна. Дальний Восток

Решение.

Минимальное значение S: 19. После первого хода Пети в куче будет 20, 22 или 38 камней. Если в куче станет 38 камней, Ваня увеличит количество камней в 2 раза и выиграет первым ходом. Когда в куче 20 или 22 камней, можно получить кучу из 23 камней (при S = 20 нужно добавить 3 камня, при S = 22 нужно добавить 1 камень). Тогда после второго хода Пети в куче будет 24 камней, или 26 камней, или 46 камней. Во всех случаях Ваня увеличивает количество камней в куче в 2 раза и выигрывает вторым ходом. Таким образом, ответ — 19.

Ответ: 19.

Задание 24. Обработка символьных строк (≈18-22 мин)

Тема: Обработка символьных строк.

Что проверяется:

• умение создавать собственные программы (10–20 строк) для обработки символьной информации;
• цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности;
• строить информационные модели объектов, систем и процессов в виде алгоритмов. 

Что нужно знать:

• первым делом нужно прочитать строку из файла; эта задача в разных языках программирования решается несколько по-разному;
• уметь находить самую длинную цепочку любых символов с заданными параметрами поиска.

Задача:

Текстовый файл состоит из заглавных букв латинского алфавита Q, R, W и цифр 1, 2, 4. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых ни одна буква не стоит рядом с буквой, а цифра  — с цифрой. Для выполнения этого задания следует написать программу.

Источник: ЕГЭ по информатике 09.04.2024. Досрочная волна

Приведём пример части символов из файла:

4211224Q241Q2441424424114141QW2121211W41211Q44W222R4222R42444141242144QR4241444111414211R141241R22212Q211212…

Решение.

Приведём решение на языке Python.

f = open('1_24.txt')

s = f.read()

count, maxi = 1,0

i = 0

for i in range(1,len(s)):

    if (s[i-1] not in 'QRW' or s[i] not in 'QRW') and (s[i-1] not in '124' or s[i] not in '124'):

        count += 1

    else:

        maxi = max(maxi,count)

        count = 1

print(maxi)

В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 17.

Ответ: 17.

Задание 26. Обработка целочисленной информации (≈35-40 мин)

Тема: Обработка массива целых чисел из файла. Сортировка.

Что проверяется:

• умение обрабатывать целочисленную информацию с использованием сортировки;

• построение алгоритмов и практические вычисления;

• строить информационные модели объектов, систем и процессов в виде алгоритмов.

Что нужно знать при написании программы: 

• чтение данных из файла;
• хранение массива данных;
• сортировка массива.

Задача:

В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 4 единицы меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.

Входные данные

В первой строке входного файла находится число N — количество форм для коржей в кондитерской (натуральное число, не превышающее 10 000). В следующих N строках находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой форме. Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем — максимально возможный диаметр самого маленького коржа в таком торте.

Типовой пример организации данных во входном файле:

5 43 40 32 40 30

Пример входного файла приведён для пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящих для изготовления многоярусного торта, составляет 3 единицы. 

При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т. е. количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Приведём пример части цифр из файла:

10000 1480 3624 9615 6566 2940 8611 2954 5464 4730 3074 6966…

Источник: ЕГЭ по информатике 09.04.2024. Досрочная волна

Решение. 

Приведем решение на языке Python.

f = open('1_26.txt')

n = int(f.readline())

a = [int(i) for i in f]

a.sort(reverse = True)

count = 1

diametr = a[0]

for i in range(1,len(a)):

    if diametr - a[i] >= 4:

        count += 1

        diametr = a[i]

print(count,diametr)

Ответ: 2172 50.

Задание 27. Программирование (≈35-45 мин)

Тема: Обработка данных, вводимых из файла в виде последовательности чисел. 

Что проверяется: 

• умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей;
• построение алгоритмов и практические вычисления;
• строить информационные модели объектов, систем и процессов в виде алгоритмов. 

Что нужно знать: 

• как прочитать данные из файла;
• основы комбинаторики;

• динамическое программирование.

Важно. Так как в компьютерном ЕГЭ само решение не проверяется и основной задачей становится получение правильного ответа, возможно, не будет задач 27, которые можно решить переборными алгоритмами с квадратичной сложностью (оценка O(n2)). Задача 27 в демоварианте КИМ даёт представление о типе задач, которые такими алгоритмами не решаются. Вероятно, будут предложены задачи, в которых полный перебор вариантов имеет сложность O(2N) или O(N!), однако использование динамического программирования позволяет быстро решить задачу за один проход.

Задача:

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить количество пар, для которых произведение элементов кратно 62.

Входные данные.

Файл A

20 410 964 971 509 214 6 786 710 224 246 892 392 290 104 901 821 688 301 109 159

Файл B

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. В качестве результата программа должна вывести одно число: количество пар, в которых произведение элементов кратно 62.

Пример организации исходных данных во входном файле: 5 2 6 13 31 93

Пример выходных данных для приведённого выше примера входных данных: 4 

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

Пояснение. Из 5 чисел можно составить 4 пары, удовлетворяющие условию. Для заданного набора чисел получаем пары (2, 31), (2, 93), (6, 31), (6, 93).

Приведём пример части цифр из файла:

60000 886 348 587 484 459 735 437 144 89 438 570 375 256 834 534…

Решение.

Произведение двух чисел делится на 62, если выполнено одно из следующих условий (условия не могут выполняться одновременно).

А.  Оба сомножителя делятся на 62.

Б.  Один из сомножителей делится на 62, а другой не делится.

В.  Ни один из сомножителей не делится на 62, но один сомножитель делится на 2, а другой — на 31.

При вводе чисел можно определять, делится ли каждое из них на 62, 2 и 31, и подсчитывать следующие значения:

1)  n62 — количество чисел, кратных 62;

2)  n31 — количество чисел, кратных 31, но не кратных 62;

3)  n2 — количество чисел, кратных 2, но не кратных 62.

Количество пар, удовлетворяющих условию А, можно вычислить по формуле n62 · (n62 – 1)/2.

Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n62 · (N – n62). 

Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 · n31.

Поэтому искомое количество пар вычисляется по формуле n62 · (n62 – 1)/2 + n62 · (N – n62) + n2 · n31.

Решение.

Напишем решение задачи на языке Pascal.

var

     N: integer; {количество чисел}

      a: integer; {очередное число}

      n62, n31, n2: integer;

      k62: integer; {количество требуемых пар}

      i: integer;

  f: text;

begin

n62:=0; n31:=0; n2:=0;

assign(f,'27989_A.txt');

reset(f);

readln(f, n);

for i := 1 to n do begin

readln(f, a);

if a mod 62 = 0 then

              n62 := n62+1

        else if a mod 31 = 0 then

             n31:= n31 + 1

         else if a mod 2 = 0 then

             n2 := n2 + 1;

     end;

     k62 := n62*(n62-1) div 2 + n62*(N-n62) + n2*n31;

     writeln(k62)

end.

В результате работы данного алгоритма при вводе данных из файла A ответ — 0, из файла B — 82307095.

Примечание. Путь к файлу необходимо указать согласно расположению файла на вашем компьютере.

Приведём другое решение на языке Python.

f = open("27990_B.txt")  # для файла A укажите его название 

s = f.readlines()

n = int(s[0])

k = 0

k_0 = 0

k_62 = 0

k_2 = 0

k_31 = 0

for i in range(1, n + 1):

    s[i] = int(s[i])

    if s[i] % 62 == 0:

        k_62 += 1

    elif s[i] % 31 == 0:

        k_31 += 1

    elif s[i] % 2 == 0:

        k_2 += 1

    else:

        k_0 += 1

k = k_62 * k_0 + k_31 * k_2 + k_62 * k_31 + k_62 * k_2 + (k_62 * (k_62 - 1)) // 2

print(k)

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

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

Удачи на экзамене!

Текст подготовил Моисеенко Александр Алексеевич