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

Условие:

В некотором царстве жил Змей Горыныч. У него было [latex]N[/latex] голов и [latex]M[/latex] хвостов. Иван-царевич решил уничтожить губителя человеческих душ, для чего ему его кума Баба Яга подарила волшебный меч, так как только им можно убить Змея Горыныча. Если отрубить одну голову, то на её месте вырастает новая, если отрубить хвост, то вместо него вырастет 2 хвоста. Если отрубить два хвоста, то вырастает 1 голова, и только когда отрубить 2 головы, то не вырастет ничего. Змей Горыныч гибнет только в том случае, когда ему отрубить все головы и все хвосты. Определить минимальное количество ударов мечом, нужное для уничтожения Змея Горыныча.

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

Два числа [latex]N[/latex], [latex]M[/latex] ([latex]0[/latex] [latex]<=[/latex][latex]N[/latex], [latex]M[/latex][latex]<=[/latex][latex]1000[/latex]).

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

Единственное число – минимальное количество ударов мечом, или -1, если уничтожить Змея Горыныча невозможно.

Тесты:

Решение

Описание решения:

При решении данной задачи было рассмотрено несколько случаев.

• Змея Горыныча убить невозможно. Это возможно только в том случае, когда у него нечетное количество голов, и нет ни одного хвоста, так как при наличии хотя бы одного хвоста становится возможным увеличение количества хвостов и голов до необходимого, путем отрубания одного, или двух хвостов соответственно. Чтобы определить возможность уничтожения Змея, делаем проверку: если количество голов нечетное и хвостов нет, то выводим «-1». Если эти условия не выполняются, то переходим ко второму пункту решения.
• Змей Горыныч может быть убит. Это означает, что у Змея есть хотя бы один хвост, или четное количество голов. В таком случае, мы работаем внутри цикла, при каждом проходе которого проверяется, выполняются ли описанные выше условия:
  
  C++

  while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

  13	while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

  Горыныча можно убить тогда и только тогда, когда при отрубании всех хвостов получается четное количество голов. Отсюда, необходимо, чтобы у Змея было четное количество хвостов, и сумма голов и количества хвостов, деленного на два, была четным числом. Поэтому будем работать по простому алгоритму:

1. Если количество хвостов [latex]M[/latex] нечетное, то отрубаем один хвост, на месте которого вырастает два новых, и увеличиваем счетчик ударов [latex]count[/latex] на один.
2. Если количество голов нечетное, и хвостов больше одного, то отрубаем два хвоста, тем самым увеличивая количество голов на 1, и увеличиваем счетчик.
3. Если количество голов и хвостов четное, и если количество хвостов при делении на два дает четное число, то мы увеличиваем счетчик на  [latex]M/2+((N+M/2)/2)[/latex], и приравниваем количество голов и хвостов нулю.
4. Если какое-то из условий пункта 3 не выполняется, то увеличиваем количество хвостов на 1, и увеличиваем счетчик ударов.
5. Повторяем алгоритм до тех пор, пока не убьем Горыныча.

После выхода из цикла в счетчике [latex]count[/latex] находится минимальное число ударов, необходимое для уничтожения Змея Горыныча. Выводим его на экран, и переходим на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Для перехода к странице на e-olimp с полностью выполненным данным заданием щелкните здесь.

Related Images: