Подразделы

Другие разделы

Дата и время

29/04/2024 20:48:59

Авторизация

7. Числа

Задача средней сложности на динамическое программирование.

Если существует `k` способов получить последовательность из `(i-1)` символа и число с позиции `i` до позиции `j` не превышает `C`, то `k` способов должно быть добавлено к числу способов получения последовательности из `j` символов. Суммирование нужно выполнять по модулю `10^k`. Рассматриваем все возможные `i` и `j` `(0\ ≤\ i\ ≤\ j\ ≤\ n)` и заполняем таблицу `t` с результатами. По окончании выводим значение `t_n`.

var
  c,n,k,v,i,j:longint;
  s:string;
  t:array[0..50000] of int64;
  p:int64;
...
  readln(n,c,k);
  readln(s);
  { вычисляем 10^k }
  p:=1;
  for i:=1 to k do
    p:=p*10;
  { основной цикл: заполнение таблицы }
  t[0]:=1;
  for i:=1 to n do
  begin
    v:=0;
    for j:=i to n do
    begin 
      { увеличиваем значения всех ячеек, достижимых с позиции i }
      v:=v*10+ord(s[j])-ord('0');
      if v>c then break;  
      t[j]:=(t[j]+t[i-1]) mod p;
      if s[i]='0' then break; { c 0 достижима только следующая ячейка }
    end;
  end;
  writeln(t[n]);

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

7. Числа