Программирование[11]

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Показать больше  

не думал просто расписать все варианты того как можно получить число 159 суммой цифр, а затем посчитать количество перестановок?

если это только 18 и 19 числа то там не так уж и много вариантов, а перестановки считают по комбинаторной формуле

  Just.Doit написал 02.11.2024 в 20:03:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

не думал просто расписать все варианты того как можно получить число 159 суммой цифр, а затем посчитать количество перестановок?

если это только 18 и 19 числа то там не так уж и много вариантов

была такая идея

если бы число было близко к 171, то есть 170 или 169, то можно было бы перебрать, типа для 170 тасовать восьмерку, для 169  две восьмёрки или 1 семёрку

159 далековато от 171 и слишком дохуища перебрать наверное

помимо этого, это не решает проблему того, что число должно быть меньше 9223372036854775808 (2^63)

я про то, что для суммы в 170:

9 899 999 999 999 999 999 не подходит к примеру

8 999 999 999 999 999 999 подходит, так как меньше 2^63

p.s. фактически мне чатгпт решил задачу, только не до 9223372036854775808, а до 9 999 999 999 999 999 999

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше (на 8%, и находит 84 миллиона вместо ответа в 34 миллиона с копейками)

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Показать больше  

Откуда задача-то?

  mercury23 написал 02.11.2024 в 20:10:

  Just.Doit написал 02.11.2024 в 20:03:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

не думал просто расписать все варианты того как можно получить число 159 суммой цифр, а затем посчитать количество перестановок?

если это только 18 и 19 числа то там не так уж и много вариантов

была такая идея

 

если бы число было близко к 171, то есть 170 или 169, то можно было бы перебрать, типа для 170 тасовать восьмерку, для 169  две восьмёрки или 1 семёрку

159 далековато от 171 и слишком дохуища перебрать наверное

 

помимо этого, это не решает проблему того, что число должно быть меньше 9223372036854775808 (2^63)

я про то, что для суммы в 170:

9 899 999 999 999 999 999 не подходит к примеру

8 999 999 999 999 999 999 подходит, так как меньше 2^63

 

Показать больше  

> и слишком дохуища перебрать наверное

по прикидке - не очень. там их штук 100-200, кажется

их даже все можно расписать в качестве массивов

> помимо этого, это не решает проблему того, что число должно быть меньше

ну это уже вторая часть задачи. тоже решаемая кмк.

  Zhenek написал 02.11.2024 в 20:17:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше (на 8%, и находит 84 миллиона вместо ответа в 34 миллиона с копейками)

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Откуда задача-то?

собес джуна на галеру

школьник спросил знакомый 

я ему накодил подсчёт суммы цифр в цикле через рекурсию, за 3 минуты программа до 20 миллионов доползла, добавил к рекурсии кеш рекурсии, сильно быстрее не стало 

сказал что подумаю на выходных и вот, сижу 5й час в ахуе 

я не знаю, за покраску кнопок готовы пол миллиона платить

когда этот школьник вырастет, ему чем платить будут? ввп россии?

  mercury23 написал 02.11.2024 в 20:28:

  Zhenek написал 02.11.2024 в 20:17:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше (на 8%, и находит 84 миллиона вместо ответа в 34 миллиона с копейками)

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Откуда задача-то?

собес джуна на галеру

 

школьник спросил знакомый 

я ему накодил подсчёт суммы цифр в цикле через рекурсию, за 3 минуты программа до 20 миллионов доползла, добавил к рекурсии кеш рекурсии, сильно быстрее не стало 

сказал что подумаю на выходных и вот, сижу 5й час в ахуе 

Бля. Я к сожалению в таком не спец, однако верю, что это именно про то, что тебе нужно

https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property?noredirect=1&lq=1

  Just.Doit написал 02.11.2024 в 20:19:

  mercury23 написал 02.11.2024 в 20:10:

  Just.Doit написал 02.11.2024 в 20:03:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

не думал просто расписать все варианты того как можно получить число 159 суммой цифр, а затем посчитать количество перестановок?

если это только 18 и 19 числа то там не так уж и много вариантов

была такая идея

 

если бы число было близко к 171, то есть 170 или 169, то можно было бы перебрать, типа для 170 тасовать восьмерку, для 169  две восьмёрки или 1 семёрку

159 далековато от 171 и слишком дохуища перебрать наверное

 

помимо этого, это не решает проблему того, что число должно быть меньше 9223372036854775808 (2^63)

я про то, что для суммы в 170:

9 899 999 999 999 999 999 не подходит к примеру

8 999 999 999 999 999 999 подходит, так как меньше 2^63

 

 

> и слишком дохуища перебрать наверное

по прикидке - не очень. там их штук 100-200, кажется

их даже все можно расписать в качестве массивов

> помимо этого, это не решает проблему того, что число должно быть меньше

ну это уже вторая часть задачи. тоже решаемая кмк.

Показать больше  

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

  scarppy написал 02.11.2024 в 20:29:

я не знаю, за покраску кнопок готовы пол миллиона платить

когда этот школьник вырастет, ему чем платить будут? ввп россии?

 

он в итмо на курсы ходит, хочет на кафедру парфёнова поступать, короче немного нестандартный школьник

  Zhenek написал 02.11.2024 в 20:31:

  mercury23 написал 02.11.2024 в 20:28:

  Zhenek написал 02.11.2024 в 20:17:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше (на 8%, и находит 84 миллиона вместо ответа в 34 миллиона с копейками)

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Откуда задача-то?

собес джуна на галеру

 

школьник спросил знакомый 

я ему накодил подсчёт суммы цифр в цикле через рекурсию, за 3 минуты программа до 20 миллионов доползла, добавил к рекурсии кеш рекурсии, сильно быстрее не стало 

сказал что подумаю на выходных и вот, сижу 5й час в ахуе 

Показать больше  

Бля. Я к сожалению в таком не спец, однако верю, что это именно про то, что тебе нужно

 

https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property?noredirect=1&lq=1

сяп, ща почитаю

  mercury23 написал 02.11.2024 в 19:41:

 помогите позязя 

Рабочка

  mercury23 написал 02.11.2024 в 20:33:

  Zhenek написал 02.11.2024 в 20:31:

  mercury23 написал 02.11.2024 в 20:28:

  Zhenek написал 02.11.2024 в 20:17:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше (на 8%, и находит 84 миллиона вместо ответа в 34 миллиона с копейками)

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Откуда задача-то?

собес джуна на галеру

 

школьник спросил знакомый 

я ему накодил подсчёт суммы цифр в цикле через рекурсию, за 3 минуты программа до 20 миллионов доползла, добавил к рекурсии кеш рекурсии, сильно быстрее не стало 

сказал что подумаю на выходных и вот, сижу 5й час в ахуе 

Показать больше  

Бля. Я к сожалению в таком не спец, однако верю, что это именно про то, что тебе нужно

 

https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property?noredirect=1&lq=1

сяп, ща почитаю

Сам уже решай, на 1/2 или на 2/3 помог

  Zhenek написал 02.11.2024 в 20:46:

  mercury23 написал 02.11.2024 в 20:33:

  Zhenek написал 02.11.2024 в 20:31:

  mercury23 написал 02.11.2024 в 20:28:

  Zhenek написал 02.11.2024 в 20:17:

  mercury23 написал 02.11.2024 в 19:41:

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

 

короче задача - посчитать количество чисел от 1 до 2^63 с суммой цифр, равной 159

 

я допёр, что 2^63 это 19значное число, максимальная сумма цифр 19-значного числа это 171

18значного числа 162

17значного числа 153

 

таким образом это 18-19значные числа

 

если просто пробежать от 699 999 999 999 999 999 (минимальное 18значное число, сумма цифр которого 159) до 2^63 пробежать и посчитать сумму цифр, даже если это многопоточкой на 8 потоков на 8ядерном пека разбить, будет считаться несколько лет

 

обращался к чат гпт, он посоветовал сделать массив m*n, где m - количество цифр в числе, а n - сумма цифр в числе

и в теории этот массив можно заполнить, левый его верхний угол выглядит как-то так:

 

1    1    1     1      1      1      1    
1    2    3     4      5      6      7    
1    3    6     10   15    21    28   
1    4    10   20   35    56    84   
1    5    15   35   70    126  210  
1    6    21   56   126  252  462  

 

данное решение в ячейке [19][159] найдёт количество 19значных чисел, сумма цифр которых 159

в ячейке [18][159] найдёт количество 18значных чисел, сумма цифр которых 159

 

но если это сложить, то мы получим сумму цифр от 1 до 10^19 - 1

а 2^63 несколько меньше (на 8%, и находит 84 миллиона вместо ответа в 34 миллиона с копейками)

 

короче я встрял, 300к наносеки помогите позязя 

 

@Zhenek если поможешь хотя бы на 2/3 или даже 1/2 решить задачу, буду очень признателен

 

Откуда задача-то?

собес джуна на галеру

 

школьник спросил знакомый 

я ему накодил подсчёт суммы цифр в цикле через рекурсию, за 3 минуты программа до 20 миллионов доползла, добавил к рекурсии кеш рекурсии, сильно быстрее не стало 

сказал что подумаю на выходных и вот, сижу 5й час в ахуе 

Показать больше  

Бля. Я к сожалению в таком не спец, однако верю, что это именно про то, что тебе нужно

 

https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property?noredirect=1&lq=1

сяп, ща почитаю

Сам уже решай, на 1/2 или на 2/3 помог

там в твоей ссылке есть решение, для примера сумма цифр 60

вроде на 3/3 помог, получается

  Arzanis написал 02.11.2024 в 20:45:

  mercury23 написал 02.11.2024 в 19:41:

 помогите позязя 

  Показать содержимое

Конечно, вот пример псевдокода для вычисления количества чисел от 1 до \(2^{63} - 1\) с суммой цифр, равной 159. Этот подход использует динамическое программирование для подсчета способов формирования нужной суммы цифр, при этом учитывая ограничения, накладываемые на числа с максимальным количеством разрядов.

```plaintext
function count_numbers_with_digit_sum(limit, target_sum):
    # limit is 2^63 - 1
    # target_sum is 159

    # Convert limit to a string to easily work with its digits
    limit_str = str(limit)
    n = len(limit_str)  # Number of digits in limit
    
    # Create DP table: dp[pos][sum][tight]
    # - pos: current position in the number
    # - sum: current sum of the digits
    # - tight: whether the number formed so far is tightly bound to the limit
    dp = array of size [n+1][target_sum+1][2] initialized to 0

    # Base case: a sum of 0 is possible with 0 digits
    dp[0][0][1] = 1

    # Iterate over all positions
    for pos from 0 to n-1:
        for sum from 0 to target_sum:
            for tight in [0, 1]:
                limit_digit = int(limit_str[pos]) if tight == 1 else 9
                
                # Try adding each digit from 0 to limit_digit
                for digit from 0 to limit_digit:
                    new_tight = tight and (digit == limit_digit)
                    if sum + digit <= target_sum:
                        dp[pos+1][sum+digit][new_tight] += dp[pos][sum][tight]

    # Total count is the sum of numbers with exact digit sum and tightness not required
    result = dp[n][target_sum][0] + dp[n][target_sum][1]

    return result

# Calculate numbers with digit sum 159 within 2^63
result = count_numbers_with_digit_sum(2**63 - 1, 159)
print(result)
```

### Пояснение:

1. **DP-таблица:** Используется трехмерный массив `dp[pos][sum][tight]`, где:
   - `pos` — текущая позиция (индекс разряда) в формируемом числе.
   - `sum` — текущая сумма цифр.
   - `tight` — флаг, определяющий, ограничено ли текущее число цифрой в той же позиции в ограничении (1, если ограничено, иначе 0).

2. **Инициализация:** Начинаем с базы, где сумма 0 достижима без использования цифр (`dp[0][0][1] = 1`).

3. **Заполнение матрицы:** На каждой позиции рассматриваем добавление цифры в текущую сумму, беря во внимание, ограничено ли это ограничением или нет.

4. **Учет "tight"**: Если текущее число точно совпадает с верхним пределом в соответствующем разряде, сохраняется `tight`, иначе он снимается, позволяя любой цифре в этой позиции.

5. **Результат:** Количество чисел, сумма цифр которых равна `target_sum` и которые меньше или равны `limit`, содержится в `dp[n][target_sum][0] + dp[n][target_sum][1]`.

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

Рабочка

спасибо, завтра почитаю если с решением с стек оверфлоу затуплю

сабж можно клоз, всем огромная благодарность

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

 

def count_numbers_with_digit_sum(limit, target_sum):
    limit_digits = [int(d) for d in str(limit)]
    memo = {}

    def dp(pos, sum_so_far, tight, isStart):
        if sum_so_far > target_sum:
            return 0
        if pos == len(limit_digits):
            return int(isStart and sum_so_far == target_sum)
        key = (pos, sum_so_far, tight, isStart)
        if key in memo:
            return memo[key]
        total = 0
        max_digit = limit_digits[pos] if tight else 9
        for digit in range(0, max_digit + 1):
            new_tight = tight and (digit == limit_digits[pos])
            new_isStart = isStart or digit != 0
            if not new_isStart:
                # Leading zeros, don't add to sum
                total += dp(pos + 1, sum_so_far, new_tight, new_isStart)
            else:
                total += dp(pos + 1, sum_so_far + digit, new_tight, new_isStart)
        memo[key] = total
        return total

    return dp(0, 0, True, False)

def main():
    limit = 2 ** 63
    target_sum = 159
    result = count_numbers_with_digit_sum(limit, target_sum)
    print(result)

if __name__ == "__main__":
    main()

Ну это классическая задачка на динамику, под такие задачки даже более узкую тему придумали digit dp 

  Drakonian написал 02.11.2024 в 22:53:

не самый оптимальный/красивый

Ну да в питоне есть memo из коробки – декоратор @cache имбовая штука для решения дп задачек на литкоде 

  mercury23 написал 02.11.2024 в 20:33:

чатгпт поможет

Так сразу спросил бы у него в чем проблема

  thousand cursed enemies написал 02.11.2024 в 08:49:

На хаскеле и ассемблере пишут конченные долбоебы. Русвермы. 

haskell прям заебись на самом деле

я тут его в рамках курса по ФП прохожу и в целом мне кажется можно поставить

этого персонажа на пьедестал 'языки на которых приятно писать код' на равне с лиспом

но чтобы оценить охуенность происходящего, надо конечно почитать что-нибудь

хотя бы на тему формального интуиционистского исчисления высказываний

там (в теории доказательств) одна теорема [double negation translation], вернее её конструктивное доказательство

является предтечей хаскельных монад и монадических операций, а конкретно continuation monad

как выглядят те самые хаскел и лисп программисты в 2024 году

ну я не курю разве что, но в остальном ровно так я/мой рабочий стол и выглядят

  Drakonian написал 02.11.2024 в 22:53:

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

прикольно кстати, реально работает

но код конечно говно ваще мешанина)

по-человечески у нас задача делится на две части:

1. подсчет ответа на отрезке [0, 10^k - 1] (тривиально)

2. подсчет на произвольном отрезке [0, b] через пункт 1

from functools import cache


# up to n digits with digit sum of s
@cache
def unbounded(n, s):
    if n < 0 or s < 0:
        return 0
    if (n, s) == (0, 0):
        return 1

    return sum(
        unbounded(n - 1, s - d)
        for d in range(0, 10)
    )

# up to the bound 
# (maximum as list of digits)
def bounded(bound, s):
    n = len(bound)
    if n == 0:
        return int(s == 0)

    max_digit, *r = bound
    result = bounded(r, s - max_digit)

    for d in range(max_digit):
        result += unbounded(n - 1, s - d)

    return result

def cnt_digsum(num, sum):
    bound = [int(d) for d in str(num)]
    return bounded(bound, sum)

print(cnt_digsum(2**63, 159))

  Kurku написал 03.11.2024 в 11:07:

ну я не курю разве что, но в остальном ровно так я/мой рабочий стол и выглядят

сочувствую

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

  Arzanis написал 30.10.2024 в 14:22:

Кто работает в ВТБ меньше чем за 500, тот лох.

я как то собесился в втб на фронтенд чисто по приколу тех собес пройти, изи прошел но не хотел идти к ним как раз из за этой хуеты с анальным зондированием и вармами хуярмами
когда речь зашла об офере чисто по приколу сказал надо 800к что на тот момент было очень дохуя (в районе 2х лет назад), они подумали и согласились ,и было типа 500 в месяц нал остальное годовой премией добивается
я все равно послал нах их бля

  Tia написал 03.11.2024 в 20:28:

  Arzanis написал 30.10.2024 в 14:22:

Кто работает в ВТБ меньше чем за 500, тот лох.

я как то собесился в втб на фронтенд чисто по приколу тех собес пройти, изи прошел но не хотел идти к ним как раз из за этой хуеты с анальным зондированием и вармами хуярмами
когда речь зашла об офере чисто по приколу сказал надо 800к что на тот момент было очень дохуя (в районе 2х лет назад), они подумали и согласились ,и было типа 500 в месяц нал остальное годовой премией добивается
я все равно послал нах их бля

дурак

ради чего ты блять в айти то тогда работаешь? может пора становится гилфойлем? и просто гикать на линуксе ыыы