e-olymp 263. Три единицы

Задача

Вычислить количество последовательностей длины $n,$ состоящих только из нулей и единиц, в которых не встречается три единицы подряд.

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

Длина последовательностей $n$ $\left ( 1 \leq n \leq 10^{5} \right ).$

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

Вывести количество искомых последовательностей по модулю $12345.$

Тесты

Входные данные Выходные данные
$1$ $2$
$4$ $0$
$263$ $10159$
$10000$ $8872$

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

Решение

Объявим массив $f,$ в котором будем сохранять значения $f(1), f(2),\dots, f(n).$ Далее читаем входные данные и заносим в соответствующие ячейки массива $f$ значения $f(1), f(2)$ и $f(3).$ Вычисляем значения $f(i)$ по рекуррентной формуле $f(n) = f(n – 1) + f(n – 2) + f(n – 3).$
Эту формулу получили так: сперва обозначили через $f(n)$ количество искомых последовательностей из $0$ и $1$ длины $n.$ Далее мы смотрим, если на первом месте последовательности будет находиться $0,$ то начиная со второго места можно построить $f(n – 1)$ последовательность. Если на первом месте стоит $1,$ то на втором месте возможны оба варианта. Если там стоит $0,$ то на следующих $n – 2 $свободных местах можно построить $f(n – 2)$ последовательности. Если $1,$ то на третьем месте обязательно должен находиться $0$ и начиная с четвертого места можно построить $f(n – 3)$ последовательности.
Вычисления значения $f(i)$ производим по модулю $12345.$ В результате выводим количество искомых последовательностей по модулю.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olymp 165. Симметрия

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

 

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]10[/latex] [latex]2[/latex]
2 [latex]116[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]1[/latex]
4 [latex]454[/latex] [latex]2[/latex]
5 [latex]12301230[/latex] [latex]2[/latex]

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

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

А137б

Задача

Даны натуральное [latex]n[/latex], действительные числа [latex]a_{1},\ldots,a_{n}[/latex]. Вычислить: [latex]a_{1}^{2},a_{1}a_{2},\ldots,a_{1}a_{n}[/latex]

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

Натуральное [latex]n[/latex], действительные числа [latex]a_{1},\ldots,a_{n}[/latex].

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

[latex]a_{1}^{2},a_{1}a_{2},\ldots,a_{1}a_{n};[/latex]

Тесты

Входные данные Выходные данные
6 4 -2 1.5 3 7 9 16 -8 6 12 28 36
12 7 5 -1 2.7 5 49 35 -7 18.9 35

Решение

Для решения этой задачи воспользуемся циклом for . Сначала прочитаем n . После этого прочитаем первую переменную и напечатаем ее квадрат. Далее в цикле будем cчитывать остальные $latex n$ переменных и выводить их произведения на первую переменную.

Пример работы программы можно увидеть на ideone.

MLoops 17

Задача

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

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

Тесты

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

m n k
13 31 9

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

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

m n k
5 8 4


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

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

m n k
20 20 3

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

Алгоритм

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

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

Ссылка на Ideone

http://ideone.com/9QGk0A

А136и

Задача: Даны натуральное число n, действительные числа [latex]k_{1}, k_{2}, \dots, k_{n}[/latex] Вычислить [latex]\frac{k_{1}}{0!} + \frac{k_{2}}{1!} + \dots + \frac{k_{n}}{(n-1!)} [/latex]

Тесты

Число-n Действительные числа Результат
5 4 5 6 7 8 13,5
7 5 4 7 9 2 8 3 14,1542
3 6 9 3 16,5

Код:

Решение:

  1. Вводим n, k (действительные числа);
  2. Получаем очередное действительное число k.
  3. Делим на факториал и суммируем;

Решение на Ideone

А165г. Среднее геометрическое

Задача:
Даны действительные числа [latex]a_{1}, a_{2},\ldots[/latex] .
Известно, что [latex]a_{1} > 0,[/latex] и что среди [latex]a_{2}, a_{3},\ldots[/latex] есть хотя бы одно отрицательное число.
Пусть [latex]a_{1},\ldots,a_{n}[/latex] — члены данной последовательности, предшествующие первому отрицательному члену([latex]n[/latex] заранее неизвестно)
Получить:
г) среднее геометрическое [latex]a_{1},\ldots,a_{n}[/latex].

Тесты:

Последовательность Среднее геометрическое
3 6 8 -9 4 5 5.24
13 14 1 4 5 6 -8 1 12 5.29
2 -3 4 2.00
2 2 2 -3 2 3 4 5 2.00
79 3 0.05 2.28

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

Алгоритм:

Считывать числа с потока ввода. Умножаем числа пока не встретится отрицательное. После чего извлекаем корень используя данные счетчика.
Формула для нахождения Среднего геометрического : [latex]a_{gm} = \sqrt[n]{a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}[/latex] Рабочий код на ideone.com

А137е

Даны натуральные [latex]n[/latex], действительные [latex]a_1,\ldots, a_n[/latex].

Вывести: [latex]a_1+1!, a_2 +2!,\ldots, a_n+n![/latex].

Тесты:

n a1 a2 a3 a4
4 1 2 3 4 Output 2 4 9 28
4 0.1 0.2 0.3 0.4 Output 1.1 2.2 6.3 24.4

 

www.ideone.com

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл for, от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.