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

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

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

Related Images: