почему это не удается один тестовый случай - PullRequest
Новая
       24

почему это не удается один тестовый случай

0 голосов
/ 24 июня 2019

ниже описывается проблема:

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

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

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

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

это мой код: 

import java.math.BigInteger;

    class Solution {
        public static String solution(String x, String y) {
            BigInteger m = new BigInteger(x);
            BigInteger f = new BigInteger(y);

            int cycles = 0;

            while(true) {
                if(m.compareTo(BigInteger.ONE) == -1 || f.compareTo(BigInteger.ONE) == -1)
                    return "impossible";
                else if(m.compareTo(BigInteger.ONE) == 0 && f.compareTo(BigInteger.ONE) == 0)
                    return String.valueOf(cycles);
                else {
                    if(m.compareTo(f) == 1) {
                        m = m.subtract(f);
                    } else {
                        f = f.subtract(m);
                    }
                    cycles++;
                }
            }
        }
    }

Я передаю всетестовые случаи, кроме одного, и проблема в том, что тестовый пример скрыт.Чего-то не хватает в моем коде?

Ответы [ 2 ]

0 голосов
/ 24 июня 2019

Оказалось, что это проблема времени и / или размера.Я преобразовал ту же логику в Python, и это сработало как шарм.Java перепаковывает значение переменной, когда оно переполняется, поэтому, возможно, когда оно получает значение, большее, чем оно может обработать, оно оборачивает его.

однако BigInteger / BigDecimals практически не имеют ограничений, но Google ограничивает пространство (хранилище) и время, затраченное программой.

Вот код: 

def answer2(M, F):
    m, f = int(M), int(F)
    total = 0
    while not (m == 1 and f == 1):
        if f <= 0 or m <= 0:
            return "impossible"
        if f == 1:
            return str(total + m - 1)
        else:
            total += int(m/f)
            m, f = f, m % 
    return str(total)
0 голосов
/ 24 июня 2019

Я примерно просмотрел ваш код, и логика кажется довольно удовлетворительной (я могу ошибаться).Но проблема, которую я вижу, заключается в сложности.Я придумал одну логику: вы можете изменить решение.Вместо того, чтобы начинать с рута, вы можете начать с места назначения.Например. m=4, n=7 ===> (4,7) --step 0 higher-lower i.e (7-4) ===> (4,3) --step 1 higher-lower i.e (4-3) ===> (1,3) -- step 2(after getting one of the value 1 higher - lower is the remaining steps) set (1,1) as the accepting state or something :P fast forward ------> step 4(which is your ans) i.e no complexity Невозможные случаи: where you get both value greater than 1 and equal EG. m=6, n=3 ===> (6,3) --step 0 higher-lower i.e(6-3) ===> (3,3) --step 1 higher-lower well. the number are equal and greater than 1===> impossible

...