2026/27, 9КЛ-1: линейные алгоритмы без дополнительной памяти

Дана последовательность из \(n\) целых чисел. Найдите их сумму.

Программа получает на вход число \(n\), \(2\le n\le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(-10^9\) до \(10^9\).

Программа должна вывести одно целое число — сумму данных чисел.

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

3
1
7
-9

-1

Дана последовательность из \(n\) целых чисел. Найдите в этой последовательности два соседних элемента с максимальной суммой.

Программа получает на вход число \(n\), \(2\le n\le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(-10^9\) до \(10^9\).

Программа должна вывести одно целое число — максимально значение суммы двух соседних элементов данной последовательности.

Решение должно иметь сложность \(O(n)\).

В этой задаче установлено небольшое ограничение по памяти: вы не сможете сохранить все данные числа в списке, ваша программа должна использовать \(O(1)\) памяти (размер используемой программой памяти должен быть ограничен и не зависит от \(n\)). Если вы превысите ограничение по памяти, то скорее всего результатом тестирования будет «Ошибка исполнения».

Для того, чтобы ваша программа работала быстро, используйте функцию sys.stdin.readline() из модуля sys вместо медленной функции input().

Пример

6
12
6
-4
27
-10
30

23

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

Программа получает на вход число \(n\), \(2\le n \le 10^6\). Следующие \(n\) строк содержат по одному целому числу от  \(-10^9\) до \(10^9\).

Программа должна вывести одно целое число — максимально значение суммы двух элементов данной последовательности.

Решение должно иметь сложность O(\(n\)) и использовать \(O(1)\) памяти.

Пример

4
-3
10
-2
-1

9

Дана последовательность \(a_i\) из \(n\) целых чисел. Найдите в этой последовательности два элемента \(a_i\) и \(a_j\) таких, что \(i \lt j\), \(a_i \gt a_j\), а сумма \(a_i+a_j\) была бы максимальна. Иными словами, нужно найти максимальную сумму двух неравных элементов, больший из которых идёт раньше в последовательности.

Программа получает на вход число \(n\), \(2\le n \le 10^6\). Следующие n строк содержат по одному целому числу от \(0\) до \(10^9\).

Программа должна вывести одно целое число — максимально значение искомой суммы. Если таких элементов не существует, программа должна вывести число \(-1\).

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

6
5
7
1
4
8
2

11

2
10
20

-1

Дана последовательность из \(n\) целых чисел. Найдите в этой последовательности два элемента с минимальным произведением.

Программа получает на вход число \(n\), \(2\le n \le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(-10^9\) до \(10^9\).

Программа должна вывести одно целое число — минимальное значение произведения двух элементов данной последовательности.

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

5
7
-3
12
0
-5

-60

Дана последовательность \(a_i\) из \(n\) целых чисел. Найдите в этой последовательности непрерывный отрезок с максимальной суммой элементов. Отрезок должен содержать хотя бы одно число.

Программа получает на вход число \(n\), \(1\le n \le 10^6\). Следующие n строк содержат по одному целому числу от \(-10^9\) до \(10^9\).

Программа должна вывести одно целое число — максимальное значение суммы на подотрезке.

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

7
6
-15
3
-1
5
2
-2

9

3
-1
-2
-3

-1

Дана последовательность из \(n\) целых чисел. Рассматриваются произведения пар элементов \(a_i\times a_j\) таких, что \(i\lt j\).

Определите количество пар элементов, произведение которых делится на \(26\).

Программа получает на вход число \(n\), \(1\le n \le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(1\) до \(10^9\).

Программа должна вывести одно целое число — количество искомых пар.

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

4
2
6
13
39

4

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

Программа получает на вход число \(n\), \(1\le n\le 0{,}5\cdot 10^6\). Следующие \(n\) строк содержат по два целых числа от \(1\) до \(10^9\).

Программа должна вывести одно целое число — максимально возможное значение искомой суммы или число \(0\), если такую сумму составить нельзя.

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Примеры

6
1 3
5 12
6 9
5 4
3 3
1 1

32

1
3 3

0

Поезд в пути следования останавливается на \(k\) станциях (станция номер \(1\) — начальная, а станция номер \(k\) — конечная). Известно, на какой станции садится и выходит каждый пассажир. Определите наибольшее число пассажиров, которые находились в поезде одновременно (на перегоне между двумя станциями).

Первая строка входных данных содержит количество станций \(k\), \(2\le k\le 10^4\). Вторая строка содержит количество пассажиров \(n\), \(1\le n\le 10^6\). Следующие \(n\) строк содержат по два числа \(a_i\) и \(b_i\), \(1\le a_i\lt b_i\le k\) — номера станций, на которых вошёл и вышел \(i\)-й пассажир.

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

Решение должно иметь сложность \(O(n+k)\) и использовать \(O(k)\) памяти.

Пример

5
3
2 5
3 4
4 5

2

Дана последовательность \(a_i\) из \(n\) целых чисел. Расстоянием между двумя элементами \(a_i\) и \(a_j\) будем называть значение \(|j-i|\), то есть расстояние между двумя соседними элементами равно \(1\).

По данному значению \(k\) найдите два элемента последовательности, расстояние между которыми не превосходит \(k\), а их сумма была бы максимальной.

Первая строка входных данных содержит число \(k\), \(1\le k\le 10^3\). Во второй строке дано число \(n\), \(2\le n \le 10^6\), \(nk \le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(-10^9\) до \(10^9\).

Программа должна вывести одно целое число — максимальное значение искомой суммы.

Решение должно иметь сложность \(O(nk)\) и использовать \(O(k)\) памяти.

Пример

3
6
-3
7
-8
-6
-1
5

6

1000
2
10
20

30

Дана последовательность \(a_i\) из \(n\) целых чисел. Расстоянием между двумя элементами \(a_i\) и \(a_j\) будем называть значение \(|j-i|\), то есть расстояние между двумя соседними элементами равно \(1\).

По данному значению \(k\) найдите два элемента последовательности, расстояние между которыми не менее \(k\), а их произведение было бы минимальным.

Первая строка входных данных содержит число \(k\), \(1\le k\le 10^6\). Во второй строке дано число \(n\), \(k + 1 \le n \le 10^6\), \(nk\le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(1\) до \(10^9\).

Программа должна вывести одно целое число — минимальное значение искомого произведения.

Решение должно иметь сложность \(O(nk)\) или \(O(n)\) и использовать \(O(k)\) памяти. Обратите внимание, в этой задаче значение \(k\) небольшое.

Пример

3
7
15
45
6
4
3
7
12

42

Дана последовательность \(a_i\) из \(n\) целых чисел. Расстоянием между двумя элементами \(a_i\) и \(a_j\) будем называть значение \(|j-i|\), то есть расстояние между двумя соседними элементами равно \(1\).

По данному значению \(k\) найдите количество пар элементов последовательности, расстояние между которыми не менее \(k\), а их произведение делится на 9 .

Первая строка входных данных содержит число \(k\), \(1\le k\le 10^4\). Во второй строке дано число \(n\), \(k + 1 \le n \le 10^6\). Следующие \(n\) строк содержат по одному целому числу от \(1\) до \(10^9\).

Программа должна вывести одно целое число — количество искомых пар.

Решение должно иметь сложность \(O(n)\) и использовать \(O(k)\) памяти. Обратите внимание, в этой задаче значение \(k\) достаточно большое, обработка одного элемента последовательности должна выполняться за \(O(1)\).

Пример

3
8
6
8
9
10
3
7
2
6

6

Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.

В конкурсе участвуют \(n\) человек, при этом количество мест равно \(k\). Определите полупроходной балл, то есть такое количество баллов, что более \(k\) абитуриентов набрало такой или больший балл, а количество абитуриентов, набравших строго больше баллов, будет меньше \(k\).

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

Первая строка входных данных содержит число \(k\) — количество мест для зачисления, \(1\le k\le 10^6\). Следующая строка содержит число \(n\) — количество абитуриентов, \(1\le n\le 10^6\). Следующие \(n\) строк содержат баллы абитуриентов — три числа от \(0\) до \(100\) каждое.

Программа должна вывести одно число — полупроходной балл. Если полупроходной балл не определён, то программа должна вывести число \(-1\). Такое может произойти в двух случаях: можно установить такой проходной балл, что этот или больший балл набрало ровно \(k\) абитуриентов или если количество абитуриентов, не имеющих неудовлетворительных оценок, будет не больше \(k\).

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

5
9
70 70 70
100 100 0
70 60 70
70 60 70
100 30 100
50 50 50
60 70 70
50 50 50
40 40 40

150

1
3
50 50 50
100 100 100
100 0 100

-1

Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.

В конкурсе участвуют \(n\) человек, при этом количество мест равно \(k\). Определите проходной балл, то есть такое количество баллов, что количество участников, набравших такое или большее количество баллов, не превосходит \(k\), а при добавлении к ним абитуриентов, набравших наибольшее количество баллов среди оставшихся непринятых абитуриентов, общее число принятых абитуриентов станет больше \(k\).

Иными словами, проходной балл равен такому минимальному баллу \(s\), что на \(k\) мест можно зачислить всех абитуриентов, набравших не менее \(s\) баллов. При этом значение \(s\) есть минимальный балл зачисленного абитуриента.

Первая строка входных данных содержит число \(k\) — количество мест для зачисления, \(1\le k\le 10^6\). Следующая строка содержит число \(n\) — количество абитуриентов, \(1\le n\le 10^6\). Следующие \(n\) строк содержат баллы абитуриентов — три числа от \(0\) до \(100\) каждое.

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

Также возможны две ситуации, когда проходной балл не определен.

Если будут зачислены все абитуриенты, не имеющие неудовлетворительных оценок (это множество может быть и пустым), программа должна вывести число \(-1\).

Если количество абитуриентов, имеющих равный максимальный балл, больше \(k\), программа должна вывести число \(-2\).

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

5
9
70 70 70
100 100 0
70 60 70
70 60 70
100 30 100
50 50 50
60 70 70
50 50 50
40 40 40

200

1
2
40 40 40
100 100 39

-1

1
2
60 60 60
100 40 40

-2

Наблюдая за курсом доллара, возникает мысль: «Эх, сколько бы можно было заработать!...»

Пусть у вас есть сумма в \(s\) рублей, и каждый из \(n\) дней вы можете покупать и продавать доллары по заранее известному курсу. Определите, какую максимальную сумму (в рублях) вы можете получить через \(n\) дней.

Первая строка входных данных содержит значение \(s\), \(1\le s\le 10^9\). Вторая строка содержит количество дней \(n\), \(2\le n\le 10^6\). Следующие \(n\) строк содержат по два числа \(a_i\) и \(b_i\), \(1\le a_i\lt b_i\le 10^9\). В \(i\)-й день вы можете продавать доллары по цене \(a_i\) рублей и покупать доллары по цене \(b_i\) рублей. Вы можете продавать и покупать любое целое положительное число долларов каждый день.

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

Решение должно иметь сложность \(O(n)\) и использовать \(O(1)\) памяти.

Пример

100
7
30 32
35 40
20 26
23 28
26 27
27 29
24 26

113

1000
2
97 99
99 101

1000