Задание 27 ЕГЭ по информатике

Грузовики собирают мусор вдоль трассы с односторонним движением. Известна вместимость каждого грузовика (одно значение для всех) и вместимость баков, из которых грузовик высыпает мусор в кузов. Так же на пути есть мусороперерабатывающие пункты (обозначенные отрицательными числами, соответствующим объему перерабатываемого мусора), в которых грузовик может оставить часть уже собранного мусора. Грузовик может высыпать часть мусорного бака в кузов. В каждом мусороперерабатывающем пункте можно оставить суммарно не более указанного значения. Мусор в мусороперерабатывающем пункте может оставить не один грузовик.

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

Описание входных данных

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

Выходные данные: одно число – минимальное количество грузовиков, которого хватит для сбора всего мусора вдоль трассы.

Пример входных данных

7 50

40

-20

30

25

-15

-20

10

Рассуждение для примера входных данных:

Первый грузовик может: забрать бак 40, оставить во втором пункте 20 единиц мусора, забрать 30, оставить 10 в 5 пункте и собрать 10 в последнем.

Второй грузовик соберет 25 единиц мусора в 4 пункте (может оставить их в 5 и 6 пунктах). Ответ: 2

На вход программе подается последовательность целых чисел. Рассматриваются все непрерывные подпоследовательности этой последовательности, произведение которых является делителем числа M = 8 023 320. Гарантируется, что хотя бы одна такая подпоследовательность существует. Найдите такую подпоследовательность наибольшей длины и определите номер её первого элемента в исходной последовательности. Если таких последовательностей несколько, используйте ту, которая встречается раньше других. Нумерация элементов последовательности начинается с 1.

Входные данные. Даны два входных файла, содержит в первой строке число N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.

Пример входного файла (для M = 60):

7

1

3

4

93

8

5

95

В этой последовательности есть следующие непрерывные подпоследовательности, произведение элементов которых является делителем числа 60: {1}, {3}, {4}, {5}, {1, 3}, {3, 4}, {1, 3, 4}. Максимальное количество элементов (три) содержит подпоследовательность, начинающаяся с первого элемента. Ответ: 1.

В ответе укажите два числа: сначала номер первого элемента искомой подпоследовательности для файла А, затем для файла B.

На вход программе подается последовательность целых чисел. Рассматриваются все непрерывные подпоследовательности исходной последовательности, такие что произведение элементов каждой из них не кратно M = 858967. Найдите количество таких подпоследовательностей.

Входные данные. Даны два входных файла, содержит в первой строке число N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.

Пример входного файла (для M = 20):

4

3

17

20

1

В этой последовательности есть 4 подпоследовательности, произведение элементов которых не делится на 20: {3}, {3, 17}, {17} и {1}. Ответ — 4.

В ответе укажите два числа: сначала искомое количество подпоследовательностей для файла А, затем для файла B.

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

Входные данные. Даны два входных файла, содержит в первой строке числа N и M, записанные через пробел (1 ≤ N, M ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.

Пример входного файла:

4 20

3

17

20

1

В этой последовательности есть 4 подпоследовательности, произведение элементов которых не делится на 20: {3}, {3, 17}, {17} и {1}. Ответ — 4.

В ответе укажите два числа: сначала искомое количество подпоследовательностей для файла А, затем для файла B.

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

Описание входных данных

В первой строки два числа N (количество баков) и K (необходимых объем, выраженный в литрах). В следующих N строках объемы баков, расположенных в системе.

Выходные данные: одно число – минимальное количество опустошенных баков, объем которых равен Х.

Пример входных данных

6 18

10

5

3

21

15

3

Такой набор баков можно представить в виде рисунка следующим образом

Задачу можно решить перекрыв:

• 2 и 5 краны, тогда суммарный объем 6, 1 и 2 баков будет равен 18,

• 6 и 3 краны, тогда суммарный объем 1, 2 и 3 баков будет равен 18,

• 4 и 6 краны, тогда суммарный объем 5 и 6 баков будет равен 18.

Пример выходных данных для примера: 2

Дана последовательность, состоящая из N целых неотрицательных чисел. Рассматриваются подпоследовательности исходной последовательности, состоящие из K элементов и содержащие в себе хотя бы один нуль. Гарантируется, что K - нечётное.

Среди этих подпоследовательностей найти такие, в которых суммы элементов, расположенных по разные стороны от центра, равны. Центральное число в суммы не учитывается. Найти количество подходящих подпоследовательностей.

Входные данные.

Даны два входных файла (файл A и файл B).

В каждом файле на вход подаётся два числа: N и K.

Следом N чисел. При этом (2 ≤ N ≤ 5 000 000).

Пример входных данных (N = 8, K = 5):

8 5

4

2

0

2

4

1

3

0

Ответ: 1.

Пояснение для примера: взяли подпоследовательность (4 - 2 - 0 - 2 - 4). Здесь центр - 0, сумма слева от центра = 4 + 2 = 6, сумма справа = 2 + 4 = 6. При этом она содержит в себе ровно один нуль. Нашлась одна такая подпоследовательность.

Дайте ответ для файла А и для файла B.

(Л. Шастин) Дана последовательность, состоящая из N натуральных чисел. Назовём "границами" одинаковые числа.

Рассматриваются все подпоследовательности исходной последовательности с ненулевой суммой элементов, кратной D, расположенные меж двух "границ".

Примечание: искомые подпоследовательности могут включать себя и другие "границы", но обязаны быть открыты и закрыты какими-либо "границами". Найти количество подходящих подпоследовательностей.

Входные данные.

Даны два входных файла (файл A и файл B).

В каждом файле на вход подаётся два числа: N и D.

Следом N чисел. При этом (2 ≤ N ≤ 5 000 000).

Пример входных данных (здесь N = 6, D = 2):

6 2

4

2

4

3

5

4

Ответ: 3.

Пояснение для примера: взяли подпоследовательности

- (2), она кратна D = 2 и стоит между двумя "граничными" четвёрками,

- (3 + 5 = 8), она кратна D = 2 и находится между "граничными" четвёрками,

- (2 + 4 + 3 + 5 = 14), кратна D = 2 и располагается между четвёрками.

Нашлись три подходящих подпоследовательности.

Дайте ответ для файла А и для файла B.

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

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

Входные данные

Дано два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N (1<,=N<,=10 000 000) - количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число - количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.

В ответе укажите два числа: сначала значение искомой величины для файла А, зачем - для файла В.

Типовой пример организации данных на входном файле

6

8

20

5

13

7

19

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

1*7+0*19+1*8+2*20+3*5+2*13

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Исследовательская сейсмическая лаборатория представляет собой окружность, составленную из сейсмографических датчиков, расположенных на одинаковом расстоянии друг от друга. Каждый датчик несколько раз в сутки отправляет сигнал в центр обработки данных (ЦОД). ЦОД решено разместить в окрестности одного из датчиков так, чтобы энергия, расходуемая на передачу данных от всех датчиков, была минимальной.

Известно, что количество энергии, необходимое для передачи любого одного сигнала прямопропорционально квадрату расстояния от датчика до ЦОД.

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

Описание входных данных:

Первое строка содержит два числа N — количество датчиков и R – расстояние между соседними датчиками. Последующие N чисел — количество сигналов, отправляемое датчиком в сутки. Номер датчика соответствует номеру строки, строки нумерубтся с 1.

Описание выходных данных:

Одно число — номер датчика, возле которого следует разместить ЦОД.

Пример организации входных данных:

6 2

8

20

5

13

7

19

Для данного примера ответ — 6 (20⸱4² + 8⸱2² + 19⸱0 + 7⸱2² + 13⸱4² + 5⸱6²).

Дана последовательность, состоящая из N натуральных чисел. Назовём подпоследовательность подходящей, если элементы в ней образуют арифметическую прогрессию с шагом Q >,= 1, при этом сумма элементов этой подпоследовательности кратна К, а количество элементов в ней кратно D. Найдите среди подходящих подпоследовательностей ту, длина которой наибольшая.

В ответ пойдёт длина найденной подпоследовательности.

Входные данные.

Даны два входных файла (файл A и файл B).

В каждом файле на вход подаётся три числа: N, K и D.

Следом N чисел. При этом (2 ≤ N ≤ 5 000 000).

Пример входных данных (для примера N = 8, K = 2, D = 2):

8 2 2

5

4

6

8

10

7

3

2

Ответ: 4.

Пояснение для примера: взяли подпоследовательность (4 + 6 + 8 + 10).

Её длина = 4, она кратна D = 2, сумма = 28, она кратна K = 2.

Дайте ответ для файла А и для файла B.

Известны высоты всех домов в городах А и Б. Требуется найти минимальную разницу в высоте среди любых двух домов. Первый дом берётся из города А, второй дом – из города Б.

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N – количество домов в каждом из городов. В следующих N строках находятся высоты домов города А – целые числа, не превышающее 10¹⁴. В следующих за ними N строках находятся высоты домов города Б – целые числа, не превышающее 10¹⁴. Высоты домов каждого города расположены в порядке возрастания.

Выходные данные
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле
3
1
7
20
10
30
32

При таких исходных данных высоты домов города А это (1, 7, 20), высоты домов города Б (10, 30, 32). Минимальная разница высот будет между городами (7 и 10). Разница их высот равна 10 - 7 = 3. Порядок домов не имеет значения, разница между двумя любыми высотами всегда является положительным числом.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

(Л.Шастин) Дана последовательность натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, в которых начальное число последовательности делится на 21 и является квадратом конечного числа последовательности. Найдите длину наибольшей такой подпоследовательности.

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 100000). Каждая из следующих N строк файлов содержит одно натуральное число, не превышающее 10000.

Пример входного файла:

7

441

1764

21

19

17

42

95

В этом наборе можно выбрать последовательности (441-21) и (1764-42), длина первой – 3, длина второй – 5. Ответ: 5.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

(А.Жуков) Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов (a_i, a_j) этого набора, в которых 1 ≤ i+5 ≤ j ≤ N, сумма элементов нечётна, а произведение делится на 13.

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример входного файла:

7

4

14

27

39

7

2

13

Для указанных входных данных количество подходящих пар должно быть равно 2. В приведённом наборе имеются две пары (4, 13) и (14, 13), сумма элементов которых нечётна, произведение кратно 13 и индексы элементов последовательности отличаются не менее, чем на 5.

В ответе укажите два числа: сначала количество подходящих пар для файла А, затем для файла B.

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

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример входного файла:

11

12

45

5

3

17

23

21

20

19

12

26

Для указанных входных данных искомое контрольное значение равно 95.

В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.

Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Они представляют собой результаты измерений, выполняемых прибором с интервалом 1 минута. Требуется найти для этой последовательности контрольное значение – наименьшую сумму квадратов двух результатов измерений, выполненных с интервалом не менее, чем в 5 минут.

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример входного файла:

9

12

45

5

4

21

20

10

12

26

Для указанных входных данных искомое контрольное значение равно 169.

В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.

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

Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

Описание входных данных:

Первое число N — количество контейнеров для мусора. Последующие N чисел — количество килограмм мусора, которое производится на точке.

Описание выходных данных:

Одно число — номер контейнер для мусора рядом с которым стоит расположить перерабатывающий завод.

Пример организации входных данных:

6

8

20

5

13

7

19

Для данного примера ответ — 6 (7⸱1 + 13⸱2 + 5⸱3 + 20⸱2 + 8⸱1 + 19⸱0).

Дана последовательность натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество чисел, делящихся на 5, положительно и кратно 11. Найдите количество таких подпоследовательностей.

Входные данные.

Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 100000). Каждая из следующих N строк файлов содержит одно натуральное число, не превышающее 10000.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

На вход программе подается два числа N и K, а также последовательность из N целых чисел в диапазоне от 1 до K. Рассматриваются все непрерывные подпоследовательности исходной последовательности, в которых содержатся ровно K различных чисел . Программа должна вывести одно число – минимальную длину такой подпоследовательности. Гарантируется, что в последовательности такая подпоследовательность существует.

Входные данные. Даны два входных файла, каждый содержит в первой строке натуральное число N – количество чисел в последовательности (100 ≤ N ≤ 5000000) и натуральное число K. В каждой из следующих N строк записано одно целое число в диапазоне от 1 до K

Пример входного файла:

8 5

1

1

2

1

3

4

5

1

Ответ: 5

Пояснение: В ответ идёт длина подпоследовательности 2 1 3 4 5, так как она содержит все числа от 1 до K=5 и её длина минимальна.

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

Рассматриваются все непрерывные подпоследовательности исходной последовательности,

такие, что их сумма кратна K, при этом сумма невыбранных (невошедших в эту подпоследовательность)

чисел кратна D и состоит из нечётного количества элементов.

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

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 5000000), значение K (K >, 0) и значение D (D >, 0), разделённые пробелами. Каждая из следующих N строк файла содержит одно положительное целое число. Гарантируется, что сумма любой подпоследовательности не превышает 10⁹.

Пример входного файла:

8 2 7

10

7

4

3

16

3

9

4

Можно выбрать подпоследовательность (16, 3, 9), которая имеет сумму 28, кратную 2. При этом сумма оставшихся (невыбранных) элементов = 28 , она кратна 7 и состоит из нечётного количества элементов (из 5: 10 + 7 + 4 + 3 + 4). Ответ: 28.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

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

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10⁸.

Пример входного файла:

4

8

7

12

23

Для указанных данных можно выбрать следующие группы: {12, 23}, {8, 7}. Программа должна вывести количество этих групп – 2.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

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

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10⁸.

Пример входного файла:

6

21

29

12

72

14

28

Для указанных данных можно выбрать следующие группы: {21, 29}, {21, 29, 72, 28}. Суммы элементов данных групп равны 50 и 150. Программа должна вывести наибольшую из этих сумм – 150.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Учёные исследовали уровень воды моря на определённом участке берега с помощью футштока. Они ежеминутно фиксировали высоту поверхности воды и получили в совокупности N показаний в условных единицах, которые передали в гидрологический кластер.
Определите два таких переданных показания, чтобы время между моментами их передачи было кратно K, а их произведение было максимально возможным. Укажите найденное произведение двух показаний.

Входные данные
Даны два входных файла (файл A и файл B ), каждый из которых в первой строке содержит натуральное число K. Во второй – количество переданных показаний N (1 ≤ N ≤ 10 000 000, N >, K).
В каждой из следующих N строк находится одно целое число, по модулю не превышающее 10 000 000, обозначающее высоту поверхности воды за соответствующую минуту. Показания расположены в порядке их фиксации.
Запишите в ответе два числа: сначала значение искомой величины для файла A, затем – для файла B.
Типовой пример организации данных во входном файле
2
5
8
9
-7
3
6
При таких исходных данных максимально возможное произведение двух показаний равно 48 – это произведение показаний, зафиксированные в первую и пятую минуты.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 67. Найдите среди них подпоследовательность с максимальной суммой. Укажите в ответе найденную максимальную сумму.

Входные данные

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел N (1 <, N <, 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

7

1

3

4

93

8

5

95

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем — для файла В.

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

Входные данные

Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма любой выборки заданных чисел не превышает 2 ∙ 10⁹ по абсолютной величине.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Дана последовательность целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных чётных элементов кратно k = 30

Входные данные

Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма любой выборки заданных чисел не превышает 2 ∙ 10⁹ по абсолютной величине.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Набор данных представляет собой последовательность натуральных чисел. Необходимо найти количество подпоследовательностей подряд идущих чисел, чтобы их сумма делилась на 39 и количество чисел в ней не превышало k=20. Гарантируется, что такие подпоследовательности существуют.

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 10⁸). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.

Пример входного файла (для k=3):

6

17

22

11

67

14

117

В этом наборе можно выбрать последовательности 17+22 (сумма 39), 11+67 (сумма 78) и 117. Ответ: 3.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

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

Входные данные. Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (100 ≤ N ≤ 5000000). Каждая из следующих N строк файлов содержит одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности, содержащей особое число, не превышает 10⁹.

Пример входного файла:

14

-1

-1

2

-3

3

20

1

-1

6

-7

8

23

8

1

В этом наборе пять особых чисел: 2, 20, 6, 8, 8. Можно выбрать подпоследовательность (23, 8, 1), которая имеет сумму 32 и содержит одно особое число. Ответ для приведенного примера: 32.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Набор данных представляет собой последовательность целых чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была минимальной и делилась на 2077, и определить её длину. Гарантируется, что такая подпоследовательность существует. Если таких подпоследовательностей несколько, нужно выбрать подпоследовательность наибольшей длины.

Входные данные.

Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (100 ≤ N ≤ 5000000). Каждая из следующих N строк файлов содержит одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает 10⁹.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.