Вопрос по информатике:
Сила заклинания
Вася нашел древний свиток с заклинанием. Заклинание состоит из 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.
Система оценки: Решения, верно работающие при 1 ≤ N ≤ 100 будут получать не менее 50% баллов.
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 04.08.2015 21:55
- Информатика
- remove_red_eye 14511
- thumb_up 48
Ответы и объяснения 1
Пусть 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)
- 05.08.2015 03:30
- thumb_up 24
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.