blob: 3451956fe4abbdb334a0d6eb5d46b0a634d92ef3 (
plain)
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
|
# Uses python3
import sys
def optimal_sequence(n):
sequence = []
stepsCount = [0] * n
path = [0] * n
for i in range(1, n):
j = i + 1;
div2Steps = float('inf')
div3Steps = float('inf')
if j % 3 == 0:
div3Steps = stepsCount[j // 3 - 1]
if j % 2 == 0:
div2Steps = stepsCount[j // 2 - 1]
minus1Steps = stepsCount[i - 1]
stepCountAndType = [(minus1Steps, 1), (div2Steps, 2), (div3Steps, 3)]
stepCountAndType.sort()
stepsCount[i] = stepCountAndType[0][0] + 1
path[i] = stepCountAndType[0][1]
sequence.append(n)
while n > 1:
i = path[n - 1]
if i == 3:
n = n // 3
sequence.append(n)
continue
if i == 2:
n = n // 2
sequence.append(n)
continue
n = n - 1
sequence.append(n)
return reversed(sequence)
input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
print(x, end=' ')
|
