Леонид: Спасибо
20-09-2023
Читать статью
Калужский Александр: Леонид, цикл x повториться 300 раз, цикл..
Леонид: Почему k == 90000 в примере (x > A) ∨ (y..
Привет! Сегодня мы рассмотрим последнее 27 задание из ЕГЭ по информатике 2021.
Решить 27 задание из ЕГЭ по информатике очень важно, ведь оно самое трудное, и за него дают, как правило, больше всего вторичных баллов.
Перейдём к практике 27 задания из ЕГЭ по информатике.
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000
Пример организации исходных данных во входном файле:
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Напишем программу на языке программирования Pascal ABC для решения этого 27 задание из Демонстрационного варианта ЕГЭ по информатике.
var f: text; i, sum, min_range, x, y, n: integer; begin assign(f, 'c:\27-A.txt'); reset(f); read(f, n); min_range:=10001; sum:=0; for i:=1 to n do begin read(f, x); read(f, y); if x>y then sum:=sum+x else sum:=sum+y; if (abs(x-y) < min_range) and (abs(x-y) mod 3 <> 0) then min_range := abs(x-y); end; if sum mod 3 <> 0 then Writeln(sum) else Writeln(sum-min_range); end.
В начале считаем левый столбик чисел в массив m, а правый столбик в массив k.
Найдём максимальную сумму в переменную sum. В переменной min_range мы будем хранить минимальную разницу между парой чисел, которая НЕ делится на 3.
Идея задачи следующая: Если максимальная сумма делится на 3, то мы должны отнять переменную min_range от максимальной суммы. Это означает, что мы заменили какой-то элемент суммы. При этом новое значение точно не будет делиться на 3, ведь min_range - Не делится на 3! Плюс min_range - это минимальная разница между числами, а значит, сумма будет максимально возможной.
Не забудьте заменить при обработке файла 27-A.txt значение для константы n на 20.
Решим ещё одну примерную задачу из 27 задания ЕГЭ по информатике.
Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй — нечётной. Определите минимально возможную сумму всех чисел в третьей группе.
Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Для указанных данных искомая сумма равна 11, она соответствует такому распределению чисел по группам: (2, 8, 7), (3, 12, 9), (1, 4, 6).
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Источник: https://inf-ege.sdamgia.ru/
Запрограммируем задачу на языке программирования Pascal ABC.
var f: text; i, n, sum1, sum2, sum3, min_range, min, x, y, z: integer; begin assign(f, 'c:\27-B.txt'); reset(f); read(f, n); sum1:=0; sum2:=0; sum3:=0; min_range:=10001; for i:=1 to n do begin read(f, x); read(f, y); read(f, z); min:=x; if y < min then min:=y; if z < min then min:=z; sum1:=sum1+min; if (x=min) then begin sum2 := sum2 + y; sum3 := sum3 + z; end else begin if (y=min) then begin sum2 := sum2 + x; sum3 := sum3 + z; end else begin if (z=min) then begin sum2 := sum2 + x; sum3 := sum3 + y; end; end; end; if (x <> min) and (x-min < min_range) and ((x - min) mod 2 <> 0) then min_range := x-min; if (y <> min) and (y-min < min_range) and ((y - min) mod 2 <> 0) then min_range := y-min; if (z <> min) and (z-min < min_range) and ((z - min) mod 2 <> 0) then min_range := z-min; end; if (sum2 + sum3) mod 2 <> 0 then writeln(sum1) else writeln(sum1 + min_range); end.
В переменную sum1 мы будем суммировать минимальное число из каждой тройки. В переменные sum2 и sum3 суммируем оставшееся числа из тройки (Порядок будет не важен). В переменной min_range получим минимальную разницу между минимальными значениями и оставшимися числами из каждой тройки, причём, эта разница должна быть нечётная.
Ключевой момент: Если сумма одного столбца будет чётной, а второго столбца - нечётной, то сумма этих двух столбцов будет нечётной.
Пример: 5+8=13, 13+4=17 и т.д. Наоборот: 4+6=10, 3+3=6.
Если у нас такая ситуация будет, тогда достаточно распечатать переменную sum1 (Т.е. тот столбец, где находятся минимальные числа).
Если ситуация будет другая, то достаточно заменить числа в той паре, которая дала нам переменную min_range. Тогда сумма в sum1 возрастёт на значение min_range.
Т.к. значение переменной min_range является нечётным, то после замены, sum2+sum3 - будет нечётной, что означает, что одно значение будет чётным, а другое нечётное.
Рассмотрим задачу с популярного сайта по информатике К.Ю. Полякова.
(№ 2683) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел НЕ оканчивалась на 5 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
Для указанных входных данных значением искомой суммы должно быть число 44.
Источник: https://kpolyakov.spb.ru/
Задача похоже на демонстрационный вариант из ЕГЭ по информатике 2021.
var f: text; i, sum, min_range, x, y, n: integer; begin assign(f, 'c:\27-23b.txt'); reset(f); read(f, n); min_range:=10001; sum:=0; for i:=1 to n do begin read(f, x); read(f, y); if x>y then sum:=sum+x else sum:=sum+y; if (abs(x-y) < min_range) and (abs(x-y) mod 10 <> 0) then min_range := abs(x-y); end; if sum mod 10 <> 5 then Writeln(sum) else Writeln(sum-min_range); end.
Теперь мы ищем минимальную разницу между числами, которая не оканчивается на 0! И кладём её в переменную min_range. Если сумма наибольших чисел оканчивается на 5, то мы вычитаем из этой суммы переменную min_range, и тогда точно сумма не будет оканчиваться на 5. Т.к. в переменной min_range значение минимальное из всех возможных, значит, сумма останется максимальной.
