mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
26 lines
732 B
Python
26 lines
732 B
Python
import math
|
|
def min_steps(x):
|
|
result = {}
|
|
result[1] = 0
|
|
|
|
for i in range(1, x + 1):
|
|
if result.get(i, -1) >= 0:
|
|
result[i + 3] = min(result.get(i+3, math.inf), result[i] + 1)
|
|
result[i * 2] = min(result.get(i*2, math.inf), result[i] + 1)
|
|
# print(f"i: {i}, curr: {result[i]}, +3 => {result[i+3]}, *2 => {result[i*2]}", x)
|
|
|
|
print(result.get(x, -1))
|
|
return result.get(x, -1)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
assert min_steps(1) == 0
|
|
assert min_steps(2) == 1
|
|
assert min_steps(3) == -1
|
|
assert min_steps(4) == 1
|
|
assert min_steps(5) == 2
|
|
assert min_steps(17) == 4
|
|
assert min_steps(42) == -1
|
|
assert min_steps(100) == 7
|
|
assert min_steps(1000) == 13
|