Подразделы

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

Дата и время

12/04/2025 13:10: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. Числа