Ошибка.
Попробуйте повторить позже
Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности, такие, что сумма элементов каждой из них кратна k = 27. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные: Даны два входных файла: файл A и файл B, каждый из которых содержит в первой строке количество чисел N . Каждая из следующих N строк содержит целое число, по модулю не превышающее .
Пример входного файла:
7
35
10
-18
-22
-22
49
-43
В этом наборе можно выбрать числа 35, 10 и -18, которые в сумме образуют число 27. А также числа -22 и 49, тоже в сумме образующие число 27. Ответом для данного примера будет число 2.
В ответе укажите два числа через пробел: сначала значение искомой суммы для файла А, затем для файла B.
f = open(’27B_04_2.txt’) n = int(f.readline()) a = [int(i) for i in f] k = 27 # Из сумм, изначально кратных 27-и не нужно ничего вычитать, поэтому для остатка 0 сумма всегда 0 sm = [0] + [10 ** 10] * (k - 1) # Префиксная сумма от начала строки до i имеет длину (i + 1), поэтому изначально хвосты равны -1 tl = [-1] * k s = 0 mx = 0 ln = 0 for i in range(len(a)): # Увеличиваем основную сумму s += a[i] # ВАЖНО - из-за наличия отрицательных чисел нельзя считать s # самой большой суммой на данный момент # Вычитаем из основной суммы префиксную с нужным остатком - получаем кратную 27-и сумму if s - sm[s % k] > mx: mx = s - sm[s % k] ln = i - tl[s % k] elif s - sm[s % k] == mx: # Если суммы равны - выбираем самую короткую ln = min(ln, i - tl[s % k]) # Заменяем префиксную сумму для остатка, если нашли её меньше чем предыдущую if s < sm[s % k]: sm[s % k] = s tl[s % k] = i print(ln)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!