#43 Problem
** Thoughts ** I couldn't solve it during the contest. I think this problem is difficult because I can't write the code to generate the run-run numbers. I couldn't write either. According to the commentary, it seems to pay attention to the remainder divided by 10 and 9. When the remainder of dividing $ x $ by 10 is 0, the ones digit becomes 0 and the number of runruns that can be generated decreases. Similarly, when the remainder of dividing $ x $ by 9 is 0, the number of run-runs that can be generated decreases. Because, when the ones place is 0, there are only 0 and 1 run-run numbers such that the difference between adjacent numbers is 1. Even when it is 9, there are only 8 and 9. If you organize what kind of run-run number is generated for each,
x != 0 mod(10) → 10x+(x%10)-1
x != 9 mod(10) → 10x+(x%10)+1
It will be. If you implement this
from collections import deque
k = int(input())
lun = deque([])
for i in range(1,10):
lun.append(i)
for i in range(k):
x = lun.popleft()
if x % 10 != 0:
lun.append(10*x+(x%10)-1)
lun.append(10*x+x%10)
if x % 10 != 9:
lun.append(10*x+(x%10)+1)
print(x)
I'm using deque because I only access both ends of the data
I wanted to solve it in production. I am not good at calculations using remainders, so I will practice around integer problems. see you.
Recommended Posts