Подготовка ребёнка к ЕГЭ по информатике. Часть седьмая

03.02.19

Разработка - Математика и алгоритмы

Последний уровень

Решение задания № 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.

 

Заключение

 

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4419    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

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

1 стартмани

09.06.2023    7462    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8839    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7805    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. user1389250 06.04.20 12:45 Сейчас в теме
ТС - идиот. В первом задании
Мне одному кажется, что в количестве элементов допущена ошибка?

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