B - Sum of Digits Sequence 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

正整数 x に対して、f(x) を x の十進表記における各桁の和として定義します。例えば、f(123) = 1 + 2 + 3 = 6 です。

無限数列 A = (A_0, A_1, A_2, \ldots) を以下の式により定義します。

  • A_0 = 1
  • i \geq 1 のとき A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

正整数 N が与えられます。A_N の値を求めてください。

制約

  • N は 1 以上 100 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

6

出力例 1

23
  • A_0 = 1
  • A_1 = f(A_0) = 1
  • A_2 = f(A_0) + f(A_1) = 2
  • A_3 = f(A_0) + f(A_1) + f(A_2) = 4
  • A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
  • A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
  • A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

であるため、A_6 = 23 です。

入力例 2

45

出力例 2

427

Score : 200 points

Problem Statement

For a positive integer x, define f(x) as the sum of the digits in the decimal representation of x. For example, f(123) = 1 + 2 + 3 = 6.

Define an infinite sequence A = (A_0, A_1, A_2, \ldots) by the following formula:

  • A_0 = 1
  • For i \geq 1, A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

You are given a positive integer N. Find the value of A_N.

Constraints

  • N is an integer between 1 and 100, inclusive.

Input

The input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

6

Sample Output 1

23
  • A_0 = 1
  • A_1 = f(A_0) = 1
  • A_2 = f(A_0) + f(A_1) = 2
  • A_3 = f(A_0) + f(A_1) + f(A_2) = 4
  • A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
  • A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
  • A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

Thus, A_6 = 23.

Sample Input 2

45

Sample Output 2

427