Начало
СоревнованияПодразделы
Другие разделы
Дата и время
16/11/2024 19:20:04
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]);
