Ежедневно почтальон разносит корреспонденцию по домам. Его сумка вмещает не более 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.
Задача 4
В файле записана последовательность натуральных чисел. Назовём парой любые два числа из последовательности. Необходимо определить количество пар, в которых сумма чисел в паре делится без остатка на 11, а их произведение – на 2310.
Входные данные: Даны два входных файла: файл A (27-135a.txt) и файл B (27-135b.txt), каждый из которых в первой строке содержит натуральное число N (1 ≤ N < 1 000 000). В каждой из следующих N строк записано по одному натуральному числу, не превышающему 10 000.
Пример входного файла:
7
154
14
33
17
118
44
165
В этой последовательности существует одна пара чисел, 154 и 165, сумма которых (319) делится на 11, а произведение (25410) делится на 2310. Ответ: 1.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
191 3975706
Задание 17
В файле содержится последовательность из 10 000 целых положительных чисел. Каждое число не превышает 10 000. Определите и запишите в ответе сначала количество пар элементов последовательности, у которых сумма элементов кратна 60 и хотя бы один элемент из пары делится на 40, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.
А: 17 29278 19860
17b 311925638 19980