Лена учится играть на пианино. У нее есть n композиций, упорядоченных по возрастанию сложности. Для каждой композиции Лена знает время, которое ей потребуется для ее исполнения. Перед тем, как начать учиться, она выбирает целое число L от 1 до n включительно и строит свою программу обучения следующим образом: в первый день она играет композиции 1 , 2 , . . . , L , во второй день композиции 2 , 3 , . . . , L + 1 и так далее. В день, когда Лена играет последнюю композицию, обучение заканчивается (действительно, она же успешно сыграла самую сложную композицию).
Лена заметила, что от выбора L время, которое она проведет за исполнением композиций, меняется. Ей стало интересно, сколько времени она проведет за исполнением композиций, если выберет L = 1 , 2 , . . . , n .
Требуется написать программу, которая для каждого L = 1 , 2 , . . . , n подсчитывает суммарное время, которое Лена потратит на исполнение композиций при заданном L .
Входные данные В первой строке записано число n ( 1 ≤ n ≤ 3 ⋅ 10 5 ) – количество композиций. В следующей строке через пробел записаны n чисел a 1 , a 2 , . . . , a n ( 1 ≤ a i ≤ 10 7 ) , где a i – время исполнения i -й композиции
Выходные данные Выведите n чисел через пробел – суммарное время для L = 1 , 2 , . . . , n соответственно.
Система оценки Решения, работающие правильно при n ≤ 5 , будут набирать не менее
Решения, работающие правильно при n ≤ 300 , будут набирать не менее
Решения, работающие правильно при n ≤ 10 000 , будут набирать не менее
Примеры входные данные 4 1 3 2 4 выходные данные 10 15 15 10 входные данные 5 5 1 3 5 4 выходные данные 18 27 30 27 18 Примечание Обращаем ваше внимание на то, что ответ в данной задаче может быть достаточно большим, поэтому рекомендуем использовать 64-битный тип данных. В C++ для этого предусмотрен тип long long, в Pascal – int64.
Так же, давайте разберем первый пример из условия:
При L = 1 В первый день Лена потратит 1 минуту
Во второй – 3 минуты
В третий – 2 минуты
И в четвертый – 4 минуты
Итого 1+3+2+4=10 минут
При L = 2 В первый день Лена потратит 1+3=4 минуты
Во второй – 3+2=5 минут
В третий – 2+4=6 минут и закончит обучение, так как сыграет последнюю композицию
Итого 4+5+6=15 минут
При L = 3 В первый день Лена потратит 1+3+2=6 минут
Во второй – 3+2+4=9 минут
Итого 6+9=15 минут
При L = 4 В первый и единственный день Лена потратит 1+2+3+4=10 минут
Два Первый, прямой. Просто перебрать возможные варианты (не забывая про инверсию). Нужные суммы: 7, 14, 21, 28, 35 7 выходит при: 1+6,2+5,3+4. 14 выходит при: 1+13,2+12,3+11,4+10,5+9,6+8,7+7 21 выходит при: 1+20,2+19,3+18,4+17,5+16,6+15,7+14,8+13,9+12,10+11 28 выходит при: 8+20,9+19,10+18,11+17,12+16,13+15,14+14 35 выходит при: 15+20,16+19,17+18 При инверсиях кол-во вариантов: В первом случае 3*2=6, во втором: 2*6+1=13. Всего: 13+6=19. В третьем случае 10*2=20 В четвертом случае 2*6+1=13, в пятом: 3*2=6. Всего так же как и в первых двух 19. Складываем. 19+20+19=58.
Второй, гибкий. Сумма двух чисел делится на число n, если сумма остатков от деления на n этих чисел равна самому n либо 0 (из теории чисел). Известно, что у 20-гранника 20 возможных "чисел". 7 мы получаем из 1+6,2+5,3+4 и инверсий этих групп. Сколько чисел присутствует в 20, при сложении остатков которых мы получим 7? Вот 7+0. Остаток 7 невозможен, поэтому берем просто 0+0. Это у нас 7 и 14 для обоих случаев, т.е. 2*2=4.
Для начала 6+1. Для первого: 6, 13, 20. Для второго: 1, 8, 15. 3*3=9. Затем 5+2. Для первого 5, 12, 19. Для второго: 2, 9, 16, 3*3=9 Далее 4+3. Для первого: 4, 11, 18. Для второго: 3, 10, 17. 3*3=9 3+4. Первое: те самые 3, 10, 17. Второе, понятно, 4, 11, 18. 3*3=9 2+5: 1) 2, 9, 16, 2) 5, 12, 19. 3*3=9 1+6: 1) 1, 8, 15, 2) 6, 13, 20 3*3=9 0+7 (было уже как 0+0). (вообще, из этого можно было установить закономерность и не высчитывать все). 9*6+4=58.
#include <iostream>
using namespace std;
int main()
{
int a, b;
cout << "a = ", cin >> a;
cout << "b = ", cin >> b;
for (int i=a; i<=b; i++) {
cout << i << " ";
}
return 0;
}
Пример:
a = 5
b = 12
5 6 7 8 9 10 11 12
2.
#include <iostream>
using namespace std;
int main()
{
int a, b, s=0;
long long p=1;
cout << "a = ", cin >> a;
cout << "b = ", cin >> b;
for (int i=a; i<=b; i++) {
p = p*i;
s = s+i;
}
cout << "p = " << p << " s = " << s;
return 0;
}
Пример:
a = 5
b = 12
p = 19958400 s = 68