Ограничение памяти: 256M Сила заклинания Оценка за задачку: 30 баллов Вася нашел
Ограничение памяти: 256M Сила заклинания Оценка за задачу: 30 баллов Вася нашел древний свиток с заклинанием. Заклинание состоит из N чисел. Сила заклинания рассчитывается следующим образом: для каждой подстроки (в данном случае это последовательность подряд идущих чисел), считается сумма чисел в этой подстроки, а потом вычисляется сумма всех сумм подстрок. Помогите Васе найти силу заклинания. Формат входных данных В первой строке содержится число N (1 N 10000) - количество чисел в записи заклинания. Во второй строке содержится N чисел, задающих заклинание. Каждое из чисел не превосходит 10000 по модулю. Формат результата Выведите одно число - силу заклинания. Примеры Входные данные 2 10 20 Результат работы 60 Входные данные 3 2 1 3 Итог работы 19 Примечания В первом тесте последующие подстроки: 10; 20; 10 20. Сумма одинакова 60. Во втором тесте следующие подстроки: 2; 1; 3; 2 1; 1 3; 2 1 3. Сумма одинакова 19.
Задать свой вопрос
Пусть f(k - 1) сумма сумм всех чисел из подстрок, заканчивающихся на числе с номером k - 1. Вычислим f(k).
f(k) = (a(0) + a(1) + a(2) + ... + a(k - 1) + a(k)) + (a(1) + a(2) + ... + a(k - 1) + a(k)) + (a(2) + ... + a(k - 1) + a(k)) + ... + (a(k - 1) + a(k)) + a(k) = f(k - 1) + (k + 1) * a(k)
Разыскиваемая сумма есть сумма всех f(k).
python 3.6:
n = int(input())
a = enumerate(map(int, input().split()))
s = f = 0
for k, ak in a:
f += (k + 1) * ak
s += f
print(s)
-
Вопросы ответы
Статьи
Информатика
Статьи
Разные вопросы.
Математика.
Физика.
Геометрия.
Разные вопросы.
Обществознание.
Математика.
Химия.
Русский язык.
Разные вопросы.