Блог пользователя Wassup

Автор Wassup, история, 4 года назад, По-русски

UPD: Большое спасибо за помощь, наконец разобрался что к чему. Всем привет! У меня появился интересный вопрос. 401D - Роман и числа в данной задаче если коротко, то у нас есть два целых числа N и M, мы должны посчитать количество чисел, которые могут быть получены из числа N перестановкой цифр, и которые делятся на M. Решение "в лоб" — просто пробежаться по всем перестановкам цифр числа N и проверить каждую. Это дает нам (количествоцифр_N)!! операций. Интуитивно понятно, что нам в любом случае придётся проверить каждую из перестановок и я не могу понять, как мы этого избегаем?_

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Вот именно за этим и нужно дп — избегать перебора. К тому же, в ващем лучае асимптотика не N!, а (количество_цифр_N)!, что не супер много