1018 — это обычное 64-битное целое. long long в Си, long в Java, int64 в Delphi.
Очевидно, задача переводная, спичка не только match (это слово у них очень многозначное), но и matchstick. Причём переводил то ли автомат, то ли редкий надмозг, пример неговорящий, и откровенно непонятно: то ли где находится число 11, то ли что на 11-й позиции. Будем решать 2-ю задачу: что на 11-й позиции.
1. Определить количество разрядов (для этого хватает несложного цикла) и какой номер у данного числа среди N-значных чисел.
2. А теперь находим, сколько есть N-значных чисел из M спичек. Рекуррентное соотношение:
Q[N, M] = sum{k = 1..9} (Q[N−1, M−q(k)]), если N — найденная нами значность, но не 1-ца,
Для остальных N формула та же, но суммирование 0…9.
q(0) = 6, q(1) = 2, q(2) = 5, и т.д. — кол-во спичек в цифре.
Граничное условие: Q[0, 0] = 1, Q[0, M] = 0 для остальных M.
«Методом выкручивания рук» также примем, что для отрицательных M все Q равняются 0.
Решаем рекуррентное соотношение динамическим программированием.
3. А теперь самое интересное: воспользовавшись таблицей динамического программирования, находить цифру за цифрой, начиная со старшей.
Например, у нас 15-е число. Первый шаг опустим, поверьте мне: это 4-е двузначное, начиная с нуля.
2-й шаг.
Q[1,2] = 1
Q[1,3] = 1
Q[1,4] = 1
Q[1,5] = 3
Q[1,6] = 3
Q[1,7] = 1
Q[2,4] = 1
Q[2,5] = 2
Q[2,6] не вычислял, главное — запредельно большое.
Q[2,0]…Q[2,3] равняются нулю.
Вычитаем Q[2,4] — получается 3.
Вычитаем Q[2,5] — получается 1.
Вычитаем Q[2,6] — не получается. Итого у нас шесть спичек, остаётся 1.
3-й шаг, работаем по цифре.
Ноль, Q[1, 6−6] = 0. Остаётся 1.
Единица, Q[1, 6−2] = 1. Остаётся 0.
Двойка, Q[1, 6−5] = 0. Остаётся 0.
Тройка, Q[1, 6−5] = 0. Остаётся 0.
Четвёрка, Q[1, 6−4] = 1. Не вычитается, остаётся 2 спички, 1 знак и номер 0. Записываем цифру 4.
Ноль, Q[0, 2−5] = 0. Остаётся 0.
Единица, Q[0, 2−2] = 1. Не вычитается, остаётся 0 спичек, 0 знаков и номер 0. Записываем цифру 1.
Итого получили 41.
Простой
