| Условие задачи | | Прогресс |
|
Темы:
ЕГЭ - вычислительные задачи
На плоскости задано множество точек с целочисленными координатами.Необходимо найти максимально возможную площадь невырожденного (т. е. имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение. Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта. Перед текстом программы кратко опишите алгоритм решения и укажите
язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: максимальную возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «No solution».
| Ввод |
Вывод |
|
3
6 6
-8 8
9 7
|
48 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из N натуральных чисел, каждое из которых не больше 10000. Требуется вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления. Если какие-то цифры встречаются одинаковое число раз, они выводятся в порядке убывания.
Входные данные
На вход программе подаётся натуральное число N (\(N <= 10000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.
Выходные данные
Вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
456
20
3452
|
6 3 0 5 4 2 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Назовём длиной числа количество цифр в его десятичной записи. Например, длина числа 2017 равна 4, а длина числа 7 равна 1. Дан набор из N целых неотрицательных чисел, каждое из которых меньше 109.
Необходимо определить, числа какой длины реже всего (но не менее одного раза) встречаются в данном наборе и сколько в нём чисел этой длины. Если числа разной длины встречаются одинаково часто (и реже, чем числа любой другой длины), нужно выбрать меньшую длину.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (\(1 <= N <= 10000\)). В каждой из последующих N строк записано одно неотрицательное число, не превышающее 109.
Пример входных данных:
5
12
417
125
327
4801
Пример выходных данных для приведённого выше примера входных данных:
2 1
В данном наборе реже всего (по 1 разу) встречаются числа длины 2 и 4.
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна из сторон которого лежит на оси OX. Напишите эффективную по используемой памяти и времени программу, которая будет решать эту задачу. Размер памяти, которую использует программа, не должен зависеть от длины переданной последовательности чисел.
В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа – сначала координата х, затем координата у очередной точки.
Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.
Пример входных данных:
6
0 0
2 0
3 3
5 5
-6 -6
1 2
Пример выходных данных для приведенного выше примера входных данных:
6
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 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 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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 можно составить симметричную строку
Напишите эффективную по времени и по памяти программу, которая решает поставленную задачу.
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний прибора максимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 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 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На плоскости задано множество точек с целочисленными координатами. Необходимо найти минимально возможную площадь невырожденного (т. е. имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести "NO".
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения, укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа – координаты очередной точки.
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «NO».
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
6 6
-8 8
9 7
|
48 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ "#". Следует учитывать, что количество измерений может быть очень велико.
На вход программе в первой строке подается общее количество N значений измерений.
В каждой из последующих N строк записано целое число. Гарантируется, что \(N>0\), то есть всегда имеется хотя бы одно измерение.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
100
10
100
10
100 |
# |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4.
В результате программа должна вывести количество выбранных чисел и их сумму. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Входные данные
На вход программе подаётся натуральное число N (\(N <= 1000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.
Выходные данные
Программа должна вывести два числа: сначала количество выбранных чисел, а затем их сумму.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1
2
1
|
2 3 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Дан набор из N целых чисел. Необходимо определить количество элементов, имеющих значения не равные значению максимального элемента из этого набора.
Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом N.
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= 𝑁 <=100 000\)). В каждой из последующих 𝑁 строк записано одно целое число, не превышающее по модулю 1000.
Выходные данные
Выведите одно число - ответ на задачу
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
7
-5
9
8
9
|
3 |
В приведённом наборе из 5 чисел имеются три элемента — 7, –5 и 8, значения которых не равны значению максимального элемента этого набора — 9.
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Радиотелескоп пытается получать и анализировать сигналы из космоса. Различные шумы переводятся в последовательность вещественного неотрицательного числа, заданного с точностью до 1 знака после десятичной точки. Для того, чтобы описывать различные участки космоса, данные, получаемые из одного района, было решено характеризовать числом, равным максимальному произведению, которое можно получить, перемножая значения сигналов, приходящих из этого района. То есть требуется выбрать такое непустое подмножество сигналов (в него может войти как один сигнал, так и все поступившие сигналы), произведение значений у которого будет максимальным. Если таких подмножеств несколько, то выбрать можно любое из них.
Напишите эффективную, в том числе по используемой памяти, программу, которая будет обрабатывать результаты эксперимента, находя искомое подмножество. Сигналов может быть очень много, но не может быть меньше трех. Все сигналы различны.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
Входные данные
На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно вещественное число с точностью до 1 знака после десятичной точки. Все числа различны.
Выходные данные
Программа должна вывести в порядке возрастания номера сигналов, произведение которых будет характеризовать данную серию. Нумерация сигналов ведется с единицы.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
12.3
0.1
100.2
0.3
1.4 |
1 3 5 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
По каналу связи передаются данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух. Признаком конца данных считается число 0. После данных передаётся контрольное значение. Оно равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Напишите эффективную, в том числе по памяти, программу, которая будет моделировать процесс приёма данных. Программа должна ввести все числа и контрольное значение, и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.
Перед текстом программы кратко опишите алгоритм решения задачи, укажите используемый язык программирования и его версию.
Входные данные
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.
Выходные данные
Программа должна вывести отчёт по форме, приведённой ниже в примере.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
7
8
9
0
64 |
input: 4
reference value: 64
calculated value: 63
values false |
В последней строке в зависимости от результата может быть values true
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 100 000. Все числа не превышают 10 000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным -1.
Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N>6\). В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
Выходные данные
Программа должна вывести одно число - описанное в условии произведение, либо -1, если получить такое произведение не удаётся.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
12
45
5
3
1
7
23
21
20
19
18
1
7 |
18 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель.
Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять, какое значение А встречалось чаще всего. Если несколько значений А встречается одинаковое наибольшее количество раз, вывести их в порядке убывания.
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел 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 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел была кратна 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 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не была кратна 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 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи натуральное число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии количество пар таких показаний прибора, произведение которых кратно 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), удовлетворяющих условию задачи.
| |
![]()
|
|
Темы:
Динамическое программирование
ЕГЭ - вычислительные задачи
На вход программы подается натуральное число 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% тестов.
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальное произведение смежных элементов последовательности. N не превышает 10000, каждый элемент последовательности не превосходит по модулю 100.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
2
3
-2
-3
-1
4
6
|
72 |
Пояснения: наибольшее произведение можно получить для последовательности -3 -1 4 6.
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Дан набор из 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.
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Дан набор из 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.
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Дано N пар чисел. Из каждой пары нужно выбрать одно число так, чтобы сумма выбранных чисел была наибольшей из возможных и не делилась на 4. В первой строке вводится число N, не превышает 100 000.
Если таких чисел нет, вывести "NO".
На вход подается сначала количество пар, затем сами пары.
Входные данные
В первой строке задается количество пар. В последующих строках - сами пары. Числа по модулю не превышают 30 000.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
1 2
4 9
3 5
7 2
4 4
2 2
|
29 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Дано N пар чисел. Из каждой пары нужно выбрать одно так, чтобы сумма выбранных чисел была наименьшей из возможных и не делилась на 4. В первой строке вводится число N, не превышающее 100 000.
Если таких чисел нет, вывести "no".
На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
10 10
1 7
2 5
4 5
6 9
13 13 |
37 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность натуральных чисел 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 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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)}
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен).
Необходимо определить минимальную сумму произвольной пары чисел и количество пар с суммой равной минимальной.
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
Выходные данные
В качестве результата программа должна вывести два числа: найденную минимальную сумму и количество пар с суммой равной минимальной.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10
1
2
3
1
2
3
1
2
3
1
|
2 6 |
| 2 |
5
2
2
1
2
2
|
3 4 |
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых \(1 <= i < j <= N\) и произведение элементов кратно 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
14
7
7
2
19 |
6 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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).
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы подается натуральное число N ( \(N<= 100000\)), а затем N строк, в в которых по одному целому числу. Необходимо посчитать количество пар чисел, у которых индексы отличаются не меньше чем на три и произведение кратно 29.
Напишите эффективную по памяти и времени программу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
29
7
8
29
4
5 |
3 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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) |
Примечание: в примерах элементы массива располагаются в одну строчку для экономии места и улучшения читабельности. В самих тестах к задаче все эелементы расположены по одному числу в строке.
| |
![]()
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из N целых неотрицательных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Найти максимальную сумму произвольной пары ненулевых элементов последовательности. Найденная сумма должна быть кратна трём и между элементами пары должны быть нулевые элементы. Если такой пары нет, следует вывести 0.
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 10000.
Входные данные
В качестве результата, программа должна вывести одно число, количество найденных пар.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
1
0
2
0
5
0
8 |
9 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 8 друг от друга (разница в индексах элементов должна быть 8 или более). Необходимо определить максимальную сумму такой пары.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Входные данные
В первой строке входных данных задаётся количество чисел N (\(9 <= N <= 100000\)). В каждой из последующих 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.
| |
![]()
|
|
Темы:
Остатки
ЕГЭ - вычислительные задачи
У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит Ai количество конфет. Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- Al + Al+1 + ... + Ar делится на M.
Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=105) и M (2<=M<=109). Вторая строка содержит N чисел Ai (1<=Ai<=109, 1<=i<=N).
Выходные данные
Выведите количество пар (l, r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 2
4 1 5 |
3 |
| 2 |
13 17
29 7 5 7 9 51 7 13 8 55 42 9 81 |
6 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1<= N <= 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
ID 39248.
1
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 109. Рассматриваются все её непрерывные подпоследовательности, в которых количество чётных чисел кратно K = 8. Найдите наибольшую сумму такой подпоследовательности.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.
Пример организации исходных данных во входном файле (для К=4):
6
9
16
4
12
10
18
В этом наборе можно выбрать последовательности 9+16+4+12+10 (сумма 51) и 4+12+10+18 (сумма 44).
Ответ (для K = 4): 51.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
ID 39250.
2
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 109. Рассматриваются все её непрерывные подпоследовательности, в которых количество нечётных чисел кратно K = 7. Найдите наибольшую сумму такой подпоследовательности.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.
Пример организации исходных данных во входном файле (для К=4):
6
8
17
3
13
11
21
В этом наборе можно выбрать последовательности 8+17+3+13+11 (сумма 52) и 3+13+11+21 (сумма 48).
Ответ (для K = 4): 52.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
ID 39269.
3
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из N чисел. Известно, что сумма всех чисел последовательности не превышает 109. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратно K = 11. Найдите наибольшую сумму такой подпоследовательности.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 <= N <= 1 000 000). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.
Пример организации исходных данных во входном файле (для К=3):
6
-1
2
3
-5
18
12
В этом наборе можно выбрать следующие подпоследовательности, с количеством положительных элементов кратных K=3:
-1 + 2 + 3 + (-5) + 18 = 17;
2 + 3 + (-5) + 18 = 18;
3 + (-5) + 18 + 12 = 28.
Ответ (для K = 3): 28.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
ID 39299.
4
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел N (1 <= N <= 1 000 000), L и C (1 <= L, C <= N <= 106). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.
Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3
1
-1
2
-2
3
В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3.
Ответ (для L = 3 и С = 3): 3.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
ID 39300.
5
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке подается 3 числа: количество чисел N (1 <= N <= 1 000 000), L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.
Пример организации исходных данных во входном файле (для L = 3 и С = 1):
5 3 1
1
-1
-5
-2
3
В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной -4 будет: -5+(-2)+3.
Ответ (для С = 3 и L = 1): -4.
В ответе укажите два числа в одной строке через пробел: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
В городе M расположена кольцевая автодорога длиной в N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы стоимость доставки мусора была минимальной. Стоимость доставки мусора вычисляется, как вместимость пункта сбора умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым. Контейнеры нумеруются с 1 до N.
Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?
Описание входных данных
Даны два входных файла (файл A и файл B), каждый из которых содержит (2 <= N <= 109) чисел. Первое число N - количество контейнеров для мусора. Последующие N чисел - количество килограмм мусора, которое производится на точке.
Описание выходных данных
Одно число - номер контейнера для мусора, рядом с которым стоит расположить перерабатывающий завод.
В ответе укажите два числа в одной строке через пробел: ответ для файла А и ответ для файла В.
Пример организации входных данных:
6
8
20
5
13
7
19
Для данного примера ответ - 6 (7*1 + 13*2 + 5*3 + 20*2 + 8*1 + 19*0).
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Гамма 2022». Количество передаваемых чисел в серии известно и не превышает 100 000. Все числа не превышают 10 000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «гамма-значение» серии показаний прибора – максимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 10 минут. Если получить такое произведение не удаётся, ответ считается равным -1.
Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N > 10\). В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
Выходные данные
Программа должна вывести одно число - описанное в условии произведение, либо -1, если получить такое произведение не удаётся.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
15
45
5
3
1
7
23
21
20
19
18
1
7
2
12
7 |
540 |
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Гамма 2022». Количество передаваемых чисел в серии известно и не превышает 100 000. Все числа не превышают 10 000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «гамма-значение» серии показаний прибора – минимальное нечетное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным -1.
Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N>6\). В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
Выходные данные
Программа должна вывести одно число - описанное в условии произведение, либо -1, если получить такое произведение не удаётся.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
12
45
5
3
1
7
23
21
20
19
18
1
7 |
1 |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
ЕГЭ - вычислительные задачи
Финансовый аналитик компании "Хлебосушки" анализирует прибыль компании на протяжении N месяцев. Аналитику поставили задачу найти интервал длиной не менее K месяцев с максимальной прибылью. Месяцы имеют сквозную нумерацию, начиная с 1 (с месяца открытия компании).
Вы - ведущий программист компании. Вам дали задачу написать программу, которая бы находила максимальную прибыль в непрерывном интервале длиной не менее K месяцев.
Формат входных данных
Первая строка содержит натуральное число N (1 < N ≤ 1 000 000) – количество месяцев существования компании и натуральное число K (1 < K < N) – минимально допустимый интервал. В каждой из следующих N строк находится одно целое число profiti, не превышающее по модулю 10 000 000: прибыль компании за iй месяц.
Формат выходных данных
Выведите одно число - максимальную прибыль в интервале длиной не менее K месяцев. Гарантируется, что ответ к задаче не превышает 109.
| |
![]()
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программе подается последовательность чисел и значение K. Особыми называются простые числа, перед которыми стоит знак «минус».
Рассмотрим все непрерывные подпоследовательности исходной последовательности, в которых количество особых чисел кратно K. Найдите максимальную сумму одной из таких подпоследовательностей.
Формат входных данных
В первой строке количество чисел N (100 ≤ N ≤ 5000000) и значение K. Каждая из следующих N строк содержит одно целое число, не превышающее по модулю 1000000. Гарантируется, что сумма любой подпоследовательности не превышает 109.
Формат выходных данных
Выведите одно число – максимальную сумму такой последовательности.
| |
![]()
|