Google foobar вызов gearing_up_for_destruction

Question

Вызов

Как личный помощник коммандера Lambda, вам было поручено настроить осевые ориентиры устройства LAMBCHOP конца света. Это должно быть довольно просто - просто добавьте шестерни, чтобы создать соответствующий коэффициент вращения. Но проблема в том, что из-за компоновки LAMBCHOP и сложной системы балок и поддерживающих его труб штифты, которые будут поддерживать шестерни, закреплены на месте.

Инженеры LAMBCHOP предоставили вам списки, определяющие расположение групп колышков вдоль различных опорных балок. Вам нужно поставить шестерёнку на каждый колышек (иначе шестерни столкнутся с незанятыми колышками). Инженеры имеют в своем арсенале множество шестерен разных размеров, поэтому вы можете выбирать шестерни любого размера с радиусом от 1 и выше. Ваша цель - создать систему, в которой последняя передача вращается с удвоенной скоростью (в оборотах в минуту или об / мин) первой передачи, независимо от направления. Каждая шестеренка (кроме последней) касается и поворачивает шестеренку следующего колышка вправо.

Учитывая список различных натуральных чисел, названных колышки, представляющих местоположение каждого колышка вдоль опорной балки, написать функцию ответ (колышки), которые, если есть решение, возвращает список из двух положительных чисел а и Ь, представляющий числитель и знаменатель радиуса первого зубчатого колеса в его простейшей форме для достижения цели, указанной выше, такой, что радиус = a/b. Отношение a/b должно быть больше или равно 1. Не все вспомогательные конфигурации обязательно будут способны создать правильный коэффициент вращения, поэтому, если задача невозможна, функция answer(pegs) должна вернуть список [-1, -1].

Например, если колышки расположены в [4, 30, 50], то первая шестерня может иметь радиус 12, вторая шестерня может иметь радиус 14, а последняя - радиус 6. Таким образом, Последняя передача будет вращаться в два раза быстрее первой. В этом случае колышками будет [4, 30, 50], а ответ (колышками) должен возвращаться [12, 1].

Пеги списка будут отсортированы в порядке возрастания и будут содержать не менее 2 и не более 20 различных положительных целых чисел, все от 1 до 10000 включительно.

Мой код:

from fractions import Fraction

def answer(pegs):
    odd = bool(len(pegs) % 2)
    s = 2
    e = rad_last(s, pegs)
    if odd:
        ans = s + (s - 2*e)
    else:
        ans = s + (2*e - s) / 3

    if ans >= 1 and valid(ans, pegs):
        f = Fraction(ans).limit_denominator()
        return [f.numerator, f.denominator]
    else:
        return [-1, -1]

def rad_last(rad_first, pegs):
    prev_rad = rad_first
    for i in range(1, len(pegs)):
        prev_rad = pegs[i] - pegs[i-1] - prev_rad
    return prev_rad

def valid(rad_first, pegs):
    prev_rad = rad_first
    for i in range(1, len(pegs)):
        prev_rad = pegs[i] - pegs[i-1] - prev_rad
        if prev_rad < 1:
            return False
    return True

Я рвал на себе волосы, потому что не могу понять, почему мое решение не соответствует четырем контрольным случаям. Я определил, что радиус последней передачи должен быть вдвое меньше радиуса первой передачи. На основании того, есть ли четное или нечетное количество колышков, значение первого радиуса может быть определено с помощью алгебры.

Моя математика

f = правильный первый радиус, такой, что он равен 2 * последнему радиусу

s = любое произвольное значение для первого радиуса

e = соответствующий радиус последней передачи, если радиус первой передачи был s

x = смещение от s, необходимое для получения правильной конфигурации

Странный

По мере увеличения радиуса первой передачи радиус последней

f = s + x = 2 (e + x)

s + x = 2e + 2x

х = с - 2е

f = s + (s - 2e)

Четное

По мере увеличения радиуса первой передачи радиус последней передачи уменьшается

f = s + x = 2 (e - x)

s + x = 2e - 2x

3x = 2e - s

х = (2е - с) / 3

f = s + (2e - s) / 3

Что я делаю неправильно? Это просто проблема с моей реализацией или я что-то упустил из этой проблемы?

Answer 1

Я думаю, что эта проблема больше похожа на бинарный поиск, поэтому я пишу версию. Я не знаю, почему она может применять бинарный поиск, но она кажется идеальной. Может помочь. я не думаю, что это проблема MATH, так как она потерпит неудачу.

from fractions import Fraction

def rad_last(rad_first, pegs):
    prev_rad = rad_first
    bad_answer = False
    for i in range(1, len(pegs)):
        prev_rad = pegs[i] - pegs[i-1] - prev_rad
        if prev_rad < 1:
            bad_answer = True
    return (prev_rad, bad_answer)

def binary_search(low, high, pegs):
    if low < high:      
        mid = (low+high) // 2
        suppose = Fraction(mid/2)
        ret, b = rad_last(mid, pegs)

        if ret < suppose:
            return binary_search(mid+1, high, pegs)
        elif ret > suppose:
            return binary_search(low, mid, pegs)
        elif ret == suppose:
            if b == False:
                return ret
            else:
                return -1
    else:
        return -1

if __name__ == '__main__':
    test_pegs = [[4, 30, 50],[40,300,500],[4,30,50,62],[1,5,8],[6,50,84],[5,50,83],[1,23,43],[123,342,324,546],[12,123,1232],[12,13,16]]
    for pegs in test_pegs:
        n = min(pegs[1]-pegs[0], 2*(pegs[-1]-pegs[-2]))
        a = binary_search(1, n, pegs)
        print(a)