Google Foobar Bomb_baby. TLE

Question

Это вопрос, с которым я сталкиваюсь на 3 уровне Google Foobar. Итак, вопрос в следующем.

Есть два типа: бомбы Маха (M) и бомбы Facula (F). Бомбы, выпущенные во внутреннюю работу LAMBCHOP, автоматически развернутся на всех стратегических точках, которые вы определили, и уничтожат их одновременно.

Но есть несколько уловов. Во-первых, бомбы самовоспроизводятся с помощью одного из двух отдельных процессов: каждая бомба Маха извлекает блок синхронизации из бомбы Факула; для каждой бомбы Маха создается бомба Факула; Каждая бомба Facula самопроизвольно создает бомбу Маха.

Например, если у вас было 3 бомбы Маха и 2 бомбы Факула, они могли производить либо 3 бомбы Маха и 5 бомб Факула, либо 5 бомб Маха и 2 бомбы Факула. Процесс репликации может быть изменен каждый цикл.

Во-вторых, вам нужно убедиться, что у вас есть точное количество бомб Маха и Факулы для уничтожения устройства LAMBCHOP. Слишком мало, и устройство может выжить. Слишком много, и вы могли бы перегрузить массовые конденсаторы и создать особенность в центре космической станции - не хорошо!

И, наконец, вы смогли пронести только одну бомбу каждого типа - один Маха и один Факул - на корабль, когда вы прибыли, так что это все, с чего вам нужно начать. (Таким образом, может быть невозможно развернуть бомбы, чтобы уничтожить LAMBCHOP, но это не помешает вам попробовать!)

Вам необходимо знать, сколько циклов репликации (поколений) потребуется, чтобы сгенерировать правильное количество бомб для уничтожения LAMBCHOP. Напишите функциональный ответ (M, F), где M и F - количество необходимых бомб Маха и Факулы. Верните наименьшее количество поколений (в виде строки), которое необходимо пройти, прежде чем вы получите точное количество бомб, необходимых для уничтожения LAMBCHOP, или строку "невозможно", если это невозможно сделать! M и F будут строковыми представлениями натуральных чисел не более 10 ^ 50. Например, если M = "2" и F = "1", нужно пройти одно поколение, поэтому ответом будет "1". Однако, если M = "2" и F = "4", это было бы невозможно.

Языки

Чтобы предоставить решение Python, отредактируйте solution.py Чтобы предоставить решение Java, отредактируйте solution.java

Контрольные примеры

Входные данные: (строка) M = "2" (строка) F = "1" Выходные данные: (строка) "1"

Входные данные: (строка) M = "4" (строка) F = "7" Выходные данные: (строка) "4"

Так как входные данные являются числами в строках и могут быть длиной до 10^50, я использую класс BigInteger в Java. Подход, который я использовал, дает мне TLE. Может кто-нибудь сказать мне, как я могу оптимизировать его дальше?

Мой код в Java.

пакет com.google.challenges;

import java.math.BigInteger;

public class Answer {   
    public static String answer(String M, String F) { 

    if(M.equals("1") && F.equals("1"))
    {
        return "0";
    }
    BigInteger ans = func(new BigInteger(M),new BigInteger(F));
    if(ans.compareTo(new BigInteger("-1")) == 0)
    {
        return "impossible";
    }
    else
    {
        return ans.toString();
    }
    }   
    public static BigInteger func(BigInteger m,BigInteger f)
    {
        int check;
        BigInteger steps = new BigInteger("0");
        BigInteger one = new BigInteger("1");
        while((check = m.compareTo(f)) != 0)
        {
            if(check == -1)
            {
                f = f.subtract(m);
            }
            else
            {
                m = m.subtract(f);
            }
            steps = steps.add(one);
            if(m.compareTo(one) == 0 || f.compareTo(one) == 0)
                break;
        }
        int mComparedTof = m.compareTo(f);
        int mCompareToOne = m.compareTo(one);
        int fCompareToOne = f.compareTo(one);
        if(mCompareToOne == 0 && fCompareToOne == 0)
        {
            return steps;
        }
        else if(mComparedTof == 0 && mCompareToOne != 0)
        {
            return new BigInteger("-1");
        }
        else if(mCompareToOne == 0)
        {
            steps = steps.add(f.subtract(one));
            return steps;
        }
        else
        {
            return steps.add(m.subtract(one));
        }
    }

}