CSES - Steps

Consider again the machine of the preceding task. How many different ways there are to produce a number xx?

For example, x=17x=17 can be produced in the following ways:

  • 124714171 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 14 \rightarrow 17
  • 12481114171 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 11 \rightarrow 14 \rightarrow 17
  • 12581114171 \rightarrow 2 \rightarrow 5 \rightarrow 8 \rightarrow 11 \rightarrow 14 \rightarrow 17
  • 14714171 \rightarrow 4 \rightarrow 7 \rightarrow 14 \rightarrow 17
  • 1481114171 \rightarrow 4 \rightarrow 8 \rightarrow 11 \rightarrow 14 \rightarrow 17

In this case, the answer is 55.

In a file allsteps.py, implement the function count_steps that returns the number of ways to produce the number xx.

The function should be efficient when xx is in the range 110001 \dots 1000.

def count_steps(x):
    # TODO

if __name__ == "__main__":
    print(count_steps(1)) # 1
    print(count_steps(2)) # 1
    print(count_steps(3)) # 0
    print(count_steps(4)) # 2
    print(count_steps(5)) # 1
    print(count_steps(17)) # 5
    print(count_steps(42)) # 0
    print(count_steps(100)) # 242
    print(count_steps(1000)) # 2948311