| Условие задачи | | Прогресс | Попытки, все/успешные |
|
Темы:
ЕГЭ - вычислительные задачи
На вход программе подается последовательность чисел и значение K. Особыми называются простые числа, перед которыми стоит знак «минус».
Рассмотрим все непрерывные подпоследовательности исходной последовательности, в которых количество особых чисел кратно K. Найдите максимальную сумму одной из таких подпоследовательностей.
Формат входных данных
В первой строке количество чисел N (100 ≤ N ≤ 5000000) и значение K. Каждая из следующих N строк содержит одно целое число, не превышающее по модулю 1000000. Гарантируется, что сумма любой подпоследовательности не превышает 109.
Формат выходных данных
Выведите одно число – максимальную сумму такой последовательности.
| |
![]()
|
41/
3
|
|
Темы:
Префиксные суммы(минимумы, ...)
ЕГЭ - вычислительные задачи
Финансовый аналитик компании "Хлебосушки" анализирует прибыль компании на протяжении N месяцев. Аналитику поставили задачу найти интервал длиной не менее K месяцев с максимальной прибылью. Месяцы имеют сквозную нумерацию, начиная с 1 (с месяца открытия компании).
Вы - ведущий программист компании. Вам дали задачу написать программу, которая бы находила максимальную прибыль в непрерывном интервале длиной не менее K месяцев.
Формат входных данных
Первая строка содержит натуральное число N (1 < N ≤ 1 000 000) – количество месяцев существования компании и натуральное число K (1 < K < N) – минимально допустимый интервал. В каждой из следующих N строк находится одно целое число profiti, не превышающее по модулю 10 000 000: прибыль компании за iй месяц.
Формат выходных данных
Выведите одно число - максимальную прибыль в интервале длиной не менее K месяцев. Гарантируется, что ответ к задаче не превышает 109.
| |
![]()
|
77/
14
|
|
Темы:
ЕГЭ - вычислительные задачи
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Гамма 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 |
| |
![]()
|
91/
7
|
|
Темы:
ЕГЭ - вычислительные задачи
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Гамма 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 |
| |
![]()
|
32/
6
|
|
Темы:
ЕГЭ - вычислительные задачи
В городе 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).
| |
![]()
|
/
|
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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
/
|
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 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 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 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
/
|
|
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность из 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
| |
![]()
|
/
|
|
Темы:
Остатки
ЕГЭ - вычислительные задачи
У Анны Николаевны есть 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 |
| |
![]()
|
7/
2
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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 |
| |
![]()
|
1117/
212
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из N целых неотрицательных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Найти максимальную сумму произвольной пары ненулевых элементов последовательности. Найденная сумма должна быть кратна трём и между элементами пары должны быть нулевые элементы. Если такой пары нет, следует вывести 0.
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 10000.
Входные данные
В качестве результата, программа должна вывести одно число, количество найденных пар.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
1
0
2
0
5
0
8 |
9 |
| |
![]()
|
431/
98
|
|
Темы:
ЕГЭ - вычислительные задачи
Дана последовательность 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.
| |
![]()
|
1048/
471
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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)}
| |
![]()
|
996/
388
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность натуральных чисел 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 |
| |
![]()
|
933/
308
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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 |
| |
![]()
|
1219/
363
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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) |
Примечание: в примерах элементы массива располагаются в одну строчку для экономии места и улучшения читабельности. В самих тестах к задаче все эелементы расположены по одному числу в строке.
| |
![]()
|
641/
176
|
|
Темы:
ЕГЭ - вычислительные задачи
На вход программы поступает последовательность из 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 |
| |
![]()
|
1775/
148
|
|