Дана последовательность из N натуральных чисел. Рассматриваются все её
Условие
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные.
Файл AФайл BДаны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.Пример организации исходных данных во входном файле:141214938595643286 В ответе укажите два числа: сначала значение искомой длины для файла А, затем — для файла B. Для приведенного примера ответ — 7. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Приведём решение на языке Python. f = open("27_B.txt")n = int(f.readline())mins = [1000000001 for i in range(43)]minl = [0 for i in range(43)]sum = 0maxsum = 0minlen = 0ms = 0l = 0for i in range(1, n + 1): num = int(f.readline()) sum = sum + num d = sum % 43 if d == 0: maxsum = sum minlen = i else: ms = sum - mins[d] l = i - minl[d] if ms > maxsum: maxsum = ms minlen = l if (ms == maxsum) and (l < minlen): maxsum = ms minlen = l if sum < mins[d]: mins[d] = sum minl[d] = iprint(minlen)
Осталось ещё 1 шаг
Приведём решение Матвея Курченко на языке…
Бесплатно · займёт минуту