Возможно ли решить данную задачу?

Добрый день.
На днях в городе(Ташкент) прошла олимпиада.
И попалась следующая задача,
смущает лишь то, что на входе число в промежутке от 1 до 10 в 18 степени( внизу указано ).
И дано лишь 2 секунды.
Результат проверяет машина, и подставляет самые различные значения.
Если же решение возможно, то прошу направить меня на решение данной задачи.

68892fbeab104d22bcf8de38ada0cc45.jpg
  • Вопрос задан
  • 3720 просмотров
Решения вопроса 2
@Mercury13
Программист на «си с крестами» и не только
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.
Ответ написан
@BorisKorobkov
Web developer
Ну наконец-то хоть одна нормальная задачка, а то все какой-то бред от нубов, не умеющих отличить переменную от функции.

Вот мое решение нахождение ИНДЕКСА по ЧИСЛУ
Перебор в лоб: sandbox.onlinephpfunctions.com/code/564a9c5441c3f3...
Оптимизированный вариант: sandbox.onlinephpfunctions.com/code/5d1986edffd300...
Там же можно его позапускать прямо из браузера (надо выбрать PHP 7).
Результат запуска
Число 0, его порядковый номер 7
Число 1, его порядковый номер 1
Число 2, его порядковый номер 4
Число 3, его порядковый номер 5
Число 4, его порядковый номер 3
Число 5, его порядковый номер 6
Число 6, его порядковый номер 8
Число 7, его порядковый номер 2
Число 8, его порядковый номер 10
Число 9, его порядковый номер 9
Число 10, его порядковый номер 25
Число 11, его порядковый номер 11
Число 12, его порядковый номер 17
Число 13, его порядковый номер 18
Число 14, его порядковый номер 14
Число 15, его порядковый номер 19
Число 16, его порядковый номер 26
Число 17, его порядковый номер 12
Число 18, его порядковый номер 37
Число 19, его порядковый номер 27
Число 20, его порядковый номер 66


А это, наоборот, нахождение ЧИСЛА по ИНДЕКСУ
Перебор в лоб: sandbox.onlinephpfunctions.com/code/3ffc2cc919fb4d...
Выводит:
Результат запуска
Порядковый номер 1, число 1
Порядковый номер 2, число 7
Порядковый номер 3, число 4
Порядковый номер 4, число 2
Порядковый номер 5, число 3
Порядковый номер 6, число 5
Порядковый номер 7, число 0
Порядковый номер 8, число 6
Порядковый номер 9, число 9
Порядковый номер 10, число 8
Порядковый номер 11, число 11
Порядковый номер 12, число 17
Порядковый номер 13, число 71
Порядковый номер 14, число 14
Порядковый номер 15, число 41
Порядковый номер 16, число 77
Порядковый номер 17, число 12
Порядковый номер 18, число 13
Порядковый номер 19, число 15
Порядковый номер 20, число 21
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@aslan7470
Ненадо там ничего считать
для I от 0 до 9 на I-м месте число из одной цифры, для записи которой требуется I-е по счету кол-во спичек
поменяй так каждую из введенных цифр позиции
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы