e-olymp 1868. Функция

Условие задачи
Вычислите функцию:
$$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$$
Входные данные
Одно натуральное число $n$ $(1 \leq n \leq 10^{12})$
Выходные данные
Значение $f(n)$ , взятое по модулю $2^{32}$.
Тесты

Входные данные Выходные данные
10
7
123
229966
1
1
100
136345
51
5092

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

Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами.Далее, по условию, мы пишем наконец нашу функцию:

  • Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
  • Если есть значение с таким же ключом, то оно возвращает значение.
  • Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение $f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)$.
  • Во всех остальных случаях наша функция возвращает значение $f(n-1)+f(n-3)$.

Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 1489. Шоколад

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленькихшоколадных долек — прямоугольников $2 \cdot 1$.       

Петя делит шоколадку на две части, разламывая ее вдоль некоторой прямой, параллельной одному из краев шоколадки. Ни Петя, ни Маша не любят ломаные дольки, поэтому Петя хочет разломать шоколадку так, чтобы ни одна долька не была повреждена.

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные Выходные данные
2 3
1 1 2
3 3 2
Yes
5 6
1 2 2 3 3 4
1 5 6 7 7 4
8 5 6 9 10 10
8 11 11 9 12 13
14 14 15 15 12 13
No
4 7
1 1 2 5 8 11 6
2 14 4 7 3 9 5
3 7 10 6 13 2 3
4 3 8 12 5 7 7
Yes

Код решения

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true и false в обратном случае.Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа boolean. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Ссылка на E-olymp
Ссылка на решение

e-olymp 2214. Функция 9

Задача

Дана функция, аргументы которой — произвольные натуральные числа
$$f(M, N)=\begin{cases}
f(M-N, N), & \text{ npu } M>N \\
N, & \text{ npu } M=N \\
f(N-M, M), & \text{ npu } N>M
\end{cases}$$
Составить алгоритм (написать программу), вычисляющий значение функции.

Вводные данные

Два натуральных числа $n$ и $m$ $(1\leq n, m \leq 10^{18}).$

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

Искомое значение функции.

Тесты

Входные данные Выходные данные
$6$ $3$ $3$
$12$ $12$ $12$
$126$ $98$ $98$
$10329$ $1501$ $1501$
$1008359$ $15113$ $15113$

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

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

Для решения задачи напишем функцию f. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того, что больше $n$ или $m$). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n \mod m = 0$ или $m \mod n = 0,$ то функция возращает в переменную искомое значение). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 2262. Явная формула

h1>Задача

Дано 10 булевых переменных [latex] x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10} [/latex]. Вычислите количество пар и троек, у которых хотя бы одна переменная установлена в [latex]1[/latex]. Установим [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}) = 1[/latex] если это количество нечетно и [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}) = 0[/latex] если количество четно.
Рассмотрим явную формулу, которая реализует функцию [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}):[/latex] [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}) = [/latex] [latex] \left( x_{1}\vee x_{2} \right) \oplus \left( x_{1}\vee x_{3} \right) \oplus \left( x_{1}\vee x_{4} \right)\oplus \left( x_{1}\vee x_{5} \right)
\oplus \left( x_{1}\vee x_{6} \right) \oplus \left( x_{1}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{8} \right) \\
\oplus \left( x_{1}\vee x_{9} \right) \oplus \left( x_{1}\vee x_{10} \right) \oplus \left( x_{2}\vee x_{3} \right)
\oplus \left( x_{2}\vee x_{4} \right) \oplus \left( x_{2}\vee x_{5} \right) \oplus \left( x_{2}\vee x_{6} \right) \\
\oplus \left( x_{2}\vee x_{7} \right) \oplus \left( x_{2}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{9} \right)
\oplus \left( x_{2}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{4} \right) \oplus \left( x_{3}\vee x_{5} \right) \\
\oplus \left( x_{3}\vee x_{6} \right) \oplus \left( x_{3}\vee x_{7} \right) \oplus \left( x_{3}\vee x_{8} \right)
\oplus \left( x_{3}\vee x_{9} \right) \oplus \left( x_{3}\vee x_{10} \right) \oplus \left( x_{4}\vee x_{5} \right) \\
\oplus \left( x_{4}\vee x_{6} \right) \oplus \left( x_{4}\vee x_{7} \right) \oplus \left( x_{4}\vee x_{8} \right)
\oplus \left( x_{4}\vee x_{9} \right) \oplus \left( x_{4}\vee x_{10} \right) \oplus \left( x_{5}\vee x_{6} \right) \\
\oplus \left( x_{5}\vee x_{7} \right) \oplus \left( x_{5}\vee x_{8} \right) \oplus \left( x_{5}\vee x_{9} \right)
\oplus \left( x_{5}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{7} \right) \oplus \left( x_{6}\vee x_{8} \right) \\
\oplus \left( x_{6}\vee x_{9} \right) \oplus \left( x_{6}\vee x_{10} \right) \oplus \left( x_{7}\vee x_{8} \right)
\oplus \left( x_{7}\vee x_{9} \right) \oplus \left( x_{7}\vee x_{10} \right) \oplus \left( x_{8}\vee x_{9} \right) \\
\oplus \left( x_{8}\vee x_{10} \right) \oplus \left( x_{9}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{3} \right)
\oplus \left( x_{1}\vee x_{2}\vee x_{4} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{5} \right) \\ \oplus \left( x_{1}\vee x_{2}\vee x_{6} \right)
\oplus \left( x_{1}\vee x_{2}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{8} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{9} \right)
\oplus \\ \left( x_{1}\vee x_{2}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{4} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{5} \right)
\oplus \left( x_{1}\vee x_{3}\vee x_{6} \right) \oplus \\ \left( x_{1}\vee x_{3}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{3}\vee x_{9} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{4}\vee x_{5} \right) \\
\oplus \left( x_{1}\vee x_{4}\vee x_{6} \right) \oplus \left( x_{1}\vee x_{4}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{4}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{4}\vee x_{9} \right) \oplus \\ \left( x_{1}\vee x_{4}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{5}\vee x_{6} \right)
\oplus \left( x_{1}\vee x_{5}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{1}\vee x_{5}\vee x_{9} \right) \\
\oplus \left( x_{1}\vee x_{5}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{6}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{6}\vee x_{9} \right) \\ \oplus \left( x_{1}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{7}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{7}\vee x_{9} \right) \oplus \left( x_{1}\vee x_{7}\vee x_{10} \right) \oplus \\ \left( x_{1}\vee x_{8}\vee x_{9} \right)
\oplus \left( x_{1}\vee x_{8}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{2}\vee x_{3}\vee x_{4} \right)
\oplus \left( x_{2}\vee x_{3}\vee x_{5} \right) \\ \oplus \left( x_{2}\vee x_{3}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{3}\vee x_{7} \right)
\oplus \left( x_{2}\vee x_{3}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{3}\vee x_{9} \right) \oplus \\ \left( x_{2}\vee x_{3}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{4}\vee x_{5} \right) \oplus \left( x_{2}\vee x_{4}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{4}\vee x_{7} \right)
\oplus \left( x_{2}\vee x_{4}\vee x_{8} \right) \\ \oplus \left( x_{2}\vee x_{4}\vee x_{9} \right) \oplus \left( x_{2}\vee x_{4}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{4}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{7} \right) \\
\oplus \left( x_{2}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{9} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{2}\vee x_{6}\vee x_{8} \right) \\ \oplus \left( x_{2}\vee x_{6}\vee x_{9} \right)
\oplus \left( x_{2}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{2}\vee x_{7}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{7}\vee x_{9} \right)
\oplus \left( x_{2}\vee x_{7}\vee x_{10} \right) \\ \oplus \left( x_{2}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{2}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{5} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{6} \right) \\
\oplus \left( x_{3}\vee x_{4}\vee x_{7} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{8} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{9} \right)
\oplus \left( x_{3}\vee x_{4}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{5}\vee x_{6} \right) \\ \oplus \left( x_{3}\vee x_{5}\vee x_{7} \right)
\oplus \left( x_{3}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{3}\vee x_{5}\vee x_{9} \right) \oplus \left( x_{3}\vee x_{5}\vee x_{10} \right)
\oplus \left( x_{3}\vee x_{6}\vee x_{7} \right) \\ \oplus \left( x_{3}\vee x_{6}\vee x_{8} \right) \oplus \left( x_{3}\vee x_{6}\vee x_{9} \right)
\oplus \left( x_{3}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{7}\vee x_{8} \right) \\ \oplus \left( x_{3}\vee x_{7}\vee x_{9} \right)
\oplus \left( x_{3}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{3}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{3}\vee x_{9}\vee x_{10} \right) \\ \oplus \left( x_{4}\vee x_{5}\vee x_{6} \right) \oplus \left( x_{4}\vee x_{5}\vee x_{7} \right)
\oplus \left( x_{4}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{4}\vee x_{5}\vee x_{9} \right) \oplus \left( x_{4}\vee x_{5}\vee x_{10} \right) \\
\oplus \left( x_{4}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{4}\vee x_{6}\vee x_{8} \right) \oplus \left( x_{4}\vee x_{6}\vee x_{9} \right)
\oplus \left( x_{4}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{4}\vee x_{7}\vee x_{8} \right) \\ \oplus \left( x_{4}\vee x_{7}\vee x_{9} \right)
\oplus \left( x_{4}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{4}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{4}\vee x_{8}\vee x_{10} \right) \\
\oplus \left( x_{4}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{5}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{5}\vee x_{6}\vee x_{8} \right)
\oplus \left( x_{5}\vee x_{6}\vee x_{9} \right) \oplus \left( x_{5}\vee x_{6}\vee x_{10} \right) \\ \oplus \left( x_{5}\vee x_{7}\vee x_{8} \right)
\oplus \left( x_{5}\vee x_{7}\vee x_{9} \right) \oplus \left( x_{5}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{5}\vee x_{8}\vee x_{9} \right)
\oplus \left( x_{5}\vee x_{8}\vee x_{10} \right) \\ \oplus \left( x_{5}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{7}\vee x_{8} \right)
\oplus \left( x_{6}\vee x_{7}\vee x_{9} \right) \oplus \left( x_{6}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{8}\vee x_{9} \right) \\
\oplus \left( x_{6}\vee x_{8}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{6}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{6}\vee x_{9}\vee x_{10} \right) \\ \oplus \left( x_{7}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{7}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{7}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{8}\vee x_{9}\vee x_{10} \right) \\
[/latex]

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

Содержит [latex]10[/latex] чисел [latex] x_{1},\ x_{2},\ x_{3} ,\ x_{4},\ x_{5},\ x_{6},\ x_{7},\ x_{8},\ x_{9},\ x_{10} [/latex]. Каждое из них равно [latex]0[/latex] или [latex]1[/latex].

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

Вывести единственное значение [latex]f( x_{1}, \ x_{2},\ x_{3} ,\ x_{4},\ x_{5},\ x_{6},\ x_{7},\ x_{8},\ x_{9},\ x_{10}).[/latex]

Тесты

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

Решение

Рассмотрим все возможные пары и тройки разных переменных из этих десяти (всего существует [latex]45[/latex] пар и [latex]120[/latex] троек). Данная формула реализует функцию [latex]f( x_{1},\ x_{2},\ x_{3} ,\ x_{4},\ x_{5},\ x_{6},\ x_{7},\ x_{8},\ x_{9},\ x_{10}) [/latex]. В указанной формуле бинарные операции обозначаются «[latex]\vee[/latex]» и «[latex]\oplus[/latex]», где «[latex]\vee[/latex]» — логическое или , а «[latex]\oplus[/latex]» — исключающее или

Ссылки

e-olymp
Ideone

e-olymp 2999. Функция — 10

Задача

Дана функция, аргументы которой – неотрицательные целые числа [latex]m[/latex] и [latex]n[/latex] [latex](m \leqslant n):[/latex]

$$f(m,n)=\begin{cases} 1, \text{ npu } m=0 \\\\ f(m-1,n-1)+f(m,n-1), \text{ npu } 0<m<n \\\\ 1, \text{ npu } m=n \end{cases}$$

Вычислить значение функции.

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

Два целых неотрицательных числа [latex]n[/latex] и [latex]m[/latex] [latex](0 \leqslant n, m \leqslant 20).[/latex]

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

Выведите искомое значение заданной функции [latex]f(m, n).[/latex]

Тесты

# Входные данные Выходные данные
1 4 2 6
2 7 7 1
3 12 0 1
4 15 5 3003
5 10 6 210

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

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

Для того, чтобы решить задачу, нам необходимо составить алгоритм, который будет вычислять значение заданной функции в зависимости от значения её аргументов. Для этого создадим специальную функцию func().
Строки 16 — 19 кода составляют тело функции. Программа выбирает, какую операцию ей нужно выполнить, в зависимости от определенного условия:

  1. Если [latex]m = 0[/latex] или [latex]m = n[/latex], то программа возвращает единицу.
  2. Если [latex]m < n[/latex], то программа вычисляет значение функции по формуле [latex]f(m-1,n-1)+f(m,n-1)[/latex]

Затем в главной функции вызываем нашу вспомогательную функцию func() с помощью новой переменной [latex]d[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

А58а

Задача. Дано действительное число a. Для функции f\left(x \right), график которой изображен, вычислить f\left(a \right).

58a

Для решения данной задачи требуется лишь проверка знака числа a. Если a> 0, то f\left(a \right) вычисляется как -a^{2}, а если a< 0, то f\left(a \right) равна  -a. При a=0f\left(a \right)=0.

Код на Ideone.

Тест

 Входные данные  Выходные данные
 -7 7
 7  -49
 0  0