ЕГЭ по информатике — Задание 27 (Делимость чисел)
Эта статья посвящена 27 заданию из ЕГЭ по информатике 2023.
В этой статье собраны некоторые задачи из 27 задания ЕГЭ по информатике, где нужно анализировать делимость чисел.
Перейдём к практике 27 задания из ЕГЭ по информатике.
Задача (Демонстрационный вариант 2021)
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000
Пример организации исходных данных во входном файле:
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Напишем программу на языке программирования Python для решения этого 27 задание из Демонстрационного варианта ЕГЭ по информатике.
Найдём максимальную сумму в переменную sm, выбирая из каждой пары максимальное число. В переменной delta будем хранить минимальную разницу между числами в паре, которая НЕ делится на 3.
Если максимальная сумма делится на 3, то мы должны отнять переменную delta от максимальной суммы. Это означает, что мы заменили какое-то число суммы на другой элемент из той же пары. При этом новое значение точно не будет делиться на 3, ведь delta не делится на 3. Значение delta — это минимальная разница между числами в парах, следовательно, сумма будет максимально возможной.
Ответ:
| 127127 | 399762080 |
Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй — нечётной. Определите минимально возможную сумму всех чисел в третьей группе.
Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:
3
1 2 3
8 12 4
6 9 7
Для указанных данных искомая сумма равна 11, она соответствует такому распределению чисел по группам: (2, 8, 7), (3, 12, 9), (1, 4, 6).
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Запрограммируем задачу на языке программирования Pascal ABC.
В переменную sm1 будем суммировать минимальные числа из каждой тройки. В переменные sm2 и sm3 распределяем оставшиеся числа из каждой тройки в произвольном порядке.
Переменная delta — это минимальная разница между наименьшим элементом и двумя оставшимися числами в тройке. Переменная delta — это наименьшая вышеуказанная разница среди всех троек, причём, она должна быть нечётной.
Если сумма переменных sm2 и sm3 будет нечётной, то условие задачи уже выполняется. Пример: 3 + 2 = 5 (т.е. сумма чётного числа и нечётного числа даёт нечётное число). Или 4 + 3 = 7. Здесь название первой, второй и третей группы весьма условны.
Если же сумма переменных sm2 и sm3 чётная, то нужно заменить одно число из sm1 числом из sm2 или sm3. После замены наша сумма sm1 увеличится на значение delta. Нам не обязательно понимать, из какой группы сделали замену, т.к. всё равно мы меняем число из той группы, где получилось значение delta.
Из-за того, что delta — это нечётное число, то чётность суммы той группы, откуда мы сделали замену, изменится. Если у нас были две чётные группы, то одна станет чётной, а другая станет нечётной. Тоже самое касается и другого случая, когда у нас были две нечётные группы, то после замены опять одна станет чётная, а другая нечётная группа. Таким образом, после замены, условие задачи будет выполнено, и в переменной sm1 будет минимально возможная сумма при данных обстоятельствах.
Ответ:
| 185 | 100918194 |
Задача(Тройки чисел, тренируем мозги)
Дана последовательность, которая состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел как в первой, так и во второй группе должна быть нечётной. Определите максимально возможную сумму всех чисел в третьей группе.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000.
Пример входного файла:
3
1 3 8
9 12 4
7 11 10
Для указанных данных искомая сумма равна 31, она соответствует такому распределению чисел по группам: (1, 9, 7), (3, 4, 10), (8, 12, 11).
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Распределим числа на три группы, как в прошлой задаче. В первую и во вторую группу числа распределяем из тройки случайно, а в третью берём максимальное число.
1) Случай, когда в первой и второй группе разная чётность.
| Первая группа | Вторая группа | Третья группа |
| Сумма чётная | Сумма нечётная | Максимальная сумма |
В этом случае нет смысла менять числа из первой и второй группы. Если мы заменим два чётных числа, сумма первой и второй группы никак не поменяется. Если поменяем два числа с разной чётностью, то обе группы поменяют свою чётность. Где-то «лишняя единица» добавится, а где-то уберётся.
Когда меняем числа, имеем в виду, что речь идёт в пределах одной тройки.
Поэтому в этом случае нужно менять число из группы с максимальной суммой.
2) Случай, когда в первой и второй группе сумма чётная.
| Первая группа | Вторая группа | Третья группа |
| Сумма чётная | Сумма чётная | Максимальная сумма |
Здесь мы можем поменять два числа из первой и второй группы между собой, но эти два числа должны быть разной чётности (разность чисел по модули должна быть нечётной). Тогда из одной суммы уйдёт «лишняя единица», а в другую добавится, и тогда обе суммы станут нечётной.
Если у нас не окажется два числа разной чётности в пределах одной тройки для первой и второй группы, значит, нужно для обеих групп искать замены из третьей группы с максимальной суммой.
Узнаём какие же будут суммы в первой и второй группе.
Программа распечатала два нуля.
В файле a получается, что первая и вторая группа имеют чётные суммы. Теперь посмотрим, есть ли нечётная разница двух чисел в этих группах в пределах одной тройки.
Получается, что переменная delta осталась равной нулю, следовательно, нет такой пары, где числа были бы разной чётности в пределах одной тройки.
Переменную delta ищем не обязательно минимальной.
Получается, мы должны заменить одно число из первой группы, одно число из второй группы на числа из третьей группы с максимальной суммой. Замены на этот раз нужно производить из разных троек, т.к. мы не можем одно число из третьей группы отдать, и в первом случае и во втором случае.
Разница между заменяемыми числами должна быть минимальной и нечётной. Минимальной она должна быть из-за того, что мы хотим оставить сумму в третьей группе как можно большей.
Получается следующий результат.
Первый список a1 отвечает за первую группу. Второй список a2 за вторую группу. В них кладём разницу между элементами из первой, второй группы и максимальным элементом тройки. При добавлении сохраняем ещё номер тройки, чтобы не заменить в итоге одно число для первой и второй группы.
После этого сортируем по первому числу списки a1 и a2, для того чтобы найти минимальную разницу для каждой группы.
Максимальная сумма до замен равна 3032. После замены элемента из первой группы наша сумма sm3 уменьшится на 17. После замены элемента из второй группы наше сумма sm3 уменьшится на 19. Мы видим, что производим замены из разных троек, поэтому ответ для файла a получается 3032 — 19 — 17 = 2996.
Как подготовиться к 27-му заданию ЕГЭ на Python?
На примере этого задания:
Все полученные данные можно представить в виде списка неотрицательных целых чисел. От вас требуется пройти окошком ширины 5 этот список и посчитать сумму в каждом окошке.
Например:
Первое окно — это элементы с 0 по 4, второе — с 1 по 5, третье — с 2 по 6 и так далее вплоть до окна с (n-4) по n, в каждом по 5 элементов.
Заведите специальную переменную, где будете хранить максимум, при каждом сдвиге окошка сравнивайте текущую сумму с максимальной, если она больше имеющейся, то это ваш новый максимум.
- Вконтакте
5Kb), автор предлагает проходить по этим числам тем же самым окном ширины 5, но считывать в память только числа, входящие в текущее окно. С точки зрения экономии памяти — хорошее решение, более того, стандартное для поточных задач.
Если вам интересно с такими вещами более подробно разобраться — прорешайте (а не прочитайте) Кормена «Алгоритмы. Вводный курс.», потом можете почитать его же книжку «Алгоритмы. Построение и анализ», но это тот еще талмуд 🙂 Главное, что нужно вынести — асимптотики выполнения операций над структурами данных.
Name already in use
If nothing happens, download GitHub Desktop and try again.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching Xcode
If nothing happens, download Xcode and try again.
Launching Visual Studio Code
Your codespace will open once ready.
There was a problem preparing your codespace, please try again.
Latest commit
Git stats
Files
Failed to load latest commit information.
README.md
Задачи 27 ЕГЭ решение на Python
About
Задачи 27 ЕГЭ на Python
Resources
Stars
Watchers
Forks
Releases
Packages 0
Languages
Footer
© 2023 GitHub, Inc.
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Рубрика «ЕГЭ Задание 27»
ЕГЭ информатика 27 задание разбор, теория, как решать.
Создание программы для анализа числовых последовательностей, (В) — 2 балла
Е27.33 В городе M расположена кольцевая автодорога длиной в N километров
В городе M расположена кольцевая автодорога длиной в N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы стоимость доставки мусора была минимальной. Стоимость доставки мусора вычисляется, как вместимость пункта сбора …
Е27.32 определить количество таких подпоследовательностей, сумма элементов которых кратна 1111
Дана последовательность натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, состоящие более чем из ста элементов. Необходимо определить количество таких подпоследовательностей, сумма элементов которых кратна 1111. Входные данные Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что число в ответе не …
Е27.31 такие что сумма элементов каждой из них кратна k = 67
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 67. Найдите среди них подпоследовательность с максимальной суммой. Укажите в ответе найденную максимальную сумму. Входные данные Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел …
Е27.30 Необходимо определить количество её непрерывных подпоследовательностей
Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма элементов которых кратна 999. Входные данные Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел и число в ответе не превышают 2 ∙ 109. Вам …
Е27.29 сумма всех выбранных чисел имела такую же последнюю цифру
Дана последовательность, которая состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел имела такую же последнюю цифру, как наибольшая возможная, и при этом была минимальной возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — минимальную возможную сумму, соответствующую условиям задачи. Входные …
Е27.28 такие что сумма элементов каждой из них кратна k = 43
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них. Входные данные Даны два входных файла (файл A и …
Е27.27 последовательности, находящихся на расстоянии не меньше чем 5
последовательности, находящихся на расстоянии не меньше чем 5 На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5 (разница в индексах элементов пары должна быть 5 или более, порядок элементов в паре неважен). Необходимо определить количество таких …
Е27.26 чтобы сумма всех выбранных чисел не делилась на 7
чтобы сумма всех выбранных чисел не делилась на 7 Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 7 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Программа должна …
Е27.25 чтобы сумма всех выбранных чисел делилась на 4
чтобы сумма всех выбранных чисел делилась на 4. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел делилась на 4 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую …
Е27.24 Определите максимально возможную сумму всех чисел в третьей группе
Определите максимально возможную сумму всех чисел в третьей группе. Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй – нечётной. Определите максимально возможную сумму всех …