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

[FasterHarder]

Всем хай! Сходу к делу!

Попалась на просторах сети такая задача.
Алгоритм вычисления значения функции F(n), где n  — целое число, задан следующими соотношениями:
F(n) = n, если n < 10;
F(n) = F(n mod 10) + F(n div 10), если n >= 10.
Определите количество значений n, меньших 2⁶³, для которых F(n) = 159.

Если решать в лоб, то все тривиально, конечно. Кстати, вот это число 2⁶³, это ведь секстиллионы, септиллионы всякие и т.п. В С++ тип данных __int64 вроде покрывает это значение, поэтому в коде везде этот тип данных воткнул, не думая долго.

#include <iostream>
#include <limits>
 
using namespace std;
 
__int64 F( __int64 n )
{
    if ( n < 10 )
    {
        return n;
    }
    else
    {
        return F( n % 10 ) + F( n / 10 );
    }
}
 
int main( void )
{
    __int64 k = 0;
 
    for( __int64 n = 11; n <= LLONG_MAX; n++ )  // LLONG_MAX - это и есть ( 2^63 - 1 )
    {
        if ( F( n ) == 159 )
        {
            k++;
        }
    }
 
    cout << k;
 
    cin.get();
    return 0;
}

Понятно, что программа умерла при запуске. Проверил, примерно за 1сек 1млн значений перебирает. А в диапазоне этих значений больше миллиардов. Причем, чем больше число, тем больше времени требуется на его обработку/проверку.

Вопрос: можно ли как-то брут-форс оптимизировать? Но не в 5 раз, т к глобально это все равно по времени работы будет "вечность". Тут нужна оптимизация в миллиард раз хотя бы, хотя этого тоже маловато будет.

==============================
С др.стороны программа вроде корректная ( если нет опечаток каких-нибудь ) и требований по времени выполнения нет. Но мне просто любопытен сам факт оптимизации всего этого дела...

Сообщение отредактировано: FasterHarder - 09.04.24, 03:27

[macomics]

(n > 1600) разделив на 10 получите явно значение большее 159 после суммирования. (1500 > n) разделив на 10 и прибавив остаток от деления (т.к. в остатке будет значение не больше 10) тоже не могут дать значение равное 159. Поэтому проверять в цикле 2⁶³ не нужно.

Рекурсию я и не заметил. Надо подумать о пределах. Хотя уже и так очевидно, то F(n % 10) эквивалентно n % 10 по условию функции.

ADD: по сути получается, что тут сумма всех цифр числа должна быть равна 159. 2⁶⁴ число содержит не более 20 цифр. Но, если к одной цифре прибавить 1, то от другой эту единицу надо отнять, чтобы не нарушалась сумма.

Сообщение отредактировано: macomics - 09.04.24, 08:28

[macomics]

Получается первое число удовлетворяющее условию это 699999999999999999. Сумма его цифр как раз равна 159. А дальше надо проверять не все (т.к. их осталось очень много 0699999999999999999 .. 9223372036854775807), а следовать выше описанному правилу.

Получается надо 12 ноликов разложить по 19 коробкамцифрам, но в каждой помещается не более 9. Еще и лимит есть, который не позволяет просто посчитать количество таких перестановок.

Сообщение отредактировано: macomics - 09.04.24, 08:29

[FasterHarder]

Абсолютно верно подмечено, что здесь "зашифрован" алгоритм нахождения суммы цифр заданного числа. Поправка небольшая: там 19 цифр, а не 20.

Вот наименьшее и наибольшее подходящее значение:
0_699_999_999_999_999_999 - MIN
9_159_999_999_999_999_999 - MAX ( вроде б! )

Получается, что нужно 159 единиц распихать по разрядам всеми возможными способами, чтобы полученное значение принадлежало [ MIN; MAX ]. Это back-tracking нужен или нет, хм...

Если все 19 разрядов принять за 9, то будет 19 * 9 = 171. То нужно получить все возможные комбинации, когда вычитается 12 единиц.

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

Еще по структурам данных: тут достаточно с числом работать или придется массив из 19 элементов заводить, хм...

Еще такой момент: в задачах такого типа иногда вообще код не пишется, а все доказывается через математические рассуждения. Где-то ариф.прогрессия, где-то факториальная зависимость и т.п. Может и здесь БЕЗ КОДА все можно сделать?)) Тут оч. сильно "попахивает" комбинаторикой, перестановками и пр. ( об этом написал macomics еще в посте №4 )

зы: в целом должно быть просто, а ведь непросто здесь как-то все...

[macomics]

Комбинаторикой можно было бы обойтись. Но придется еще как-то учесть лимит чисел (9223372036854775807). Подозреваю, что тогда формула для вычисления количества перестановок получится очень большой.

20 знаков я посчитал для unsigned int64 (18446`74407`37095`51615 = 20 знаков)

Сообщение отредактировано: macomics - 09.04.24, 08:29

[Mikle]

Без всяких int64 расчётов.
Заводим массив на 10 элементов. В ячейки записываются кол-ва цифр, равных номеру в массиве.
В начале все элементы = 0.
Рекурсивно обходим массив с 0-го элемента, поочерёдно записывая туда числа от 0 до 19.
Переходя к следующему элементу, проверяем, что сумма значений элементов не превысила 19, а сумма произведений значений элементов на их номера не превысила 159. При превышении или достижении 10-го (несуществующего) элемента проверяем, что сумма значений элементов равна 19, а сумма произведений значений элементов на их номера равна 159. Если да, то мы нашли очередной вариант кол-ва разных цифр в искомом большом числе.
Для найденных вариантов простой расчёт, допустим, мы нашли, что в числе 8 девяток, 10 восьмёрок и 1 семёрка:
8*9+10*8+1*7=159
8+10+1=19
10 восьмёрок в 19-разрядном числе можно разместить 92378 способами, 92378 - это 10-й элемент 19-й строки треугольника Паскаля.
Далее в оставшихся 9 разрядах одну семёрку можно разместить 9-ю способами (1-й элемент 9-й строки треугольника Паскаля). Девятки мы не считаем, девятки - это "все остальные цифры".
Итого 92378*9 = 831402 - такое кол-во чисел, в составе цифр которых 8 девяток, 10 восьмёрок и 1 семёрка.
Находим так для всех остальных составов, суммируем.
Но это без учёта лимита 2^63!

[FasterHarder]

Mikle, если готов, то, давай поразбираемся...

опр. Искомое число - число, состоящее из 19 разрядов, сумма цифр которого = 159.

перед нами такое уравнение:
k0*0 + k1*1 + ... * k8*8 + k9*9 = 159, где
k0, k1, ..., k8, k9 - коэффициенты, выражающие количество цифр ( соот-но 0, 1, ..., 8, 9 ( в искомом числе.
Т к искомое число состоит из 19 разрядов, то покамест эти коэффициенты лежат на отрезке [ 0; 19 ]. То есть, если делать полный перебор, то это 20^10 вариантов, что "рядом" с 2^63...

Докажем, что искомое число ДОЛЖНО иметь минимум 7 разрядов, равных 9.
Если предположить, что искомое число содержит 6 разрядов, равных 9, то в этом случае максимальная сумма цифр будет: 6 * 9 + 13 * 8 = 158, а должно быть НЕ МЕНЬШЕ 159. Доказано.

Кстати, по формуле сочетаний, получается 50 388 различных наборов чисел, состоящих из 7 девяток. Много времени потратил на развитие этой идеи, но там образуются дубликаты после перестановок, которые вообще не понимаю, как победить, поэтому отказался от этой идеи...

На данный момент известно, что по крайней мере k9 = [ 7; 19 ]. Можно еще правую границу сузить, т к 9 * 18 = 162 > 159, поэтому k9 = [ 7; 17 ].

Если забить число одними 9ками, то сумма цифр будет 9 * 19 = 171. А надо, чтобы было 159. И тут есть 2 подхода ( не уверен, что они равносильные ).
1 подход: получать всеми возможными способами сумму 159
2 подход: инвертировать логику и получать всеми возможными способами сумму 12. 159 = 171 - 12. В этой логике 9 как бы 0, 8 как бы 1 и т.д. Узнав, сколько существует способов получить сумму 12, автоматически скажет, сколько существует способов получить сумму 159.
Что проще для анализа: пытаться получить сумму, равную 159 или сумму равную 12? Вроде как визуально даже проще 12.

Запишем:
k0*0 + k1*1 + ... * k8*8 + k9*9 = 12, а также известно, что k0 = [ 7; 17 ]

Что по k1, который отвечает за кол-во единиц ( де-юре за за количество 8рок )?
k1 * 1 <= 12 ---> k1 <= 12

По k2: k2 * 2 <= 12 ---> k2 <= 6
k3: k3 * 3 <= 12 ---> k3 <= 4
k4: k4 * 4 <= 12 ---> k4 <= 3
k5: k5 * 5 <= 12 ---> k5 <= 2
k6: <= 2
k7, k8, k9 <= 1

В итоге ограничение по коэффициентам такие:
[ 7; 17 ] - 11 наборов
[ 0; 12 ] - 13 наборов
[ 0; 6 ] - 7 наборов
[ 0; 4 ] - 5 наборов
[ 0; 3 ] - 4 набора
[ 0; 2 ] - 3 набора
[ 0; 2 ] - 3 набора
остальные [ 0; 1] - 2 набора

Чтобы сделать перебор всего этого дела потребуется итераций:
11 * 13 * 7 * 5 * 4 * 3 * 3 * 2 * 2 * 2 = 1 441 400 - это ВЕРХНЯЯ ОЦЕНКА всей этой шняги...Перебор этих итераций ( пустых ) комп сделает ну где-то около секунды. Понятно, что ВНУТРИ каждой итерации должна быть проверка на сумму 159 + кол-во разрядов. Когда набор найден, включаются перестановки с повторениями, вроде бы...

Ты упомянул про треугольник Паскаля, я так понимаю, что это больше для полноты картины и можно без него ведь.

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

понятно, что еще есть проблема с самим число 2^63, т к, например, число, начинающееся с 99...уже недопустимо и как победить это - вообще не представляется возможным, т к все считается в итоге на комбинаторике, а ей по барабану на это ограничение...ужс

в целом нелегко как-то, учитывая, что это задача уровня ЕГЭ ( ну, понятно, какого-то завышенного уровня сложности ) и задачи из этой категории, как правило, решаются за 1 мин, бывает и за 15 сек) мдя...

Добавлено 12.04.24, 07:57
кстати, есть ведь готовый код на ЯП ПАЙТОН ( который я знаю ровно на 0.0 ):

from functools import *
 
# граничное значение
a = list(map(int, str(2**63-1)))
 
@cache
def f(s, l, fl):
    # если последовательность нужной длины, проверяем, что сумма нам подходит,
    # и выходим из рекурсии.
    if l == 0: return s == 159
 
    # проверяем ограниченные подпоследовательности большей длины
    return sum(f(s+x, l-1, fl and (x == a[-l])) for x in range([10, a[-l]+1][fl]))
 
# ответ - количество ограниченных последовательностей необходимой длины
print(f(0, len(a), 1))

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

на С++ ведь не получится таким же объемом кода сделать)) или...

Сообщение отредактировано: FasterHarder - 12.04.24, 07:57

[MBo]

FasterHarder

Вот я делал что на Python, но без ограничения - может быть, легче читать.

lru_cache складывает уже посчитанные результаты в таблицу, и использует без перевычисления, можно map использовать для этого.
Считает мгновенно и код выше, и этот.

import functools
@functools.lru_cache(9999)
def cnt159(summ, dig):
    if summ == 0:
        return 1
    if dig == 0:
        return 0
    res = 0
    for i in range(max(0, summ - 9*(dig-1)), min(10, summ+1)):
        res += cnt159(summ - i, dig - 1)
    return res
 
print(cnt159(159, 19))

[FasterHarder]

MBo, спс, конечно, за код, но для начала нужно понять АЛГОРИТМ. Я попробую его восстановить через код, но тут всяких моментов полно:
1. я так понимаю, что range - аналог for, т е запись for i in range( 0, 15 ) равносильна в С++ for( int i = 0; i <= 15; i++ )
2. и этот момент важнее в разы. В каком формате хранит lru_cache, в какой момент вызывается, т к явно в функции нигде вызова этого нету + какие результаты вычислений хранит. Это какая-то форма мемоизации или нет - непонятно все это...

а лучше всего пояснить алго на пальцах

[MBo]

Код на каждом уровне рекурсии перебирает очередную цифру в диапазоне возможных значений - цифра не может быть меньше, чем остаток минус все девятки на других местах, и не больше остатка. Например, если оставшаяся сумма 20, а цифр осталось 3, то 0 и 1 не может быть первой цифрой, и перебираем от 2 до 9

range(0, 15) равносилен в С++ for( int i = 0; i < 15; i++) (конец диапазона не входит).

lru_cache - это мемоизация. Скажем так - если функция с такими аргументами уже вызывалась, то результат возвращается из таблицы. Иначе результат считается и заносится в таблицу типа map.insert(std::pair<int,int>(summ,dig));

Однако, когда писал, я не придумал, как легко учесть ограничение.

Сообщение отредактировано: MBo - 12.04.24, 09:47

[FasterHarder]

MBo, спс, стало понятнее, но есть еще ряд моментов. Про них тоже прошу пояснить.

момент №1.
как я понимаю, алгоритму все равно, каким образом "анализируем" разрядную сетку числа: от старшего к младшему разряду или наоборот.

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

момент №2.
про заголовок функции cnt159
ее прототип: int cnt159( int summ, int dig )
summ - отвечает за ту сумму, которую нужно получить, используя dig разрядов
например: cnt159( 39, 4 ) говорит, что нужно собрать сумму, равную 39, используя РОВНО 4ре СВОБОДНЫХ ( еще не обработанных ) разряда

на старте она вызывается с аргументами ( 159, 19 ), т к нужно в итоге получить 159, используя 19 разрядов

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

момент №3.

Цитата MBo @ 12.04.24, 09:45

Код на каждом уровне рекурсии перебирает очередную цифру в диапазоне возможных значений - цифра не может быть меньше, чем остаток минус все девятки на других местах, и не больше остатка. Например, если оставшаяся сумма 20, а цифр осталось 3, то 0 и 1 не может быть первой цифрой, и перебираем от 2 до 9

интуитивно я понимаю о чем речь, это примерно о тех коэффициентах k0, k1, ..., k8, k9, о которых писал выше, просто у тебя этот перебор сделан сверх оптимально. Как бы это не анализ этих коэффициентов, а выбор диапазона допустимого значения разряда - это я вроде понимаю.

т е происходит анализ ТЕКУЩЕГО разряда и делается попытка найти диапазон его значений.
например, осталось 5 разрядов и нужна сумма = 40: XXXXX
что мы делаем: заполняем 9ками все разряды кроме текущего X9999 и находим разность 40 - 9*4 = 4
получается, что минимум текущий разряд должен быть 4кой. Это понятно.
а, если то же самое, но сумма = 30 --> X9999 --> 30 - 9*4 = -6 - получилось отрицательное значение.
Из этого следует, что левая граница текущего разряда начинается от 0?

по правой границе.
как я понял, нужно подставлять НУЛИ
5 разрядов и нужна сумма = 40 --> X0000 ---> 40 - 0 = 40 > 9, следовательно, правая граница = 9

другой пример. Сумму нужно набрать 7, используя 2 разряда
X0 --> 7 - 0 = 7 <= 9, следовательно, правая граница = 7.

вот этот набор правил, позволит однозначно определить границы значений текущего разряда? - но как-то ведь у тебя проще сделано + писал про остаток от деления

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

момент №4. про мемоизацию
рассмотрим упрощенный пример, пусть нужна сумма = 15 и дано 5ть разрядов
рассмотрим 2 набора:
12345
312XX - этот набор уже НЕ будет считаться, т к будет дан запрос в хранилище, мол надо получить сумму = 9, используя 2 разряда, а такой расчет уже был для варианта 12345 и сразу вычисления заканчиваются и запрос отвечает, да, такую сумму можно получить и в качестве ответа вернет число, равное кол-ву всех возможных комбинаций, которыми можно получить эту сумму

мемоизация начинает работать только тогда, когда будет получен хотя бы 1 подходящий набор для суммы = 159 из 19 разрядов. Для этих целей map будет заюзан, как ты писал выше. А обращаться к этой таблице мемоизации нужно в начале каждого вызова рекурсивной функции.
Мемоизация будет работать только тогда, когда в таблице будет совпадение по нужной сумме и кол-ву еще незанятных разрядов. Местоположение разрядов не играет никакой роли. По сути, ведь, мемоизация дает колоссальную оптимизацию при пересчете хвостовых перестановок разрядов...наверное)

Добавлено 12.04.24, 11:36
про силу мемоизации добавлю еще, что, условно, если для случая
12XXXXXXXX... получилось 256К подходящих вариантов, то
при анализе 21XXXXXXXX... сразу запрос к таблице и ответ вернется 256К за О(1) ( или может не О(1), а чуть побольше, в зависимости от архитектуры map ) без всяких пересчетов

[MBo]

>алгоритму все равно, каким образом "анализируем" разрядную сетку числа: от старшего к младшему разряду или наоборот.
Да

>summ - отвечает за ту сумму, которую нужно получить, используя dig разрядов
Да

>отрицательное значение. Из этого следует, что левая граница текущего разряда начинается от 0?
Верно, поэтому для обрезки отрицательных стоит max(0, summ - 9*(dig-1))

>нужно подставлять НУЛИ
нет, не нужно. Это условие работает, когда остаток summ становится меньше 9. Тогда нет смысла проверять все цифры до девятки

>12345 312XX - этот набор уже НЕ будет считаться, т к будет дан запрос в хранилище, мол надо получить сумму = 9, используя 2 разряда, а такой расчет уже был для варианта 12345 и сразу вычисления заканчиваются и запрос отвечает, да, такую сумму можно получить и в качестве ответа вернет число, равное кол-ву всех возможных комбинаций, которыми можно получить эту сумму

Совершенно верно

>мемоизация

Вроде всё правильно

[FasterHarder]

MBo, спс за пояснение, теперь я на 100 ( ну, хорошо, на 99 )% понял эту конструкцию:

Цитата MBo @ 12.04.24, 09:02

for i in range(max(0, summ - 9*(dig-1)), min(10, summ+1)):

меня смутила 10ка сначала, но потом вспомнил, что правая граница не входит, т е пойдет до 9ки
в целом очень лаконичная и точная запись перебора

тем временем, у меня готов код на С++!, как ты и подсказал, через map:

#include <iostream>
#include <map>
#include <algorithm>
 
using namespace std;
 
// для мемоизации данных
map< pair< int, int >, int > values;
 
// набор суммы ( sum ), используя digits разрядов
int F159( int sum, int digits )
{
    // проверим, а нет ли в таблице мемоизации уже рассчитанного готового значения для данной суммы с использованием заданного кол-ва разрядов
    map< pair< int, int >, int > :: iterator it = values.find( make_pair( sum, digits ) );
    if( it != values.end() )
    {
        return it -> second;
    }
 
    // заданную сумму удалось набрать
    // необработанные оставшиеся разряды будут равны 0, т к их добавление не влияет на набранную сумму
    if( sum == 0 )
    {
        return 1;
    }
 
    // все разряды обработаны, но заданную сумму, так и не удалось набрать
    // вроде бы избыточно, т к перебор цифр сделан сверх оптимально, что ВСЕГДА приводит к набору нужной суммы
    if( digits == 0 )
    {
        return 0;
    }
 
    int res = 0;
    for( int i = max( 0, sum - 9*( digits - 1 ) ); i < min( 10, sum + 1 ); i++ )
    {
        res += F159( sum - i, digits - 1 );
 
        // добавляем новый набор в таблицу мемоизации
        pair< int, int > new_value = make_pair( sum, digits );
        values[ new_value ] = res;
    }
 
    return res;
}
 
int main()
{
    setlocale( LC_ALL, "Russian" );
 
 
    cout << F159( 159, 19 );
 
    cin.get();
    return 0;
}

есть у меня подозрение, что вот этот блок проверки digits == 0 избыточен, т к перебор допустимых цифр настолько оптимален ( идеально просто ), что ВСЕГДА заданную сумму можно набрать

ответ выдается моментально и равен 86 489 615

Добавлено 12.04.24, 14:30
и в целом все прекрасно работает и теперь почти все основательно понятно, но есть одно маленькое НО - этот код НЕ решает поставленную задачу), т к НЕ учитывает ограничение на 2⁶³...
на данный момент находятся ВСЕ наборы, состоящие из 19 цифр + их сумма = 159.

и вот надо тут понять такие моменты:
1. можно ли доработать текущий алгоритм, добавив это ограничение
2. нужен абсолютно НОВЫЙ алго

и вот сдается мне, что здесь вариант №2 , потому что алгоритм ни коим образом не учитывает местоположение анализируемого разряда

A + B = C
C - все множество подходящих наборов из 19 цифр и суммой = 159
A - кол-во наборов, таких же как С, но < 2⁶³
B - --> >= 2⁶³
а толку - никак ведь не поможет

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

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

кстати, а тот код на Питоне ведь каким-то чудом это ограничение учитывает, хм...

[Mikle]

Цитата FasterHarder @ 12.04.24, 07:39

То есть, если делать полный перебор, то это 20^10 вариантов, что "рядом" с 2^63...

Там при переборе рекурсией будет частое обрезание целых больших ветвей по условию "сумма значений элементов не превысила 19, а сумма произведений значений элементов на их номера не превысила 159".

Цитата FasterHarder @ 12.04.24, 07:39

в целом нелегко как-то, учитывая, что это задача уровня ЕГЭ

Вот тут согласен.

Цитата FasterHarder @ 12.04.24, 07:39

Ты упомянул про треугольник Паскаля, я так понимаю, что это больше для полноты картины и можно без него ведь.

Это просто один из методов нахождения кол-ва вариантов перестановок.

Сообщение отредактировано: Mikle - 12.04.24, 15:43

[FasterHarder]

Цитата Mikle @ 12.04.24, 15:41

Там при переборе рекурсией будет частое обрезание целых больших ветвей по условию "сумма значений элементов не превысила 19, а сумма произведений значений элементов на их номера не превысила 159".

безусловно

Цитата Mikle @ 12.04.24, 15:41

Вот тут согласен.

вот пример задачи из той же категории, что и текущая
Алгоритм вычисления значения функции F(n), где n  — натуральное число, задан следующими соотношениями:
F(n)  =  n при n > 2024;
F(n)  =  n · F(n + 1), если n ≤ 2024.
Чему равно значение выражения F(2022) / F(2024)?

Сколько нужно времени, чтобы ее решить?)
F( 2022 ) = 2022 * F( 2023 )
F( 2023 ) = 2023 * F( 2024 )

2022 * 2023 * F( 2024 )
----------------------- = 2022 * 2023 = и тут аккуратно перемножить
F( 2024 )

ну, за пару минут такое вроде можно сделать.
А задача из первого сообщения, такое впечатление, не просто сложнее, а НА НЕСКОЛЬКО ПОРЯДКОВ сложнее...хм...