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

ID 82123. Подводная станция

На подводной исследовательской станции «Нептун-7» требуется установить новый научный модуль. Станция состоит из M уровней (пронумерованных от 1 до M сверху вниз, где уровень 1 ближе всего к поверхности) и K отсеков на каждом уровне.

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

Если несколько отсеков имеют одинаковое максимальное количество свободных отсеков над ними, выбирается отсек на уровне ближе к поверхности (с меньшим номером уровня).

Гарантируется, что хотя бы один свободный отсек на станции существует.

Формат входных данных

В первой строке находятся три числа:

• N — количество занятых отсеков (1 ≤ N ≤ 10 000)
• M — количество уровней (1 ≤ M ≤ 100 000)
• K — количество отсеков на каждом уровне (1 ≤ K ≤ 100 000)

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

Формат выходных данных

Два целых числа через пробел:

1. Номер уровня выбранного отсека
2. Количество свободных отсеков над ним (подряд, с тем же номером)

ID 82122. Космический техосмотр

На орбитальной станции «Галактика-7» завершился ежегодный технический осмотр космических кораблей. По его результатам каждый корабль получил:

• Оценки трёх бортовых систем: двигательной, навигационной и системы жизнеобеспечения (по шкале от 2 до 5, где 2 — критическая неисправность, 5 — отличное состояние)
• Статус лицензии пилота: действующая или просроченная

Корабль допускается к полётам, если выполнены оба условия:

1. Все три бортовые системы имеют оценку 3 или выше
2. Лицензия пилота действующая

Корабль не допущен к полётам, если хотя бы одно из условий не выполнено.

Руководство станции решило предоставить возможность экстренного ремонта одной системы одному из кораблей. Корабль может претендовать на ремонт, если:

1. Лицензия пилота действующая
2. Ровно одна система имеет критическую неисправность (оценка 2), а две другие системы исправны (оценка 3 или выше)

Если таких кораблей несколько, выбирается тот, у которого наибольшая сумма оценок всех трёх систем (такой корабль ближе всего к допуску).

Гарантируется, что ровно один корабль удовлетворяет всем критериям отбора.
 

Формат входных данных

В первой строке находится число N — количество кораблей (1 ≤ N ≤ 1000).

Каждая из следующих N строк содержит пять целых чисел через пробел:

• ID — бортовой номер корабля (натуральное число, не превышающее 10⁸)
• S₁, S₂, S₃ — оценки трёх бортовых систем (каждая от 2 до 5)
• L — статус лицензии пилота (1 — действующая, 0 — просроченная)

Формат выходных данных

Выведите два числа через пробел:

1. Количество кораблей, не допущенных к полётам
2. Бортовой номер корабля, который получит возможность экстренного ремонта

ID 49320. Подпоследовательность с особыми числами - 1

ID 49190. Подсчет прибыли

ID 42936. Гамма 2022-2

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

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

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

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

Примеры

ID 42935. Гамма 2022

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

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

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

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

Примеры

ID 39816. ДВ-2022

В городе M расположена кольцевая автодорога длиной в N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы стоимость доставки мусора была минимальной. Стоимость доставки мусора вычисляется, как вместимость пункта сбора умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым. Контейнеры нумеруются с 1 до N.
Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

Описание входных данных
Даны два входных файла (файл A и файл B), каждый из которых содержит (2 <= N <= 10⁹) чисел. Первое число 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 <= 10⁶). Каждая из следующих 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 чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратно 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 натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество нечётных чисел кратно 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 натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество чётных чисел кратно 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 38828. Демо-2022 (fipi-F291D4)

Дана последовательность из 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 38794. Раздача конфет

У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит Ai количество конфет.  Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- Al + Al+1 + ... + Ar делится на M.

Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=10⁵) и M (2<=M<=10⁹). Вторая строка содержит N чисел Ai (1<=A_i<=10⁹, 1<=i<=N).

Выходные данные
Выведите количество пар (l, r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.
 

Примеры

ID 33548. По мотивам ЕГЭ 2019

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

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


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

Примеры

ID 33483. Максимальная сумма произвольной пары

Примеры

ID 33482. Максимальная сумма пары чисел

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

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

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

Примеры

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

Примеры

ID 33295. Сумма чисел в парах

Примеры

ID 33250. Пара с минимальной суммой

Примеры