Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №6

Просмотров 8 Комментарии 0

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], …, pref[n] = a[0] + a[1] + … + a[n]

Подается число $n$ , затем $n$ чисел. Требуется найти длину (количество входящих элементов) наибольшей префиксной суммы, сумма которой кратна $100$ . Если таких префиксных сумм нет, выведите $− 1$ . Напишите ответ для $n = 10$ и чисел $7392$ , $2345$ , $263$ , $8372$ , $372$ , $1836$ , $8326$ , $9736$ , $822$ , $6183$ .

n = int(input())
pref = [0]*n
pref[0] = int(input())
ans = -1
maxim = pref[0]
if pref[0] % 100 == 0:
    ans = 1
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
    if pref[i] % 100 == 0 and pref[i] > maxim:
        ans = i+1
        maxim = pref[i]
print(ans)

Ответ: 3