Решение задания № 27 на ЕГЭ
Предисловие
Двадцать седьмая задача – последняя в кодификаторе. Она представляет проблему для многих учащихся, т. к. требует серьезного аналитического подхода для получения наивысшего балла (четырех баллов). Можно выбрать более легкое решение – заполнить массив из 10000 элементов или создать серию циклов, но за такое решение можно максимально получить лишь два первичных балла из четырех. К сожалению, это может быть недопустимо для некоторых экзаменуемых, т. к. по шкале перевода из первичных баллов во вторичные это будет 6 баллов (и максимальный балл за экзаменационную работу составит 94 балла по стобалльной шкале). Поэтому предлагаю сразу же приступить к решению задач. В этой статье будут решены 3 таких задачи, с 2017 по 2019 год.
Начнем с наиболее актуального – 2019 год.
Источник: Демонстрационная версия ЕГЭ-2019 по Информатике
1. На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.
Пример входных данных:
|
7 |
58 |
2 |
3 |
5 |
4 |
1 |
29 |
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение. Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58·4, 58·1, 58·29, 2·1, 2·29, 3·29. Из них на 29 делятся 5 произведений. Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную только
по времени, – 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от
другой, итоговой станет боL9;льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Для того, чтобы задача была оптимальна по быстродействию, не должен использоваться вложенный цикл. Чтобы задача удовлетворяла ограничению по памяти, в решении нельзя использовать массив большой размерности.
Заметим, что в условии задачи есть некоторое противоречие: «В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000)». Если количество чисел будет равным «4», то наибольшее расстояние между ними будет равно 3. Следовательно, при N=4, нет решений. Таким образом, количество чисел должно исключать вариант с четырьмя: N (4 < N ≤ 1000).
И хочется обратить внимание на еще одну особенность: выпишем все различные пары элементов, чтобы их произведение было кратно 29 и расстояние между ними было не меньше, чем 4:
|
1 |
2 |
3 |
4 |
5 |
6 |
|
58*4 |
58*1 |
58*29 |
29*3 |
29*2 |
29*7 |
Мне одному кажется, что в количестве элементов допущена ошибка?
Заметим, что 29 – это простое число. Сначала узнаем количество чисел N. Создадим динамический массив, размерностью 4. И присвоим значения элементов этого массива введенные числа с первого по четвертое. Далее будем проверять (с 5 по N-е число), делится ли первое число на 29 без остатка. Если да, то будем увеличивать счетчик количества данных чисел. Потом нужно узнать значение следующего числа последовательности. Если оно делится на 29 без остатка, то будем увеличивать счетчик с ответом (учтем расстояние и смещение по порядковому номеру). Добавим пары из первого условия к ответу. Сделаем в массиве сдвиг на 1 число влево. И присвоим значение последнего элемента массива следующего элемента последовательности. Таким образом будет подсчитано количество пар элементов, произведение которых кратно 29.
program theamountofcouplesofnumbersmod29;
const
s=4;
var
a:array[1..s]of integer;
N, InputNumber, FirstIndex, SecondIndex, amount, mod29equal0:integer;
begin
mod29equal0 := 0;
amount := 0;
writeln('Введите количество чисел N = ');
readln(N);
for FirstIndex :=1 to s do
begin
writeln('Введите число = ');
readln (a[FirstIndex]);
end;
for FirstIndex := s+1 to N do
begin
if a[1] mod 29 = 0 then
mod29equal0 := mod29equal0 + 1;
writeln('Введите число = ');
readln(InputNumber);
if InputNumber mod 29 = 0 then
amount := amount + FirstIndex – s
//Если введенное число делится на 29, то образует пары со
//всеми предыдущими числами, кроме последних S (тождественно 4)
else
amount := amount + mod29equal0;
//Если введенное число не делится на 29, то предыдущие числа, //которые делятся на 29, образуют с ним пары
for SecondIndex := 1 to s - 1 do
a[SecondIndex] := a[SecondIndex + 1];
a[s] := InputNumber;
end;
writeln(amount)
end.
Источник: Демонстрационная версия ЕГЭ-2018 по Информатике
2. На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
Пример входных данных: 4 2 6 13 39
Пример выходных данных для приведённого выше примера входных данных: 4
Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234). Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную только по времени – 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Выпишем все различные пары элементов, чтобы их произведение было кратно 26:
|
1 |
2 |
3 |
4 |
5 |
6 |
|
4*13 |
2*13 |
6*13 |
4*39 |
2*39 |
6*39 |
Может быть, я не прав, но их должно быть 6, а не 4 для этих данных.
Сначала узнаем количество чисел, установим три счетчика – первый будет считать количество чисел, кратных 2 {2, 4, 6, 8,...}, второй – количество чисел, кратных 13 {13, 26, 39, 52,...}, третий – количество чисел, кратных и 2, и 13 одновременно {26, 52, 78, 104,…}. Будем запрашивать все числа последовательности. Теперь заметим, что возможны три различных случая. Если в последовательности есть лишь одно число, кратное, и 2, и 13 одновременно, то количество пар = количество всех чисел N – 1 + (количество чисел кратных 2)*(количество чисел кратных 13). Если в последовательности более 1 числа, кратного и 2, и 13, то количество пар = считается, как сумма арифметической прогрессии с первым членом N-1, разностью -1 и x = количество чисел кратных и 2, и 13 + (количество чисел кратных 2)*(количество чисел кратных 13). Если же в последовательности нет ни одного числа, кратного и 2, и 13, то количество пар, кратных 26 = (количество чисел кратных 2)*(количество чисел кратных 13).
program countingofcouplesmod26;
var
Index, IndexHelper, N, InputNumber, amountmod2, amountmod13, amountmodboth213: integer;
begin
writeln('Введите количество чисел N = ');
readln(N);
amountmod2:=0;
amountmod13:=0;
amountmodboth213:=0;
for Index:=1 to N do
begin
writeln('Введите число = ');
readln(InputNumber);
if (InputNumber mod 2 = 0) and (InputNumber mod 13 <> 0) then
amountmod2 := amountmod2 + 1;
if (InputNumber mod 13 = 0) and (InputNumber mod 2 <> 0) then
amountmod13 := amountmod13 + 1;
if (InputNumber mod 13 = 0) and (InputNumber mod 2 = 0) then
amountmodboth213 := amountmodboth213 + 1;
end;
if amountmodboth213 = 1 then
writeln(N - 1 + amountmod2*amountmod13)
else if amountmodboth213 > 1 then
writeln((2*N-amountmodboth213-1)*amountmodboth213/2 + amountmod2*amountmod13)
else
writeln(amountmod2*amountmod13);
end.
Источник: Демонстрационная версия ЕГЭ-2017 по Информатике
3. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения. Максимальная оценка за правильную программу – 2 балла.
Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Максимальная оценка за правильную программу, эффективную по времени и памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла. Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя). НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ. Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).
Входные данные Для варианта А на вход программе подаётся шесть строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта А: 1 3 5 12 6 9 5 4 3 3 1 1
Для варианта Б на вход программе в первой строке подаётся количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта Б:
6
1 3
5 12
6 9
5 4
3 3
1 1
Пример выходных данных для приведённых выше примеров входных данных: 32
Выбираем вариант Б.
Отметим первую особенность. Минимальное число последовательности – 1, максимальное – 10000. Следовательно, максимальная разница между ними = 9999.
Очевидно, что будем суммировать максимальные числа в каждой паре, но сложность возникнет в том, чтобы конечная сумма не была кратна 3. Для этого будем запоминать минимальную разницу между введенными числами, сначала присвоив первое значение = 10000 (т. к. в абзаце выше убедились, что больше она просто быть не может), а далее присваивая минимальное не кратное трем среди разницы в числах пары. Это делается для того, чтобы в случае если конечное число оказалось равным трем, «поменять» числа местами и получить максимальную сумму. Таким образом получим требуемое число.
program Summaryofnumbersnotmod3;
var
N, maximum, minimum, FirstNumber, SecondNumber, Summary, DeltaMinMax, index:integer;
begin
summary := 0;
DeltaMinMax:=10000;
writeln('Введите колиечество пар элементов = ');
readln(N);
for index:=1 to N do
begin
writeln('Введите числа = ');
readln(FirstNumber);
readln(SecondNumber);
if FirstNumber > SecondNumber then
begin
maximum := FirstNumber;
minimum := SecondNumber;
end
else
begin
maximum := SecondNumber;
minimum := FirstNumber;
end;
if ((maximum - minimum) mod 3 <> 0) and (maximum - minimum < DeltaMinMax) then
DeltaMinMax := maximum - minimum;
Summary := Summary + maximum;
end;
if Summary mod 3 = 0 then
begin
if DeltaMinMax > 10000 then
writeln('Ошибка вычислений')
else
Summary := Summary - DeltaMinMax;
end;
writeln(Summary);
end.
Заключение
Типов двадцать седьмых задач очень много: там есть и геометрические фигуры, и координатная плоскость. Поэтому будет написана вторая статья по теме. Данные алгоритмы не относятся к самым тривиальным, поэтому их составление представляет собой определенный интерес для аудитории разных возрастов.
