Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Без двух нулей подряд

(Время: 1 сек. Память: 16 Мб Сложность: 37%)

Для решения данной задачи используем метод динамического программирования. Пусть d[i] - количество чисел, состоящих ровно из i цифр и оканчивающихся на цифру, отличную от нуля. Аналогично, обозначим через d0[i] количество i-значных чисел, оканчивающихся на нуль. При этом будем рассматривать только те числа, которые не содержат в своей записи двух нулей подряд. Так же не будем рассматривать числа с лидирующими нулями, даже в том случае, когда i=1 (так как у нас n>1). Тогда очевидно, что d[1]=k-1 и d0[1]=0. Теперь мы можем выразить d[i] и d0[i] через d[i-1] и d0[i-1] следующим образом: d[i] = (d[i-1]+d0[i-1])*(k-1), d0[i] = d[i-1]. Используя данные рекуррентные соотношения, мы можем линейно, пробегая по i от 2 до n, вычислить d[n] и d0[n]. Ответом на задачу будет значение d[n]+d0[n]. Вышеописанный алгоритм решения представим в следующей форме:

  read(n,k)
  d[1]=k-1; d0[1]=0
  for i=2..n{
    d[i] = (d[i-1]+d0[i-1])*(k-1)
    d0[i] = d[i-1]
  }
  write(d[n]+d0[n])

Следует заметить, что ограничения на n и k в задаче позволяют использовать 4-байтовый целый тип для всех переменных. Использование массивов в данной задаче так же не обязательно, так как вычисляемые значения на i-м шаге зависят только от (i-1)-го шага.


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru