Вверх

Линия заданий 27, ЕГЭ по информатике

12497. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности - наибольшее число R, удовлетворяющее следующим условиям:

1) R - произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 6.

Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение: ...

Контроль пройден (или - Контроль не пройден)

Перед текстом программы кратко опишите используемый вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:
6
70
17
6
99
997
70
6930

Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 6930
Контроль пройден

Произведение двух чисел делится на 6, если:
- один из сомножителей делится на 6 (второй может быть любым), либо - ни один из сомножителей не делится на 6, причём один из сомножителей делится на 2, а другой - на 3.
Поэтому программа, вычисляющая кодовое число, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:
М2 - самое большое чётное число, не кратное 3;
M3 - самое большое число, кратное 3, но не кратное 2;
M6 - самое большое число, кратное 6;
МAX - самое большое число среди всех элементов последовательности, отличное от М6
(если число М6 встретилось более одного раза и оно же является максимальным, то MAX = M6).
После того как все данные прочитаны, искомое кодовое слово вычисляется как максимум из произведений М6 · MAX и М2 · М3.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы. Допускаются решения, записанные на других языках программирования.

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12497.

12524. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности - наибольшее число В, удовлетворяющее следующим условиям:

1) R - произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 10.

Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение: ...

Контроль пройден (или - Контроль не пройден)

Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:
6
95
17
10
102
957
95
9690

Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 9690
Контроль пройден

Произведение двух чисел делится на 10, если:
- один из сомножителей делится на 10 (второй может быть любым), либо
- ни один из сомножителей не делится на 10, причём один из сомножителей делится на 2, а другой - на 5.
Поэтому программа, вычисляющая кодовое число, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:
М2 - самое большое чётное число, но не кратное 5;
M5 - самое большое число, кратное 5, но не кратное 2;
M10 - самое большое число, кратное 10;
МAX - самое большое число среди всех элементов последовательности, отличное от М10
(если число М10 встретилось более одного раза и оно же является максимальным, то MAX = M10).
После того как все данные прочитаны, искомое кодовое слово вычисляется как максимум из произведений М10 · MAX и М2 · M5.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы. Допускаются решения, записанные на других языках программирования.

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12524.

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

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (5 ⩽ N ⩽ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 5, в которых произведение элементов кратно 11.
Пример входных данных:
8
22
2
3
5
4
6
7
11
Пример выходных данных для приведённого выше примера входных данных:
5

Пояснение. Из восьми заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 22 ⋅ 6, 22 ⋅ 7, 22 ⋅ 11, 2 ⋅ 7, 2 ⋅ 11, 3 ⋅ 11. Из них на 11 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, - 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени, - 8 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, - 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Произведение двух чисел делится на 11, если хотя бы один из сомножителей делится на 11.
При вводе чисел можно подсчитывать количество чисел, кратных 11, не считая 5
последних. Обозначим их n11.
Сами числа, кроме 5 последних, при этом можно не хранить.
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.
Если очередное считанное число делится на 11, то к ответу следует прибавить количество чисел до него, не считая 5 последних (включая считанное).
Если очередное считанное число на 11 не делится, то к ответу следует прибавить n11.
Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на 5 элементов ранее, достаточно хранить только 5 последних элементов или информацию о них.
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12551.

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

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ⩽ N ⩽ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

Пример входных данных:
7
58
2
3
5
4
1
29
Пример выходных данных для приведённого выше примера входных данных:
5

Пояснение. Из семи заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58 ⋅ 4, 58 ⋅ 1, 58 ⋅ 29, 2 ⋅ 1, 2 ⋅ 29, 3 ⋅ 29. Из них на 29 делятся 5 произведений.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, - 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени, - 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, - 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Произведение двух чисел делится на 29, если хотя бы один из сомножителей делится на 29.
При вводе чисел можно подсчитывать количество чисел, кратных 29, не считая 4
последних. Обозначим их n29.
Сами числа, кроме 4 последних, при этом можно не хранить.
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.
Если очередное считанное число делится на 29, то к ответу следует прибавить количество чисел до него, не считая 4 последних (включая считанное).
Если очередное считанное число на 29 не делится, то к ответу следует прибавить n29.
Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на 4 элемента ранее, достаточно хранить только 4 последних элемента или информацию о них.
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12578.

12605. На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i < j и ai > aj
(первый элемент пары больше второго, i и j - порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 111. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2 ⩽ n ⩽ 12000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример входных данных:
6
60
122
61
100
273
50
Пример выходных данных для приведённого выше примера входных данных:
122 100

Пояснение. Из шести заданных чисел можно составить 3 пары, сумма элементов которых делится на m = 111: 60+273, 122+100, 61+50. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз, время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, - 4 балла.
Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, - 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, - 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Сумма ai и aj делится на m, если сумма остатков этих чисел от деления на m равна 0 или m.
Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив r длиной m, изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.

Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если r[m–p] > 0, то сумма a и r[m–p] делится на m, и, при условии r[m–p] > a, эта пара – кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и r[0].

По окончании обработки элемента a необходимо обновить элемент r[p] значением a, если a > r[p].
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12605.

12632. На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i < j и ai > aj, (первый элемент пары больше второго, i и j - порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 109. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2 n 12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример входных данных:
6
60
118
61
100
267
48
Пример выходных данных для приведённого выше примера входных данных:
118 100

Пояснение. Из шести заданных чисел можно составить 3 пары, сумма элементов которых делится на m = 109: 60-267, 118+100, 61+48. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз, время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, - 4 балла.
Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, - 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, - 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла)

Сумма ai и aj делится на m, если сумма остатков этих чисел от деления на m равна 0 или m.Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив r длиной m, изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.

Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если r[m–p] > 0, то сумма a и r[m–p] делится на m, и, при условии r[m–p] > a, эта пара – кандидат для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и r[0].

По окончании обработки элемента a необходимо обновить элемент r[p] значением a, если a > r[p].
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12632.

Для вас приятно генерировать тесты, создавайте их почаще