Задачка из ЕГЭ, время работы которой оптимизировать бы как-то...

[FasterHarder]

Итак, на данный момент есть отличный алго ( from MBo )+прожка для нахождения всех подходящих наборов БЕЗ УЧЕТА ограничения на 2⁶³.

Как победить это ограничение на 2⁶³? Вообще мыслей нет никаких?

========================================================

В неком алго from Mikle подход через массив частотностей цифр, но там ведь тоже местоположение разряда не учитывается вроде...

--------------------------------------------------------

Единственная идея, которая осталась - заводить массив из 19 элементов ( каждый элемент соот-ет разряду числа ) и чего-то там мутить, правда, что мутить абсолютно непонятно...

[MBo]

Дополнил ограничением.

Вначале создаётся список цифр числа-ограничения. Я его сделал не по-питонски, чтоб понятнее было (// - целочисленное деление)

Если уже обработанный кусок совпадает с началом числа-ограничения, то ограничиваем очередную цифру соответствующей цифрой ограничителя (например, если имеем 92235 лимит и 922 цифры уже набрали в текущей ветке, то ограничиваем перебор цифрой 3)

Информация о том, что по первым цифрам было достигнуто ограничение, передается в near_limit - этот флаг сбрасывается, если взятая цифра меньше лимита (если в примере выше 9221 используем, то дальше уже за лимит не выйдем)

import math, functools
 
limits = []
t = 2**63-1
while t:
    limits.append(t % 10)
    t //= 10
 
@functools.lru_cache(9999)
def cnt159(summ, dig, near_limit):
    if summ == 0:
        return 1
    res = 0
    if near_limit:
        digmax = limits[dig-1]+1
    else:
        digmax = 10
    for i in range(max(0, summ - 9*(dig-1)), min(digmax, summ+1)):
        res += cnt159(summ - i, dig - 1, near_limit and (i==limits[dig-1]))
    return res
 
 
print(cnt159(159, 19, True))

Сообщение отредактировано: MBo - 14.04.24, 11:13

[FasterHarder]

MBo, круто, спс, буду разбираться...

[FasterHarder]

В общем все понятно по алгоритму ( на 95% ). Получается ответ: 34 602 572 набора.
Был еще такой момент с мемоизацией, что программа выдавала ответ 34 622 921 набор, что очень близко к прав. ответу, учитывая масштаб переборов.

И вот это проверка победила эту проблему:

    if( !near_limit )
    {
        map< pair< int, int >, int > :: iterator it = values.find( make_pair( sum, digits ) );
        if( it != values.end() )
        {
            return it -> second;
        }
    }

Вообще, вот эта переменная near_limit вроде в большинстве случаев равна false. Она равна true, когда текущий разряд достиг своего максимально допустимого значения.

Кстати, насколько знаю, в таких вот алгоритмах бывают тончайшие проблемы, связанные с ЗАПУСКОМ рекурсии, т е, чтобы она корректно отработала на самом первом вызове, т к бывает, что оттолкнуться не от чего. А в этом алго все четко, несмотря на то, что самый первый разряд обрабатываемый = 9...Для своего понимания я так решил, что есть какой-то фантомный разряд, стоящий перед 9кой, который достиг предела и делается переход уже на 9ку и как бы запустилась прожка с near_limit = true...

Кстати, Питон как-то это все ( имею в виду обращения к таблице мемоизации, когда near_limit == false ) автоматически учел, что мне не на 100% понятно, но это ладно...

По сравнению с полным перебором, этот алгоритм работает в 9 триллионов раз быстрее)), ну, грубо если.

==============================================================

MBo, остался последний вопрос в рамках этой задачи: сколько всего времени ( в мин., например ) ты потратил на решение этой задачи? Речь про чистое время, не учитывая переписку здесь и пр. То есть прочитать условие + продумать алго + закодить.

=============================================================

всем спс. за помощь

[MBo]

Не очень много времени, но я уже решал задачи на наборы подходящих сумм.
Если детали интересны, то создан файл Py в 14.47, а запостил Сообщ. #8 в 16.02 по моему времени.
Отвлекался, наверное, на работу ещё

И сразу мне показалось, что ограничение будет трудно прикрутить,
а на втором заходе уже, когда ты про это конкретно спросил, как-то сразу получилось.

[FasterHarder]

MBo, понятно
спс за помощь