e-olymp 1210. Очень просто!!!

Задача

По заданным числам [latex]n[/latex] и [latex]a[/latex] вычислить значение суммы: [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex]

Входные данные

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

Выходные данные

Значение суммы. Известно, что оно не больше [latex]10^{18}[/latex].

Тесты

Входные данные Выходные данные
3 3 102
4 4 1252
9 3 250959
7 14 785923166
1009 1 509545

Код программы

Решение задачи

Данную задачу можно решить прямым линейным вычислением значений элементов заданного ряда, то есть получать значение элемента ряда с индексом [latex]i[/latex] умножением [latex]a[/latex] (которое необходимо возвести в степень [latex]i[/latex]) на индекс [latex]i[/latex] и накапливать сумму этих значений в выделенной переменной.
Но безусловно такое решение не является качественным (даже если будет использован алгоритм бинарного возведения в степень).

Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex] Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.

Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.

Ссылки

MLoops 18

Александр Димитриев
Александр Димитриев

Latest posts by Александр Димитриев (see all)

Условие

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк).

1123581321345589144233377
1235813213455891442333776
2358132134558914423337761
3581321345589144233377610
5813213455891442333776109

Входные данные

В одной строке задано два числа [latex]n[/latex] и [latex]m[/latex].

Выходные данные

Вывести таблицу размерностью [latex]n\times m[/latex].

Тесты

Входные данные Выходные данные
1 1  1
2 2  
5 5
9 18
25 5

Код

Решение

Несложно догадаться что данная последовательность чисел это числа Фибоначчи. Для того чтобы построить таблицу надо сначала найти числа Фибоначчи (у меня это — [latex]a,b,c[/latex]), после печатаем их в строку далее переходим на новую строку и начинаем со 2 элемента относительно предыдущей строки это выполняет функция [latex]h[/latex], и так пока [latex]i \le m[/latex]. Но может возникнуть проблема с выходом за предел строки и для того чтобы этого не произошло нам нужны функции [latex]f[/latex], которая возводит 10 в заданную степень, это нам надо чтобы отрезать то что выходит за предел строки, для этого используем целочисленное деление на 10 в нужной степени,  и [latex]g[/latex], которая считает количество цифр в данном числе Фибоначчи, для того чтобы определить в какую степень нам надо возвести 10, чтобы оставить только ту часть что не выходит за предел строки.
Код программы

MLoops12

Станислав Коциевский
Станислав Коциевский

Latest posts by Станислав Коциевский (see all)

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел n > 0 (количество столбцов) и m > 0 (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.
Замечание 2. Многоточие означает продолжение последовательности
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться  Онлайн-энциклопедией целочисленных последовательностей.

 

Тесты

n m k Результат
15 9 4
 10  7  3
 12  5  2
 25  15  7

 

Код программы

Решение

Закономерности в таблице

  1. Через каждые [latex]k[/latex] строк, начиная с нулевой, встречается строка, в которой нулевой и каждый [latex]k[/latex]-й символы — «+», а остальные — «-«. Такие строки разделяют одинаковые [latex]k[/latex]-местные блоки строк.
  2. Каждая строка блока строк содержит, в свою очередь, [latex]k[/latex]-местные блоки символов (эти блоки уже разные), разделенные символами «|». В каждой строке из блока два вида блоков символов (далее блок 1 и блок 2). Все нечетные блоки имеют вид блока 1, четные — блока 2.
  3. Блок 1 содержит числа по возрастанию, начиная с номера строки в блоке строк, до [latex]k[/latex] включительно, т.е. числа из сегмента [latex][i ; k][/latex], где [latex]i[/latex] — номер строки в блоке строк. После них в блоке записаны числа от [latex]1[/latex]  до номера строки в блоке, не включая сам этот номер, т.е. числа из полусегмента [latex][1 ; i)[/latex].
  4. Блок 2 каждой строки содержит те же числа, что и блок 1, но записанные в противоположном порядке.

Реализация

Программа содержит один большой цикл, перебирающий строки. Причем, этот цикл содержит 2 счетчика строк — один считает номер текущей строки в таблице, а второй — в блоке строк. В этот цикл вложен цикл, перебирающий блоки, а в нем, в свою очередь, цикл, записывающий блок. Чтобы цикл вывода блоков символов (строк) не выводил лишние символы (строки), выводящие символы (строки) циклы, которые находятся внутри них, должны содержать проверку не только на окончание блока, но и на окончание таблицы (само собой, циклы, выводящие блоки тоже имеют проверку на конец таблицы).

ссылка на код на ideone

MLoops 11

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел n > 0 (количество столбцов) и m > 0(количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.
Замечание 2. Многоточие означает продолжение последовательности.                            Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

Входные данные:

Три числа: количество столбцов и строк, параметр [latex]k[/latex].

Выходные данные:

Код программы:
Решение:

Для построения данной таблицы нужно найти закономерность чередования символов в таблице. Решение данной задачи можно осуществить с помощью двух циклов. Первый отвечает за строки, а второй — за столбцы. Пусть нумерация строк и столбцов начинается с нуля. Тогда, если номер строчки нацело делится на [latex](k+1)[/latex], то рассматриваем столбцы этой строчки. Если номер столбца нацело делится на [latex](k+1)[/latex], то записываем «+», иначе «-«. Если номер строки не делится нацело на [latex](k+1)[/latex], а номер столбца в этой строке — делится, то записываем «|». Если номер строки и столбца не делятся нацело на [latex](k+1)[/latex], то создаем переменную, с помощью которой будем заполнять таблицу цифрами. Так как, каждый столбик и каждая строка имеют свой номер, то с помощью нахождения суммы остатка от деления строки и столбца на [latex](k+1)[/latex] будем находит значение элемента, стоящего на пересечении [latex]i- [/latex]ой строки и [latex]i-[/latex]ого столбца, но этого не достаточно, в таблице есть перестановка, чтобы ее реализовать отнимаем от суммы единицу, делая этим сдвиг вправо. Также от полученного результата нужно найти остаток от деления на параметр [latex]k[/latex] для того, чтобы выполнялась правильная последовательность символов. Если результат вычисления переменной равен нулю, то записываем значение параметра [latex]k[/latex], иначе — результат вычисления переменной.

Тесты:

m n k

Выходные данные:

5 5 10  
 14 13  5  
 9  7  5  
 17  30 7  

 

 

Код программы на ideone.com

MLoops 16

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0[/latex]  (количество столбцов) и [latex]m>0[/latex] (количество строк).

123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231

 

Тесты

[latex]m[/latex]    [latex]n[/latex]
4    3 123

231

132

123

8    8 12312312
23123123
13213213
12312312
23123123
13213213
12312312
23123123
 10    27 123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123

 

Код программы

 

ideone.com

Решение

Пронумеруем строки от  [latex]1[/latex]  до  [latex]m[/latex] , столбцы — от  [latex]1[/latex]  до  [latex]n[/latex].

1 2 3 4 5 6 7 n
1 1 2 3 1 2 3 1
2 2 3 1 2 3 1 2  …
3 1 3 2 1 3 2 1
4 1 2 3 1 2 3 1  …
5 2 3 1 2 3 1 2  …
6 1 3 2 1 3 2 1  …
7 1 2 3 1 2 3 1  …  …
 …  …  …  …
m  …  …  …  …

 

Положение символа  [latex]2[/latex] определяется однозначно для всей таблицы [latex]\left (n+m \right )\vdots 3[/latex]. В столбцах, где [latex]n\vdots 3[/latex], положение символа [latex]1[/latex]  —  [latex]\left ( n+m+1 \right )\vdots 3[/latex] , на оставшихся свободных местах — символ [latex]3[/latex] . В столбцах, где [latex]\left ( n-1\right )\vdots 3[/latex], на свободных местах стоит символ [latex]1[/latex]. В оставшихся столбцах на свободных местах стоит символ [latex]3[/latex].

MLoops 17

Павел Загинайло
Павел Загинайло

Latest posts by Павел Загинайло (see all)

Задача

Найти закономерность и написать программу, которая выводит аналогичную таблицу для любых чисел n>0 (количество столбцов) и m>0 (количество строк).

Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.

Тесты

Входные данные Выходные данные
m n  k
13 31 9
5 8 4
20 20 3

 

 

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’.  Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +.  Далее проверяем, делится ли номер столбца,  уменьшенный на 1, на число [latex]k+1[/latex], где [latex]k[/latex] — вводимый параметр. Во всех остальных случаях пишем ‘.’.

Код программы

Код программы на ideone.com