Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

72. НОД для пары чисел

ЕГЭ - вычислительные задачи

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять, какое значение А встречалось чаще всего. Если несколько значений А встречалось одинаковое наибольшее количество раз, вывести их в порядке убывания.
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.

Входные данные:
На вход программе в первой строке подаётся количество пар N (1 <= N <= 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000. 
 
Ввод Вывод
6
1 3 
5 15  
6 9  
5 4  
3 3  
36 40  
3 1

78. Спутник "Восход" -2

ЕГЭ - вычислительные задачи

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи натуральное число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии количество пар таких показаний прибора, произведение которых кратно 6 и между моментами передачи которых прошло не менее 3 минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Задача А (2 балла). Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться
в массиве, после чего будут проверены все возможные пары элементов.
Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 3. В каждой из следующих N строк задаётся одно натуральное число – очередное показание прибора.
 
Ввод Вывод
5
6
2
4
1
3
3

 
В приведённом наборе из 5 чисел имеются три пары (6, 3), (2, 3) и (6, 1), удовлетворяющих условию задачи.

(с) Д. Ф. Муфаззалов

ЕГЭ - 2017

ЕГЭ - вычислительные задачи

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N и произведение элементов кратно 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи. 

Описание входных и выходных данных 
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Пример входных данных:
5
14
7
7
2
19
Пример выходных данных:
6

Сигма 2015

ЕГЭ - вычислительные задачи

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 100 000. Все числа не превышают 10 000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.\
 
Задача А. Напишите программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары
элементов. Максимальная оценка за выполнение задания А – 2 балла. 
 
Задача Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N
строк задаётся одно положительное целое число – очередное показание прибора.

Пример входных данных:
12 12 45 5 3 1 7 23 21 20 19 18 17
Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.
 
Пример выходных данных для приведённого выше примера входных данных:
18

74. Выборка чисел для максимальной суммы, кратной 4

ЕГЭ - вычислительные задачи

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. 

Входные данные:
На вход программе в первой строке подаётся количество троек N (1 ≤  N ≤  100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
Пример выходных данных для приведённого примера входных данных: 
88
 

90. Максимальное произведение смежных элементов

ЕГЭ - вычислительные задачи

На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальное произведение смежных элементов последовательности. N не превышает 10000, каждый элемент последовательности не превосходит по модулю 100.
 
Ввод Вывод
7
2
3
-2
-3
-1
4
6
72

 
Пояснения: наибольшее произведение можно получить для последовательности -3 -1 4 6.
 

71. Цифры числа в симметричную запись

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N натуральных целых чисел, каждое из которых не больше 1000. Требуется определить, можно ли записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). Если требуемую строку составить невозможно, то программа должна вывести на экран число 0, а если возможно, то вывести число 1.
Входные данные:
На вход программе подаётся натуральное число N (N <= 100000), а затем N натуральных чисел, каждое из которых не превышает 10000.
Пример входных данных:
3
13
22
32
Пример выходных данных для приведённого примера входных данных:
0
Из цифр D, 1, 6, 2, 0 нельзя составить симметричную строку.
Пример входных данных:
4
186
68
171
14
Пример выходных данных для приведённого примера входных данных:
1
Из цифр A, B, 4, 4, A, B, D можно составить симметричную строку

Напишите эффективную по времени и по памяти программу, которая решает поставленную задачу

3-ий минимум

ЕГЭ - вычислительные задачи

От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ "#". Следует учитывать, что количество измерений может быть очень велико.

На вход программе в первой строке подается общее количество N значений измерений.
В каждой из последующих N строк записано целое число. Гарантируется, что N>0, то есть всегда имеется хотя бы одно измерение.

Пример входных данных:
5
100
10
100
10
100

Пример выходных данных для приведенного выше примера входных данных:
#
 

ИН10303

ЕГЭ - вычислительные задачи

На плоскости задано множество точек с целочисленными координатами.Необходимо найти максимально возможную площадь невырожденного (т. е. имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение. Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта. Перед текстом программы кратко опишите алгоритм решения и укажите
язык программирования и его версию.
 
Входные данные
В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.
 
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «No solution».
 
Ввод Вывод
3
6 6
-8 8
9 7
48

75. Подсчет пар с произведением кратным 6

ЕГЭ - вычислительные задачи

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N и произведение элементов кратно 6. Напишите эффективную по времени и по памяти программу для решения этой задачи. 
Описание входных и выходных данных 
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
 
Ввод Вывод
4
7
5
6
12
5

В приведённом наборе из 4 чисел имеются пять пар (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), произведение элементов которых кратно 6.

(c) Д.В. Богданов

ЕГЭ - 2019

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не менее, чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить максимальную сумму пары чисел кратную 112, при этом первый элемент пары должен быть больше второго (a[i] > a[j], i < j).
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (5 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
Программа должна вывести в первой строке одно число: максимальную сумму пары элементов, находящихся в последовательности на расстоянии не менее чем 4, в которых сумма элементов кратна 112, а во второй строке – числа, образующие пару, через пробел. Если ни одной подходящей пары нет, нужно вывести одно число –1.
Входные данные:
7
119
62
343
50
48
105
274
Выходные данные:
224
119 105

20162001-СТ03

ЕГЭ - вычислительные задачи

На плоскости задано множество точек с целочисленными координатами. Необходимо найти минимально возможную площадь невырожденного (т. е.имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести "NO".

 
Напишите эффективную по времени и по используемой памяти программу
для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.

Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа – координаты
очередной точки.
 
Пример входных данных:
3
6 6
-8 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна
напечатать сообщение: «NO».
Пример выходных данных для приведённого выше примера входных данных:
48

94. Максимальная четная сумма

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N целых чисел (N > 1). Необходимо найти такое множество чисел из данного ряда, что их сумма будет четной и максимальной. Количество чисел в множестве k (1 ≤ k ≤ N).
Описание входных и выходных данных.
В первой строке входных данных задается количество чисел N (2 ≤ N ≤ 10000). В каждой из последующих N строк записано одно целое число в диапазоне от –100 до 100. В качестве ответа программа должна вывести одно число: максимальную четную сумму. 
Пример входных данных:
8
-5
-13
15
-9
-3
-6
-10
-8
Пример выходных данных для приведенного выше примера входных данных:
12

52. Дед мороз, снегурочка и конфеты

ЕГЭ - вычислительные задачи

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. Дед Мороз и Снегурочка – волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.
 
Входные данные
В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D – количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений: 1 ≤ N ≤ 10000, 1 ≤ D ≤ 100 (для каждого D), D ≤ K ≤ 1000 (для каждой пары D, K)
 
Выходные данные
Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.
 
Ввод Вывод
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
31

ЕГЭ - 2016 2 вариант

ЕГЭ - вычислительные задачи

Дано N пар чисел. Из каждой пары нужно выбрать одно так, чтобы сумма выбранных чисел была наименьшей из возможных и не делилась на 4. В первой строке вводится число N, не превышаюшее 100 000.
Если таких чисел нет, вывести "no".
На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.
 

Ввод Вывод
6
10 10
1 7
2 5
4 5
6 9
13 13
37

П50 Радиотелескоп

ЕГЭ - вычислительные задачи

Радиотелескоп пытается получать и анализировать сигналы из космоса. Различные шумы переводятся в последовательность вещественные неотрицательные числа, заданные с точностью до 1 знака после десятичной точки. Для того чтобы описывать различные участки космоса, данные, получаемые из одного района, было решено характеризовать числом, равным максимальному произведению, которое можно получить, перемножая значения сигналов, приходящих из этого района. То есть требуется выбрать такое непустое подмножество сигналов (в него может войти как один сигнал, так и все поступившие сигналы), произведение значений у которого будет максимальным. Если таких подмножеств несколько, то выбрать можно любое из них.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя искомое подмножество. Сигналов может быть очень много, но не может быть меньше трех. Все сигналы различны.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подается количество сигналов N. В каждой из последующих N строк записано одно вещественное число с точностью до 1 знака после десятичной точки. Все числа различны.
Пример входных данных:
5
12.3
0.1
100.2
0.3
1.4
Программа должна вывести в порядке возрастания номера сигналов, произведение которых будет характеризовать данную серию. Нумерация сигналов ведется с единицы.
Пример выходных данных для приведенного выше примера входных данных:
1 3 5 

Богданов_1800

ЕГЭ - вычислительные задачи

Дан набор из 𝑁 целых чисел. Необходимо определить количество элементов, имещих значения не равные значению максимального элемента из этого набора.
Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел 𝑁 в 𝑘 раз время работы программы увеличивается не более чем в 𝑘 раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом 𝑁.
 
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел 𝑁 (1 ≤ 𝑁 ≤100 000). В каждой из последующих 𝑁 строк записано одно целое число, не превышающее по модулю 1000.
 
Пример входных данных:
5
7
-5
9
8
9
Пример выходных данных для приведённого выше примера входных данных:
3

В приведённом наборе из 5 чисел имеются три элемента — 7, –5 и 8, значения
которых не равны значению максимального элемента этого набора — 9.

77. Подсчет пар с суммой кратной 12

ЕГЭ - вычислительные задачи

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 < i < j < N и сумма элементов кратна 12. Напишите эффективную по времени и по памяти программу для решения этой задачи. 
Описание входных и выходных данных 
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
 
Ввод Вывод
5
7
5
6
12
24
2

В приведённом наборе из 5 чисел имеются две пары (7, 5) и (12, 24), сумма элементов которых кратна 12.

(с) Д.В. Богданов

96

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность натуральных чисел A. Количество элементов в последовательности больше числа 7. Необходимо определить количество таких пар элементов последовательности Ai и Aj, j  – i > 4, где i и j – номера элементов последовательности, что сумма чисел в каждой из этих пар кратна числу 3.  
Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). 

Описание входных и выходных данных
В каждой строке входных данных  записано одно натуральное число, не превосходящее числа 30000.  Ввод чисел оканчивается нулем. В качестве ответа программа должна вывести одно число – количество пар элементов, удовлетворяющих условию.
 
 
Ввод Ввод
10
12
81
2
7
33
99
21
11
121
10
0
6
 

70. Цифры в числах

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N натуральных чисел, каждое из которых не больше 1000. Требуется вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления. Если какие-то цифры встречаются одинаковое число раз, они выводятся в порядке убывания. 

Входные данные:
На вход программе подаётся натуральное число N (N < 10000), а затем N натуральных чисел, каждое из которых не превышает 10000. 
 
Ввод Вывод
456
20
3452
6 3 0 5 4 2

Демо 2018

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов  последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
 
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих 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).
 

98

ЕГЭ - вычислительные задачи

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

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.

В качестве результата программа должна вывести два числа: найденную минимальную сумму и количество пар с суммой равной минимальной.
Ввод Вывод
10 
1 2 3 1 2 3 1 2 3 1
2 6
2 2 1 2 2
 
3 4

97 Сумма кратная трем, произведение - пяти

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, сумма которых кратна 3, а произведение кратно 5. На вход алгоритма подается число N и далее сами N чисел.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000. В качестве результата программа должна вывести одно число: количество найденных пар.
Пример входных данных №1:
10
1
2
3
4
5
6
7
8
9
10
Выходные данных для приведенного выше примера:
6
Найденные пары для примера : {(1;5) (2;10) (4;5) (5;7) (5;10) (8;10)}
Пример входных данных №2:
23
71 33 87 66 37 97 91 30 52 19 56 85 81 27 25 35 47 72 85 87 98 88 41
Выходные данных для приведенного выше примера:
31
(А.А. Богданов, Danov1802 №27-4)

76. Длины чисел

ЕГЭ - вычислительные задачи

Назовём длиной числа количество цифр в его десятичной записи. Например, длина числа 2017 равна 4, а длина числа 7 равна 1. Дан набор из N целых неотрицательных чисел, каждое из которых меньше 109.
Необходимо определить, числа какой длины реже всего (но не менее одного раза) встречаются в данном наборе и сколько в нём чисел этой длины. Если числа разной длины встречаются одинаково часто (и реже, чем числа любой другой длины), нужно выбрать меньшую длину.
Напишите эффективную по времени и по памяти программу для решения этой задачи.

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно неотрицательное число, не превышающее 109.
Пример входных данных:
5
12
417
125
327
4801
Пример выходных данных для приведённого выше примера входных данных:
2 1
В данном наборе реже всего (по 1 разу) встречаются числа длины 2 и 4.
 

46. Набор точек на плоскости

ЕГЭ - вычислительные задачи

На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна из сторон которого лежит на оси OX. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. 
В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа – сначала координата х, затем координата у очередной точки.
Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.
Пример входных данных:
6
0 0
2 0
3 3
5 5 
-6 -6
1 2
Пример выходных данных для приведенного выше примера входных данных:
6

63. Спутник "Восход"

ЕГЭ - вычислительные задачи

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний прибора максимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 9 минут. Если получить такое произведение не удаётся, ответ считается равным –1. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.
Задача А (2 балла). Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться
в массиве, после чего будут проверены все возможные пары элементов.
Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих
характеристик).
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 9. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередное показание прибора.
Пример входных данных:
11
12
45
5
3
17
23
21
20
19
12
26
Программа должна вывести одно число – описанное в условии произведение.
Пример выходных данных для приведённого выше примера входных данных: 
1170
 

ЕГЭ - 2016 1-ый вариант

ЕГЭ - вычислительные задачи

Дано N пар чисел. Из каждой пары нужно выбрать одно число так, чтобы сумма выбранных чисел была наибольшей из возможных и не делилась на 4. В первой строке вводится число N, не превышает  100 000.
Если таких чисел нет, вывести "no".
На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.
 

Ввод Вывод
6
1 2
4 9
3 5
7 2
4 4
2 2
 
29

66. Максимальная сумма, не делящаяся на 4

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4. В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Входные данные:
На вход программе подаётся натуральное число N (N ≤ 1000), а затем N натуральных чисел, каждое из которых не превышает 10000. 
Пример входных данных: 
1
2
1
Выходные данные:
Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму. 
Пример выходных данных для приведённого примера входных данных: 
2 3
 

51. Максимальное произведение по условию

ЕГЭ - вычислительные задачи

По каналу связи передаются данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух, признаком конца данных считается число 0. После данных передаётся контрольное значение. Оно равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Напишите эффективную, в том числе по памяти, программу, которая будет моделировать процесс приёма данных. Программа должна ввести все числа и контрольное значение и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.
Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.
Описание входных данных
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.
Описание выходных данных
Программа должна вывести отчёт по форме, приведённой ниже в примере.
Пример входных данных:
6
7
8
9
0
64
Пример выходных данных для приведённого выше примера входных данных:
input: 4
reference value: 64
calculated value: 63
values false    


(в последней строке в зависимости от результата может быть values true)

73. Выборка чисел из тройки для максимальной суммы, не кратной 4

ЕГЭ - вычислительные задачи

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите эффективную программу, решающую поставленную задачу.

Входные данные:
На вход программе в первой строке подаётся количество троек N (1 <= N <= 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000. 
 
Ввод Вывод
6
1 3 2
5 12 12
6 8 12
5 4 12
3 3 12
1 1 13
63

87. Максимальная сумма смежных элементов

Динамическое программирование ЕГЭ - вычислительные задачи

На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальную сумму смежных элементов последовательности. N не превышает 1000000, каждый элемент последовательности не превосходит по модулю 100.
 
Ввод Вывод
9
-2
1
-3
4
-1
2
1
-5
4
6

 
Пояснения: для заданной последовательности чисел (-2 1 -3 4 -1 2 1 -5 4) наибольшую сумму можно получить для смежной последовательности элементов: 4 -1 2 1.
Решение на 2 балла проходит 50% тестов, на 3 балла 75%.
(с) Жуков
 

ЕГЭ - 2018

ЕГЭ - вычислительные задачи

На вход программы подается натуральное число N (N<= 100000), а затем N строк, в в которых по одному целому числу. Необходимо посчитать количество пар чисел, у которых индексы отличаются не меньше чем на три и произведение кратно 29.
 
Ввод Вывод
6
29
7
8
29
4
5
6

Напишите эффективную по памяти и времени программу.

101

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить такую максимальную сумму элементов пары, чтобы суммы элементов пары и их индексов были кратны 3. Если такой суммы не найдется, вывести «–1». Нумерация элементов начинается с 1.

Входные данные 
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
Выходных данные
В качестве результата программа должна вывести одно число: максимальную сумму пары кратную трём с суммой индексов кратной трём или «–1», если такой пары не нашлось
 
Ввод Вывод Примечание
10 
1 2 3 4 5 6 7 8 9 10
18 найденная пара: (8; 10)
23 
36 16 15 15 17 16 14 15 47 22 27 29 35 23 39 29 15 
25 16 35 28 45 26
 
75 пара (a[9]=47; a[21]=28)


Напишите эффективную по памяти и времени программу.
 
(с) А.А. Богданов – Danov1901 №27
 

109

ЕГЭ - вычислительные задачи

На вход программы поступает последовательность из N целых неотрицательных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Найти максимальную сумму произвольной пары ненулевых элементов последовательности. Найденная сумма должна быть кратна трём и между элементами пары должны быть нулевые элементы. Если такой пары нет, следует вывести 0.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000. В качестве результата, программа должна вывести одно число, количество найденных пар.
Входные данные:
7
1
0
2
0
5
0
8
Выходные данные:
9

4002493

ЕГЭ - вычислительные задачи

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

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

В первой строке входных данных задаётся количество чисел N (9 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
 

Ввод Вывод
10
1
3
5
4
6
7
9
10
12
11
14


Пояснение. Из 10 чисел можно составить 3 пары, удовлетворяющие условию. Это будут элементы с индексами 1 и 9, 1 и 10, 2 и 10. Для заданного набора чисел получаем пары (1, 12), (1, 11), (3, 11). Максимальная сумма чисел в этих парах равна 14.

Напишите эффективную по времени и по памяти программу для решения этой задачи.