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

Задача

Дана функция, аргументы которой — произвольные натуральные числа

[latex]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}[/latex]

Составить алгоритм (написать программу), вычисляющий значение функции.

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

Два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 \le n, m \le 10^{18})[/latex].

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

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

Тесты

Входные данные Выходные данные
[latex]6[/latex] [latex]3[/latex] [latex]3[/latex]
[latex]12[/latex] [latex]12[/latex] [latex]12[/latex]
[latex]126[/latex] [latex]98[/latex] [latex]98[/latex]
[latex]10329[/latex] [latex]1501[/latex] [latex]1501[/latex]
[latex]1008359[/latex] [latex]15113[/latex] [latex]15113[/latex]

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

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

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

Ссылки

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

e-olymp 16. Дракон

У каждой [latex]S[/latex]-ножки [latex]1[/latex] голова. Найти количество ног [latex]N[/latex] у [latex]K[/latex]-главого дракона, если у всех вместе [latex]A[/latex] голов и [latex]B[/latex] ног.

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

4 числа: [latex]S[/latex], [latex]K[/latex], [latex]A[/latex], [latex]B[/latex]. Все числа не превышают [latex]1000[/latex].

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

Количество ног у дракона. Если входные данные противоречивы, вывести [latex]-1[/latex], в случае наличия нескольких решений – вывести любое из них.

Задача взята с сайта e-olymp.

Тесты

[latex]S[/latex] [latex]K[/latex] [latex]A[/latex] [latex]B[/latex] [latex]N[/latex] Комментарий
4 7 35 36 2 7 многоножек и 4 2-ногих дракона
10 3 10 34 8 1 многоножка и 3 8-ногих дракона
44 17 37 132 0 3  многоножки и 2 0 — ногих дракона
4 19 42 42 13 4 многоножки и 2 13 — ногих дракона
1 0 1 1 0 1 многоножка и 1 0 — ногий дракон
5 8 3 6 -1 Количество голов в сумме меньше чем у одного дракона
5 17 6 2 -1 Количество ног в сумме меньше чем у одной многоножки

Алгоритм

Для начала введем несколько дополнительных параметров. Обозначим количество имеющихся драконов через [latex]D[/latex], а количество многоножек как [latex]M[/latex]. Внесем имеющиеся данные в таблицу для удобства построения решения.

Дракон Многоножка
 Один Несколько  Одна  Несколько
 Голов Ног  Голов Ног Голов  Ног  Голов  Ног
[latex]K[/latex] [latex]N[/latex] [latex]KD[/latex] [latex]ND[/latex] [latex]1[/latex] [latex]S[/latex] [latex]M[/latex] [latex]SM[/latex]

Воспользуемся полученной таблицей и промоделируем сложившуюся ситуацию в виде системы уравнений:
[latex] \left\{\begin{matrix}
KD + M = A & \\
ND + SM = B &
\end{matrix}\right.[/latex]

Выразим из первого уравнения количество многоножек и подставим во второе уравнение:
[latex] \left\{\begin{matrix}
A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex]

Раскрыв скобки, преобразуем выражение во втором уравнении:
[latex] \left\{\begin{matrix}

A — KD = M & \\
B — SA = D(N — SK) &
\end{matrix}\right.[/latex]

Теперь мы можем выразить количество драконов:
[latex] \left\{\begin{matrix}

A — KD = M & \\
\frac{B — SA}{N — SK} = D &
\end{matrix}\right.[/latex]

Учитывая тот факт, что мы работаем не просто с системой уравнений, а с величинами имеющими определенный логический смысл, проведем анализ полученного результата:

  1. [latex]D[/latex] — количество драконов, следовательно, это положительное целое число.
  2. Выполняя деление мы предполагаем, что [latex]N — SK[/latex] [latex]\neq[/latex] [latex]0[/latex]. Следует проверить имеет ли данный случай смысл и решение в контексте условия задачи.
    Вернемся к системе считая, что  [latex]N = SK[/latex]:
    [latex] \left\{\begin{matrix}A — KD = M & \\
    ND + S(A — KD) = B &
    \end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
    SKD + SA — SKD = B &
    \end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
    SA = B &
    \end{matrix}\right.[/latex] Приходим к выводу, что, при условии [latex]SA = B[/latex], задача гарантировано имеет решение вида [latex]N = SK[/latex].
  3. Теперь оценим знак полученного нами выражения:
    [latex]\frac{B — SA}{N — SK}[/latex] [latex]> 0[/latex] [latex] \Rightarrow[/latex] [latex](B — SA > 0[/latex] [latex]\wedge[/latex] [latex]N — SK > 0)[/latex]  [latex]\vee[/latex] [latex](B — SA < 0[/latex] [latex]\wedge[/latex] [latex]N — SK < 0)[/latex].
    Оценим значение [latex]B — SA [/latex]:
    [latex]B — SA = ND +SM — SA = ND +S(M — A) [/latex] [latex]M[/latex] — количество голов у одной многоножки, [latex]A[/latex] — общее количество голов [latex] \Rightarrow[/latex] [latex]M — A <= 0[/latex] , делаем вывод, что
    [latex]B — SA <= 0[/latex]  [latex]\forall[/latex] [latex]B, S, A[/latex] [latex] \Rightarrow[/latex] [latex]N — SK <= 0[/latex] [latex] \Rightarrow[/latex] [latex]N <= SK [/latex]

Анализ условия задачи окончен. Перейдем к реализации решения, принимая во внимание все  условия и ограничения полученные в процессе размышлений.
Запустим цикл от [latex]0[/latex] до [latex]SK[/latex] (выполнять цикл далее не имеет смысла, так как там не будет найдено ни одного решения), который перебирает количество ног дракона. Объединим все получившиеся ограничения:

  1. Прежде всего выполняем проверку для избежания деления на [latex]0[/latex]. (Условие проверки : [latex]SA = B[/latex]  [latex] \Rightarrow[/latex]  выводим результат [latex]N = SK [/latex] и заканчиваем работу программы).
  2. Иначе выполняем ряд последовательных проверок для текущего [latex]N[/latex] в цикле:
    • [latex]\frac{B — SA}{N — SK}[/latex] — целая величина. (Условие проверки : [latex]B — SA[/latex] делится нацело на [latex]N — SK[/latex])
    • Количество ног драконов не превышает общее количество ног минус количество ног одной многоножки (имеется хотя бы одна многоножка, которая имеет [latex]S[/latex] ног). (Условие проверки: [latex]B — S >= DN[/latex])
    • Количество голов драконов меньше чем общее количество голов (имеется хотя бы [latex]1[/latex] многоножка с [latex]1[/latex] головой). (Условие проверки: [latex]A > DK[/latex])

Как только выполняются все вышеописанные условия из пункта 2, выполняем вывод текущего количества ног дракона и заканчиваем работу программы, в противном случае выводим [latex]-1[/latex], так как данные противоречивы.

Примечание: в ходе решения выяснилось, что автор задачи предполагает существование 0 — ногих драконов, 0 — ногих многожек и т.д. Эти условия повлияли на вид некоторых неравенств.

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

Код программы
Засчитанное решение