Числа - 2

Эта задача имеет динамическое решение, суть которого заключается в следующем. Будем считать, что нам уже известно значение d[j] - количество возможных разбиений на числа строки, состоящей из первых j цифр исходной строки s для всех j, меньших i. Нам предстоит определить значение d[i] на основании меньших, ранее вычисленных значений d[j]. Таким образом, при увеличении значения i мы получим ответ на задачу в момент когда i будет равно n. В качестве начальных значений можно положить, что d[0]=1 (считаем, что при отсутствии цифр существует только одно разбиение).

Поскольку в качестве последнего числа может служить число, состоящее не более чем из 9 цифр, то на i-м шаге можно рассмотреть все варианты чисел, на которые может оканчиваться разбиение на числа последовательности из первых i символов строки s. Понятно, что количество разбиений, оканчивающихся на конкретное число, соответствующее последним t цифрам строки s, в точности равно d[i-t]. Таким образом, d[i] будет равно сумме всех таких разбиений при различной длине последнего числа в последовательности. При этом следует исключить из суммы те последние числа, которые превышают значение c, а так же те, которые начинаются с нуля (кроме самого нуля). Помимо этого, в процессе вычислений d[i] следует каждый раз вычислять остаток от деления на 10^k (брать только последние k цифр числа), что позволит избежать переполнения.

Описанная выше идея может быть оформлена следующим образом:

  read(n,c,k,s);             //чтение данных
  d[0]=1;                    
  for i=1..n{                //цикл по номеру цифры строки s
    d[i]=0;
    for j=i-9..i-1           //цикл по началу возможного последнего числа
      if(s[j+1]>0 or j=i-1){ //если последнее число не имеет лидирующего нуля
        x=s[j+1..i];         //извлекаем последнее число из строки
        //если это число не больше c, то учитываем в сумме все последовательности, на него оканчивающиеся
        if(x<=c) d[i] = (d[i]+d[j]) mod 10^k; 
      }
  }
  write(d[n]);

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