Решение задачи Змей Горыныч с Acmp

С пояснением   Просмотров: 86


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


Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m, k = 0;
    cin >> n >> m;
    if(n % 2 && m == 0){
        cout << -1;
        return 0;
    }
    while(m % 2 != 0 || (n + m/2) % 2 != 0){
        m++;
        ++k;
    }
    cout << k + m/2 + (n + m/2)/2;
    return 0;
}

         

Администратор Photo Автор: Администратор


Код

k = 0
n, m = map(int, input().split())
if n % 2 and m == 0:
    print(-1)
    exit()
while m % 2 != 0 or (n + m/2) % 2 != 0:
    m+=1
    k+=1
print(int(k + m/2 + (n + m/2)/2))

         

Администратор Photo Автор: Администратор


Чтобы было понятнее, как я решил данную задачу, давайте разберём пример из теста.

1 Способ


Кол-во хвостов Кол-во голов
3 3
1 => 3 4
2 => 4 2
3 => 2 2
4 => 2 3
5 => 2 4
6 => 3 2
7 => 4 0
8 => 2 0
9 => 0 0

2 способ

Кол-во хвостов Кол-во голов
3 3
1 => 3 4
2 => 3 5
3 => 3 6
4 => 4 4
5 => 5 2
6 => 6 0
7 => 4 0
8 => 2 0
9 => 0 0

Пусть количество голов - \( n \), количество хвостов - \( m \), \( k = 0 \).
Из второго способа ясно, что нужно увеличивать \( m \) и счётчик k, пока результат \( n + m/2 \) не станет чётным. Затем по условию "Если отрубить два хвоста, то вырастает 1 голова" выполним действие
\( k = k + m / 2 \). Соответственно количество голов тоже увеличится и будет равно \( n + m/2 \).
И последнее, что мы сделаем, выполним условие "только когда отрубить 2 головы, то не вырастет ничего",
т.е \( k = k + n / 2 \)


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться