1

Решаю задачку (https://www.codewars.com/kata/5b5ce2176d0db7331f0000c0/train/python). Вот моё решение:

def get_rope_length(field_diameter, eaten_ratio):
    import math
    
    R = field_diameter/2
    eps = 10**(-(len(str(field_diameter)))-1)
    
    def square(r):
        import math
        alpha = (math.asin(r/(2*R)))*2
        beta = math.acos(r/(2*R))

        square_alpha = (R**2)*(alpha - 0.5*math.sin(alpha*2))
        square_beta = (r**2)*(beta - 0.5*math.sin(beta*2))

        square = square_alpha + square_beta

        return(square)
    
    if (R > 0) and (eaten_ratio < 1):
        S = math.pi*R*R
        
        step = R
        r = step
        
        while True:
            delta = (S * eaten_ratio) - square(r)
            if abs(delta) < eps:
                break
            if delta > 0:
                r = r + step
            else:
                r = r - step
            step = step/2
        return (int(r))
    elif (R == 0):
        return(0)
    elif (eaten_ratio == 1):
        return(int(R*2))

Вкратце. Функция square определяет площадь фигуры, образованной наложением окружностей (центр "искомой" окружности лежит на одной из точек "зафиксированной" окружности). Далее идет само решение задачи. Решал методом деления отрезка пополам. Искомый радиус последовательно приближается к искомому значению, при котором площадь наложения не отличается от требуемой на заданную точность (переменная eps). Однако такой метод медленно работает при больших входных величинах. Не подскажете, как решать данную задачу и вообще задачи подобного типа, когда составить какую-то зависимость достаточно проблематично. Как мне кажется, ускориться можно, если выбрать другое начальное приближение и шаг сближения (В моем решении я начинаю безусловно решать при step == R == r)

5
  • Я правильно понимаю, что у вас эпсилон обратно пропорционален field_diameter? Может это как-то неправильно? Эпсилон для больших чисел должен быть больше, а не меньше. Либо я чего-то не понимаю.
    – CrazyElf
    30 июн 2022 в 8:45
  • 2
    обычно подобные задачи значат что надо садиться и писать кучу формул а не перебирать варианты 30 июн 2022 в 8:49
  • Да, здесь немного напутал, сравниваю же абсолютную разницу, а не относительную. Вообще его можно зафиксировать порядка 10**(-3 ~ -4) 30 июн 2022 в 8:55
  • Мол вывести зависимость площади от малого радиуса? Ух, жаришка, вряд ли потяну такое 30 июн 2022 в 8:57
  • 1
    Ваша задача - получить целое число, поэтому не имеет смысла дробить step менее 1
    – MBo
    30 июн 2022 в 12:40

1 ответ 1

3

Почему бы не задействовать двоичный поиск?

class Solution:
    def __init__(self, diameter):
        self.diameter = diameter

    def __len__(self):
        return self.diameter + 1

    def __getitem__(self, rope_length):
        # процент отъеденный от поля диаметром self.diameter при длине веревки rope_length
        return ...

А потом, бац,

import bisect

def get_rope_length(field_diameter, eaten_ratio):
    return bisect.bisect_right(Solution(field_diameter), eaten_ratio)
5
  • Ничего не понял, но очень интересно :D. Пойду учиться) 30 июн 2022 в 16:50
  • @НиколайБруцкий-Стемпковский 1) в вашем примере, как заметил MBo, результат должен быть целым, значит и проверять нужно только целые длины. 2) при увеличении длины веревки площадь пересечения не убывает. Это дает нам неубывающую последовательность длиной diameter + 1 (от 0 до diameter включительно), в которой с помощью двоичного поиска (bisect_right) можно найти количество элементов меньших либо равных eaten_ratio, что вам и требуется.
    – extrn
    30 июн 2022 в 16:58
  • Нее, я совсем бегинер, пока страшновато от обилия функций и классов. Но идею я понял. То, что я назвал методом деления отрезка пополам, вроде как и есть двоичный поиск. Однако я буквально делил отрезок пополам, получал дробные числа и прочие прелести. Наверное, если работать с массивом целых значений, дело пойдет быстрее. Или я все же чего-то не догнал? 30 июн 2022 в 19:08
  • @НиколайБруцкий-Стемпковский "массив" дробных значений, где каждый индекс - (целая) длина веревки, а каждое значение по этому индексу - процент покрытия. В остальном все верно. Только массив этот будет неподъемного размера, поэтому я использую Solution(diameter) как нечто притворяющееся массивом: можно получить его длину и обратиться к нему по индексу. Для библиотечной реализации двоичного поиска этого достаточно. Но он не хранит всех своих значений, а вычисляет их при обращении. В кустарной реализации поиска можно и вовсе обойтись без массива, но это уже оставляю на вас.
    – extrn
    30 июн 2022 в 19:26
  • Ну что сказать, круто, работает. Спасибо) 1 июл 2022 в 4:14

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.