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

Задачи из рубрикатора

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

Условие задачи  
ID 7140: Максимальное произведение по условию
Максимальное произведение по условию
Темы: ЕГЭ - вычислительные задачи   

По каналу связи передаются данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух. Признаком конца данных считается число 0. После данных передаётся контрольное значение. Оно равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Напишите эффективную, в том числе по памяти, программу, которая будет моделировать процесс приёма данных. Программа должна ввести все числа и контрольное значение, и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.
Перед текстом программы кратко опишите алгоритм решения задачи, укажите используемый язык программирования и его версию.

Входные данные
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.

Выходные данные
Программа должна вывести отчёт по форме, приведённой ниже в примере.
 

 

Примеры
Входные данные Выходные данные
1 6
7
8
9
0
64
input: 4
reference value: 64
calculated value: 63
values false

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

ID 30694: НОД для пары чисел
НОД для пары чисел
Темы: ЕГЭ - вычислительные задачи   

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. 

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

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

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.


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

 

Входные данные
Выведите ответ на задачу

 

 

Примеры
Входные данные Выходные данные
1
6
1 3 
5 15  
6 9  
5 4  
3 3  
36 40  
3 1

ID 30695: Выборка чисел из тройки для максимальной суммы, не кратной 4
Выборка чисел из тройки для максимальной суммы, не кратной 4
Темы: ЕГЭ - вычислительные задачи   

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

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


Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000. 

Выходные данные
Выведите ответ на задачу

 

 

Примеры
Входные данные Выходные данные
1
6
1 3 2
5 12 12
6 8 12
5 4 12
3 3 12
1 1 13
63


 

ID 30698: Спутник "Восход" -2
Спутник "Восход" -2
Темы: ЕГЭ - вычислительные задачи   

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


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

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


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

 

 

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


 

ID 30767: Максимальная сумма смежных элементов
Максимальная сумма смежных элементов
Темы: Динамическое программирование    ЕГЭ - вычислительные задачи   

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

 

Примеры
Входные данные Выходные данные
1
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% тестов.

 

ID 33210: Максимальная четная сумма
Максимальная четная сумма
Темы: ЕГЭ - вычислительные задачи   

На вход программы поступает последовательность из N целых чисел (\(N>1\)). Необходимо найти такое множество чисел из данного ряда, что их сумма будет четной и максимальной. Количество чисел в множестве k (\(1 <= k <= N\)).


Входные данные
В первой строке входных данных задается количество чисел N (\(2 <= N <= 10000\)). В каждой из последующих N строк записано одно целое число в диапазоне от –100 до 100. 

Выходные данные
Вывести одно число: максимальную четную сумму. 
 

 

Примеры
Входные данные Выходные данные
1 8
-5
-13
15
-9
-3
-6
-10
-8
12

ID 33458: Сумма кратная трем, произведение - пяти
Сумма кратная трем, произведение - пяти
Темы: ЕГЭ - вычислительные задачи   

На вход программы поступает последовательность из 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)}

ID 33250: Пара с минимальной суммой
Пара с минимальной суммой
Темы: ЕГЭ - вычислительные задачи   

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

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

Выходные данные
В качестве результата программа должна вывести два числа: найденную минимальную сумму и количество пар с суммой равной минимальной.
 

 

Примеры
Входные данные Выходные данные
1
10 
1 2 3 1 2 3 1 2 3 1
2 6
2
2 2 1 2 2
3 4

ID 29518: Длины чисел
Длины чисел
Темы: ЕГЭ - вычислительные задачи   

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

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

ID 25970: По мотивам ЕГЭ 2017
По мотивам ЕГЭ 2017
Темы: ЕГЭ - вычислительные задачи   

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


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


Выходные данные
Выведите ответ на задачу.
 

 

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

ID 33482: Максимальная сумма пары чисел
Максимальная сумма пары чисел
Темы: ЕГЭ - вычислительные задачи   

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

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

Входные данные
Выведите ответ на задачу.

Примеры
Входные данные Выходные данные
1 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.
 

ID 33483: Максимальная сумма произвольной пары
Максимальная сумма произвольной пары
Темы: ЕГЭ - вычислительные задачи   

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


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

Входные данные
В качестве результата, программа должна вывести одно число, количество найденных пар.
 
Примеры
Входные данные Выходные данные
1 7
1
0
2
0
5
0
8
9

ID 30697: Подсчет пар с суммой кратной 12
Подсчет пар с суммой кратной 12
Темы: ЕГЭ - вычислительные задачи   

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

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

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

Выходные данные
Выведите ответ на задачу

 

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

ID 30693: Цифры в числах
Цифры в числах
Темы: ЕГЭ - вычислительные задачи   

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

Входные данные
На вход программе подаётся натуральное число N (\(N <= 10000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

Выходные данные
Вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления.
 

 

Примеры
Входные данные Выходные данные
1
456
20
3452
6 3 0 5 4 2

ID 22029: Набор точек на плоскости
Набор точек на плоскости
Темы: ЕГЭ - вычислительные задачи   

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

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

Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.

Пример входных данных:
6
0 0
2 0
3 3
5 5 
-6 -6
1 2
Пример выходных данных для приведенного выше примера входных данных:
6

ID 29496: По мотивам ЕГЭ 2018 - 1
По мотивам ЕГЭ 2018 - 1
Темы: ЕГЭ - вычислительные задачи   

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов  последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
 
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= N <= 100000\)). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

Выходные данные
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
 

 

Примеры
Входные данные Выходные данные
1
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).
 

ID 30769: По мотивам ЕГЭ 2018 - 2
По мотивам ЕГЭ 2018 - 2
Темы: ЕГЭ - вычислительные задачи   

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

 

Примеры
Входные данные Выходные данные
1 6
29
7
8
29
4
5
3

ID 23454: Площадь невырожденного треугольника - 2
Площадь невырожденного треугольника - 2
Темы: ЕГЭ - вычислительные задачи   

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

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


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

 

Примеры
Входные данные Выходные данные
1
3
6 6
-8 8
9 7
48

ID 30768: Максимальное произведение смежных элементов
Максимальное произведение смежных элементов
Темы: ЕГЭ - вычислительные задачи   

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

 

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

ID 25979: Выборка чисел для максимальной суммы, кратной 4
Выборка чисел для максимальной суммы, кратной 4
Темы: ЕГЭ - вычислительные задачи   

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


Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Выходные данные
Выведите ответ на задачу

 

 

Примеры
Входные данные Выходные данные
1

6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12

88

ID 27172: Площадь невырожденного треугольника
Площадь невырожденного треугольника
Темы: ЕГЭ - вычислительные задачи   

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

ID 7141: Радиотелескоп
Радиотелескоп
Темы: ЕГЭ - вычислительные задачи   

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

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

Выходные данные
Программа должна вывести в порядке возрастания номера сигналов, произведение которых будет характеризовать данную серию. Нумерация сигналов ведется с единицы.
 

 

Примеры
Входные данные Выходные данные
1
12.3
0.1
100.2 
0.3
1.4
1 3 5

 

ID 24670: По мотивам ЕГЭ 2016 - 2
По мотивам ЕГЭ 2016 - 2
Темы: ЕГЭ - вычислительные задачи   

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

 

Примеры
Входные данные Выходные данные
1 6
10 10
1 7
2 5
4 5
6 9
13 13
37

ID 29497: Дед мороз, снегурочка и конфеты
Дед мороз, снегурочка и конфеты
Темы: ЕГЭ - вычислительные задачи   

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. 

Дед Мороз и Снегурочка – волшебники, поэтому число утренников N, на которых они побывали, может быть очень большим. 

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

Программа будет считаться эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программа будет считаться эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.

 
Входные данные
В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: D – количество пришедших на очередной утренник детей; K – количество конфет в мешке Деда Мороза на этом утреннике. 

Гарантируется выполнение следующих соотношений: \(1 <= N <= 10000\), \(1 <= D <= 100\) (для каждого D), \(D <= K <= 1000\) (для каждой пары D, K)

Выходные данные
Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.
 

 

Примеры
Входные данные Выходные данные
1
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
31

ID 37994: Последняя цифра - наибольшая, но сумма минимальна
Последняя цифра - наибольшая, но сумма минимальна
Темы: ЕГЭ - вычислительные задачи   

Дана последовательность, которая состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел имела такую же последнюю цифру, как наибольшая возможная, и при этом была минимальной возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — минимальную возможную сумму, соответствующую условиям задачи.
Входные данные: в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.
Пример входного файла:

6
2 7
1 8
10 2
6 4
3 3
3 10
Для указанных данных максимальная сумма – 44 (7 + 8 + 10 + 6 + 3 + 10), её последняя цифра 4. Искомая минимальная сумма, имеющая последнюю цифру 4, равна 24, она соответствует выбору чисел (2 + 8 + 2 + 6 + 3 + 3).
Выходные данные:  искомое значение.
 

ID 25980: Максимальная сумма, не делящаяся на 4
Максимальная сумма, не делящаяся на 4
Темы: ЕГЭ - вычислительные задачи   

На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4. 

В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные
На вход программе подаётся натуральное число N (\(N <= 1000\)), а затем N натуральных чисел, каждое из которых не превышает 10000. 
 
Выходные данные
Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму. 
 

 

Примеры
Входные данные Выходные данные
1
1
2
1
2 3

ID 27037: Не равные максимальному
Не равные максимальному
Темы: ЕГЭ - вычислительные задачи   

Дан набор из N целых чисел. Необходимо определить количество элементов, имеющих значения не равные значению максимального элемента из этого набора.

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом N.
 
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= 𝑁 <=100 000\)). В каждой из последующих 𝑁 строк записано одно целое число, не превышающее по модулю 1000.
 
Выходные данные
Выведите одно число - ответ на задачу
 

 

Примеры
Входные данные Выходные данные
1
5
7
-5
9
8
9
3

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

ID 30680: Симметричная запись из цифр
Симметричная запись из цифр
Темы: ЕГЭ - вычислительные задачи   

На вход программы поступает последовательность из 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 можно составить симметричную строку

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

ID 30696: Подсчет пар с произведением кратным 6
Подсчет пар с произведением кратным 6
Темы: ЕГЭ - вычислительные задачи   

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых \(1 <= i < j <= N \)и произведение элементов кратно 6. 

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

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

Выходные данные
Ввыведите ответ на задачу

 

 

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

ID 29437: Сигма 2015
Сигма 2015
Темы: ЕГЭ - вычислительные задачи   

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

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

Максимальная оценка за выполнение задания А – 2 балла. 
 

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


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


Выходные данные
Программа должна вывести одно число - описанное в условии произведение, либо 1, если получить такое произведение не удаётся.

 

 

Примеры
Входные данные Выходные данные
1 12
12
45
5
3
1
7
23
21
20
19
18
1
7
18

ID 33295: Сумма чисел в парах
Сумма чисел в парах
Темы: ЕГЭ - вычислительные задачи   

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

Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). 


Входные данные
В каждой строке входных данных  записано одно натуральное число, не превосходящее числа 30000.  Ввод чисел оканчивается нулем.

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

ID 24669: По мотивам ЕГЭ 2016 - 1
По мотивам ЕГЭ 2016 - 1
Темы: ЕГЭ - вычислительные задачи   

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

На вход подается сначала количество пар, затем сами пары.


Входные данные
В первой строке хадается количество пар. В последующих строках - сами пары. Числа по модулю не превышают 30 000.

Выходные данные
Выведите ответ на задачу

 

Примеры
Входные данные Выходные данные
1
6
1 2
4 9
3 5
7 2
4 4
2 2
29

ID 33548: По мотивам ЕГЭ 2019
По мотивам ЕГЭ 2019
Темы: ЕГЭ - вычислительные задачи   

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не менее, чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить максимальную сумму пары чисел кратную 112, при этом первый элемент пары должен быть больше второго (\(a[i] > a[j]\), \(i < j\)).

Входные данные
В первой строке входных данных задаётся количество чисел N (\(5 <= N <= 1000\)). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.


Входные данные
Программа должна вывести в первой строке одно число: максимальную сумму пары элементов, находящихся в последовательности на расстоянии не менее чем 4, в которых сумма элементов кратна 112, а во второй строке – числа, образующие пару, через пробел. Если ни одной подходящей пары нет, нужно вывести одно число –1.
 

Примеры
Входные данные Выходные данные
1 7
119
62
343
50
48
105
274
224
119 105

ID 33238: Сумма кратная трем
Сумма кратная трем
Темы: ЕГЭ - вычислительные задачи   

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

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

Выходные данные 
В качестве результата программа должна вывести одно число: максимальную сумму пары кратную трём с суммой индексов кратной трём или «–1», если такой пары не нашлось.


 

Примеры
Входные данные Выходные данные Комментарий
1
10 
1 2 3 4 5 6 7 8 9 10
18 найденная пара: (a[8]=8; a[10]=10)
2
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)

 

ID 23419: Спутник "Восход"
Спутник "Восход"
Темы: ЕГЭ - вычислительные задачи   

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

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

Задача А (2 балла). 

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

Задача Б (4 балла). 

Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). 

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

Выходные данные
Программа должна вывести одно число – описанное в условии произведение.



Примеры
Входные данные Выходные данные
1
11
12
45
5
3
17
23
21
20
19
12
26
1170

 

ID 25969: 3-ий минимум
3-ий минимум
Темы: ЕГЭ - вычислительные задачи   

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

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

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

 

Примеры
Входные данные Выходные данные
1 5
100
10
100
10
100
#