1 Востаннє редагувалося koala (06.03.2023 23:31:01)

Тема: Codewars: Maximum different differences. Точність обчислень

Повна умова тут

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

розглянемо всі можливі масиви впорядкованих додатних чисел, максимальне з яких an. Обчислимо для кожного такого масиву масив різниць [a2-a1, a3-a2,... an-a(n-1)]. У цих масивах може бути різна кількість різних  значень, наприклад для масиву [1,2,3,4] масив різниць [1,1,1], значення одне {1}, а для масиву [1,2,4] масив різниць [1,2] має два значення {1,2}. Для заданого an знайти максимальну кількість різниць.

Якщо викинути всю мішуру, то треба знайти номер найбільшого трикутного числа, меншого за задане. Це нескладно, але перевірка іде з високою точністю (на кшталт an=479303728892892547), і моя тупа математика

int(((8*(a_n-1)+1)**.5-1)/2)

дає похибку в 1 (тест каже, що має бути 979085009, а мій код видає 979085010. І взагалі там значення до 2**200).
Як тут можна підвищити точність?

О, власне, спитав і сам дав собі відповідь:

from decimal import *

def max_df(a_n: int) -> int:
    getcontext().prec = 60
    return int(((Decimal(8*(a_n-1)+1))**Decimal(.5)-1)/2)

Зараз гляну, як інші викручувалися...

Подякували: Betterthanyou1

2

Re: Codewars: Maximum different differences. Точність обчислень

Ага, для таких випадків є math.isqrt. Треба буде запам'ятати. Хоча дехто просто бінарний пошук робив, теж швидкості вистачає.

Подякували: leofun011