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 — ногих многожек и т.д. Эти условия повлияли на вид некоторых неравенств.

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

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

One thought on “e-olymp 16. Дракон

  1. Зачтено. Очень хороший анализ.

    Кстати, Вы столкнулись с уравнениями решение которых приходится искать во множестве целых чисел. Такие уравнения называют диофантовыми. В Вашем случае получается линейное диофантово уравнение с двумя неизвестными (число ног у дракона и число драконов). Для его решения существует очень эффективный и простой алгоритм — расширенный алгоритм Евклида.
    Когда (если) будет свободное время, попробуйте сделать ещё одно решение. Сравним эффективность.

Добавить комментарий