Basic-Algorithms-in-Python/primitive_calculator.py at master · shilpakbanerjee/Basic-Algorithms-in-Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Uses python3
import sys

def optimal_sequence(n):
    sequence = []
    while n >= 1:
        sequence.append(n)
        if n % 3 == 0:
            n = n // 3
        elif n % 2 == 0:
            n = n // 2
        else:
            n = n - 1
    return reversed(sequence)

def dynamic_optimal_sequence(n):
    op = [[n+10,0],[0,1]]
    for i in range(2,n+1):
        temp = [0,0,0]

        if i % 2 == 0:
            temp[0] = i // 2
        else:
            temp[0] = 0

        if i % 3 == 0:
            temp[1] = i // 3
        else:
            temp[1] = 0

        temp[2] = i-1

        op_temp = [op[temp[0]][0], op[temp[1]][0], op[temp[2]][0]]
        prev_number = temp[op_temp.index(min(op_temp))]


        op.append([op[prev_number][0]+1]+op[prev_number][1:]+[i])
        #print(op)

    return op[n][1:]


input = sys.stdin.read()
n = int(input)
sequence = list(dynamic_optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
    print(x, end=' ')