diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py b/AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py new file mode 100644 index 0000000..3451956 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py @@ -0,0 +1,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=' ') |