Матч 334, Расширенное счастливое число

(ExtendedHappyNumbers)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 2

 

Дано натуральное число n. Возведем в k - ую степень каждую его цифру и просуммируем полученные результаты. Обозначим результат через Sk(n). Например, S2(65) = 62 + 52 = 61. Построим последовательность n, Sk(n), Sk(Sk(n)), … . Счастьем числа n по отношению к k будем называть наименьшее число в этой последовательности.

По заданным числам a, b и k следует найти счастье каждого числа между a и b включительно по отношению к k и вернуть их сумму.

 

Класс: ExtendedHappyNumbers

Метод: long long calcTheSum(int a, int b, int k)

Ограничения: 1 £ a, b £ 106, 1 £ k £ 6.

 

Вход. Три числа a, b, k.

 

Выход. Найти счастье каждого числа между a и b включительно по отношению к k и вернуть их сумму.

 

Пример входа

a

b

k

13

13

2

1

5

2

535

538

3

 

Пример выхода

1

14

820

 

 

РЕШЕНИЕ

динамическое программирование

 

Поскольку значение k в процессе вычислений фиксировано, заведем массив powk, в котором powk[i] = ik. Им будет удобно пользоваться при вычислении значений Sk(n) в функции sum(n). Наибольшее значение, которое могут принимать элементы последовательности n, Sk(n), Sk(Sk(n)), …, не больше 4*106, так как даже при k = 6 значение S6(n) при n <  4*106 не больше 36 + 6*96 = 3189375 < 4*106.

Заведем массив f[4000000], в котором будем хранить f[i] = Sk(i). Рассмотрим для некоторого i последовательность a0 = i, a1 = Sk(i), a2 = Sk(Sk(n)), … . Очевидно, что найдутся такие индексы s и t (пусть s < t для определенности), что as = at. Тогда f[ak], (0 £ k £ t) положим равным минимуму среди чисел ak, ak+1, …, at. При этом начиная вычислять значение f[a0], в процессе мы находим все значения f[ak], 0 £ k £ t.

Описанную процедуру совершаем в функции g. Значение f[i] считается вычисленным, если f[i] > 0. При первом проходе по числам a0, …, at устанавливаем f[ai] = -1. Дойдя до at = as, продолжаем путь as , as+1, …, at, устанавливая f[ai] = ai для s £ i £ t. Когда вторично дойдем до f[at], значение этой ячейки уже будет положительным и рекурсия начнет раскручиваться назад. Двигаясь назад по кольцу дважды от at до as, а потом и до a0, устанавливаем f[ai] в наименьшее значение среди чисел ai, ai+1, …, at.

 

ПРОГРАММА

 

#include <cstdio>

#include <algorithm>

#define MAX 5000001

using namespace std;

 

int powk[10], f[MAX], ptr;

 

int sum(int n)

{

  int s;

  for(s = 0; n; n /= 10)

    s += powk[n % 10];

  return s;

}

 

int g(int n)

{

  if (f[n] > 0) return f[n]; else

  if (f[n] == 0) f[n] = -1; else

  if (f[n] == -1) f[n] = n;

  return f[n] = min(n,g(sum(n)));

}

 

class ExtendedHappyNumbers

{

public:

  long long calcTheSum(int a, int b, int k)

  {

    int i, j, s;

    long long res = 0;

    for(i = 0; i < 10; i++)

    {

      for(s = 1, j = 0; j < k; j++) s *= i;

      powk[i] = s;

    }

    for(i = a; i <= b; i++)

      res += g(i);

    return res;

  }

};