Ежедневно почтальон разносит корреспонденцию по домам. Его сумка вмещает не более M килограмм корреспонденции. Определите максимальное количество домов, расположенных друг за другом (как непрерывная подпоследовательность), которое ему удастся обойти. В ответе укажите количество домов.
Входные данные: Даны два входных файла: файл A (a1.txt) и файл B (b1.txt), каждый из которых в первой строке содержит два числа: N (1 ⩽ N ⩽ 10 000 000) – общее количество домов и M (1 ⩽ M ⩽ 100 000 000) – максимальный вес корреспонденции, который может унести с собой почтальон. В каждой из следующих N строк находится число – масса корреспонденции, которую нужно доставить в дом (натуральные числа, не превышающие 3000).
Пример входного файла:
7 10
1
3
5
3
6
5
8
Будем искать такую максимальную длину подпоследовательности, при которой возможно получить максимальную сумму, меньшую или равную 10. 1+3+5=9 – максимальная масса (килограммы), которую удастся получить, чтобы почтальон смог унести её. При этом он обойдёт три соседних дома (самые первые). Ответ: 3.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
288 24212
В файле записана последовательность натуральных чисел. Назовём тройкой любые три числа из последовательности, для которых расстояние между двумя любыми числами не меньше 17. Расстоянием называется разность номеров элементов последовательности. Необходимо определить количество троек, в которых сумма чисел в тройке делится без остатка на 7717.
Входные данные: Даны два входных файла: файл A (a2.txt) и файл B (b2.txt), каждый из которых в первой строке содержит натуральное число N (1 ≤ N < 1 000 000). В каждой из следующих N строк записано по одному натуральному числу, не превышающему 10 000.
Пример входного файла:
7
5
12
23
14
45
3
17
Будем искать тройки с расстоянием между элементами не менее 3, сумма которых делится на 9. В этой последовательности существует одна такая тройка чисел: (5, 14, 17). Их сумма 36 делится на 9, а расстояние между каждыми двумя числами в последовательности не меньше 3. Ответ: 1.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
19493 1378891946
Задача 3
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности длины K. Требуется найти максимальную сумму чисел, кратную 68, в двух таких непересекающихся подпоследовательностях.
Входные данные: Даны два входных файла: файл A (a3.txt) и файл B (b3.txt), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000) и длину подпоследовательностей K (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример входного файла:
5 2
68
67
9
60
811
Первая подпоследовательность: 68 67, вторая подпоследовательность – 9 60. Сумма: (68 + 67) + (9 + 60) = 204 делится на 68. Ответ: 204.