Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,m  =map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
ans = 0

for k in range(m):
	a[n-1]=a[n-1]//2
	a.sort()

for i in range(n):
	ans+=a[i]

print(ans)


Fixed submission:
import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


print(-sum(a))

Buggy python submission (verdict: Runtime Error):
n,m  =map(int,input().split())
a = [int(i) for i in input().split()]

ans = 0

for k in range(m):
		max(a)=max(a)//2


for i in range(n):
	ans+=a[i]

print(ans)


Fixed submission:
import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


print(-sum(a))

Buggy python submission (verdict: Runtime Error):
n,m  =map(int,input().split())
a = [int(i) for i in input().split()]

ans = 0

for _ in range(m):
		max(a)=max(a)//2


for i in range(n):
	ans+=a[i]

print(ans)


Fixed submission:
import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


print(-sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n,m  =map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
ans = 0

for _ in range(m):
		a[n-1]=a[n-1]//2
		a.sort()

for i in range(n):
	ans+=a[i]

print(ans)


Fixed submission:
import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


print(-sum(a))
Buggy python submission (verdict: Runtime Error):
a,b = map(int,input().split())
c =

if b<=1:
	print("0")
else:
	while 1+(a-1)*c<b:
		c=c+1


print(c)

Fixed submission:
a,b = map(int,input().split())
c =1

if b==1:
	c =0
else:
	while 1+(a-1)*c<b:
		c=c+1


print(c)
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = [int (i) for i in input().split()]
ans=0

l=[]

if n==1:
	print("0")

else:
	for i in range(1,n):
		if h[i-1] >= h[i]:

			ans+=1

			if i==n-1:
				l.append(ans)

		else:

			l.append(ans)

			ans=0

print(max(l))

Fixed submission:
n = int(input())
h = [int (i) for i in input().split()]
ans=0

l=[]

if n==1:
	l.append(ans)

else:
	for i in range(1,n):
		if h[i-1] >= h[i]:

			ans+=1

			if i==n-1:
				l.append(ans)

		else:

			l.append(ans)

			ans=0

print(max(l))

Buggy python submission (verdict: Runtime Error):
n = int(input())
h = [int (i) for i in input().split()]
ans=0

l=[]

for i in range(1,n):
	if h[i-1] >= h[i]:

		ans+=1

		if i==n-1:
			l.append(ans)

	else:

		l.append(ans)

		ans=0

print(max(l))


Fixed submission:
n = int(input())
h = [int (i) for i in input().split()]
ans=0

l=[]

if n==1:
	l.append(ans)

else:
	for i in range(1,n):
		if h[i-1] >= h[i]:

			ans+=1

			if i==n-1:
				l.append(ans)

		else:

			l.append(ans)

			ans=0

print(max(l))

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int (i) for i in input().split()]
ans=[]
b =0
for i in range(1,n):
	for j in range(i+1,n):
		if a[j-1]>=a[j]:
			b+=1
	ans.append(b)
	b=0

print(max(ans))

Fixed submission:
n = int(input())
h = [int (i) for i in input().split()]
ans=0

l=[]

if n==1:
	l.append(ans)

else:
	for i in range(1,n):
		if h[i-1] >= h[i]:

			ans+=1

			if i==n-1:
				l.append(ans)

		else:

			l.append(ans)

			ans=0

print(max(l))
Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)
for i in range(0,n-1):
	if i == n-2:
		if s[i] == s[i+1]:
			n-=1
		break
	if s[i]==s[i+1]:
		s[i+1]+=s[i+2]
		s.pop(i+2)
		n-=1
print(n)8

Fixed submission:
s = list(input())
ans = 0
length = 1
Si = s[0]
loop = [0]
for i in loop:
	Si_1 = ""
	for j in range(0,length):
		Si_1 += s[i+1+j]
	if Si == Si_1:
		length += 1
		i -= 1
		loop.append(i+1)
	else:
		ans += 1
		i += length - 1
		length = 1
		Si = Si_1
		loop.append(i+1)
	if i + length + 1 == len(s):
		ans += 1
		break
print(ans)

Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)
for i in range(0,n-2):
	if i == n-2:
		if s[i] == s[i+1]:
			n-=1
		break
	if s[i]==s[i+1]:
		s[i+1]+=s[i+2]
		s.pop(i+2)
		n-=1
print(n)

Fixed submission:
s = list(input())
ans = 0
length = 1
Si = s[0]
loop = [0]
for i in loop:
	Si_1 = ""
	for j in range(0,length):
		Si_1 += s[i+1+j]
	if Si == Si_1:
		length += 1
		i -= 1
		loop.append(i+1)
	else:
		ans += 1
		i += length - 1
		length = 1
		Si = Si_1
		loop.append(i+1)
	if i + length + 1 == len(s):
		ans += 1
		break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = [int(input()) for i in range(n)]

for i in (a):
	b = max(a)
	if i ==b:
		print(sorted(a)[-2])
	else:
		print(b)

Fixed submission:
n = int(input())

a = [int(input()) for l in range(n)]
b = max(a)
c = sorted(a)[-2]
for i in (a):
	if not i==b:
		print(b)
	else:
		print(c)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = [int(input()) for i in range(n)]

for i in (a):
	b = max(a)
	if i ==b:
		print(sorted(a)[-2])
	else:
		print(b)

Fixed submission:
n = int(input())

a = [int(input()) for l in range(n)]
b = max(a)
c = sorted(a)[-2]
for i in (a):
	if not i==b:
		print(b)
	else:
		print(c)
Buggy python submission (verdict: Runtime Error):
N,K=map(int, input().split(" "))
ans = N - K + 1
input(ans)    

Fixed submission:
N, K = map(int, input().split(" "))
ans = N-K+1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = list(map(int, input().split(" ")))

ans = float("ïnf")
for i in a:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") -1)

print(ans)

Fixed submission:
N = int(input())

a = list(map(int, input().split(" ")))

ans = float('inf')

for i in a:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)

print(round(ans))
Buggy python submission (verdict: Runtime Error):
A, B, C, K = map(int, input().split())
ABC_total = 0
A_list = [1,] * A
B_list = [0,] * B
C_list = [-1,] * C
ABC_list = A_list + B_list + C_list
for i in range(K):
  ABC_total += ABC_list[i]
print(ABC_total)


Fixed submission:
A, B, C, K = map(int, input().split())
if A >= K:
  print(K)
elif A + B >= K:
  print(A)
else:
  print(A - (K - A - B))

Buggy python submission (verdict: Time Limit Exceeded):
A, B, C, K = map(int, input().split())
ABC_total = 0
ABC_list =[]
for i in range(A):
  ABC_list.append(1)
for i in range(B):
  ABC_list.append(0)
for i in range(C):
  ABC_list.append(-1)
for i in range(K):
  ABC_total += ABC_list[i]
print(ABC_total)

Fixed submission:
A, B, C, K = map(int, input().split())
if A >= K:
  print(K)
elif A + B >= K:
  print(A)
else:
  print(A - (K - A - B))
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
fn = {i+1:0 for i in range(N)}
rtN = int(math.sqrt(N))+1

def n(x,y,z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

for x in range(1, rtN):
    for y in range(1, rtN):
        for z in range(1, rtN):
            n_ = n(x,y,z)
            try:
                f[n_] += 1
            except KeyError:
                pass

for k in fn.values():
    print(k)

Fixed submission:
import math
N = int(input())
fn = {i+1:0 for i in range(N)}
rtN = int(math.sqrt(N))+1

def n(x,y,z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

for x in range(1, rtN):
    for y in range(1, rtN):
        for z in range(1, rtN):
            n_ = n(x,y,z)
            try:
                fn[n_] += 1
            except KeyError:
                pass

for k in fn.values():
    print(k)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = sorted(map(int, input().split()))

dp = [True] * (A[-1] + 1)
for a in A:
    if dp[a] == True:
        n = 2
        while n * a <= A[-1]:
            dp[n * a] = False
            n += 1

score = 0
for a in A:
    score += dp[a] * (A.count(a) == 1)
    
print(score)

Fixed submission:
import collections

N = int(input())
A = sorted(map(int, input().split()))

dp = collections.defaultdict(lambda: True)

for i in range(N):
    if i < N - 1 and A[i] == A[i + 1]:
        dp[A[i]] = False
    k = 2
    while True:
        if A[i] * k > A[-1]:
            break
        else:
            dp[A[i] * k] = False
            k += 1

print(sum(dp[a] for a in A))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = sorted(map(int, input().split()))

dp = [True] * (A[-1] + 1)
for a in A:
    n = 2
    while n * a <= A[-1]:
        dp[n * a] = False
        n += 1

score = 0
for a in A:
    score += dp[a] * (A.count(a) == 1)
    
print(score)

Fixed submission:
import collections

N = int(input())
A = sorted(map(int, input().split()))

dp = collections.defaultdict(lambda: True)

for i in range(N):
    if i < N - 1 and A[i] == A[i + 1]:
        dp[A[i]] = False
    k = 2
    while True:
        if A[i] * k > A[-1]:
            break
        else:
            dp[A[i] * k] = False
            k += 1

print(sum(dp[a] for a in A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
  e = 1
  while n >= (p ** e) and n % (p ** e) == 0:
    n = n // (p ** e)
    score += 1
    e += 1
  else:
    p = p + 1 if p == 2 else p + 2
else:
  if sum([n % (i + 1) == 0 for i in range(p+1, n)]) == 1:
    score += 1
print(score)

Fixed submission:
a, b = map(int, input().split())
print(a * b)

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input())
print(a * b)

Fixed submission:
a, b = map(int, input().split())
print(a * b)
Buggy python submission (verdict: Runtime Error):
N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
  e = 1
  print(n, p, e)
  while n >= (p ** e) 
and n % (p ** e) == 0:
    n = n // (p ** e)
    score += 1
    e += 1
  else:
    p = p + 1 if p == 2 else p + 2
else:
  if n != 1:
    score += 1
print(score)

Fixed submission:
N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
  e = 1
  # print(n, p, e)
  while n >= (p ** e) and n % (p ** e) == 0:
    n = n // (p ** e)
    score += 1
    e += 1
  else:
    while n >= p and n % p == 0:
      n = n // p
    p = p + 1 if p == 2 else p + 2
else:
  if n != 1:
    score += 1
print(score)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
p, score = 2, 0
while p <= N:
  e = 1
  while p ** e <= N:
    # print(p, e, N, score)
    if N % (p ** e):
      break
    else:
      N = N // (p ** e)
      score += 1
      e += 1
      # print('tasu')
      # print(p, e, N, score)
  else:
    p += 1
print(score)

Fixed submission:
N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
  e = 1
  # print(n, p, e)
  while n >= (p ** e) and n % (p ** e) == 0:
    n = n // (p ** e)
    score += 1
    e += 1
  else:
    while n >= p and n % p == 0:
      n = n // p
    p = p + 1 if p == 2 else p + 2
else:
  if n != 1:
    score += 1
print(score)
Buggy python submission (verdict: Runtime Error):
print(input().replase('?', 'D'))

Fixed submission:
print(input().replace('?', 'D'))

Buggy python submission (verdict: Runtime Error):
print(input().replase('?', 'D')

Fixed submission:
print(input().replace('?', 'D'))
Buggy python submission (verdict: Runtime Error):
print('ARC' if input() != 'ABC else 'ABC')

Fixed submission:
S = input()
print('ARC' if S == 'ABC' else 'ABC')

Buggy python submission (verdict: Runtime Error):
S = input()
print('ARC' if S != 'ABC else 'ABC')

Fixed submission:
S = input()
print('ARC' if S == 'ABC' else 'ABC')
Buggy python submission (verdict: Runtime Error):
S = input()
print(sum([int(S[i:j])  % 2019 == 0 for i in range(len(S)) for j in range(i, len(S) + 1) if i < j]))

Fixed submission:
S, W = map(int, input().split())
print('safe' if S > W else 'unsafe')

Buggy python submission (verdict: Runtime Error):
A, B, C, D = map(int, input().split())
while A > 0 and C > 0:
  C -= B
  A -= D
print('Yes' if C <= 0 else 'No' )

Fixed submission:
S, W = map(int, input().split())
print('safe' if S > W else 'unsafe')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import math
def main():
    N = int(input())
    max_x = 100
    max_y = 100
    ans = [0] * N
    for x in range(1, max_x+1):
        for y in range(1, max_y+1):
            for i in range(N):
                a, b = divmod(x**2 + y**2 + x*y - (i+1), -1 * (x+y))
                a = 1
                b = x + y
                c = x**2 + y**2 + x*y - (i+1)
                d = b**2 - 4 * a * c
                if d < 0:
                    continue
                z1 = -1 * (a+b) + math.sqrt(d)
                z2 = -1 * (a+b) - math.sqrt(d)
                if (z1.is_integer() and z1 > 0) or (z2.is_integer() and z2 > 0):
                    ans[i] += 1
    for ni in ans:
        print(ni)
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    max_x = 100
    max_y = 100
    max_z = 100
    ans = [0] * N
    for x in range(1, max_x+1):
        for y in range(1, max_y+1):
            for z in range(1, max_z+1):
                a = (x+y+z)**2 - x*y - y*z - z*x
                if 1 <= a <= N:
                    ans[a-1] += 1
    for ni in ans:
        print(ni)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    for a in A:
        ans *= a
    if ans > 10 ** 18:
        print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    INF = 10 ** 18
    ans = 1
    is_INF = False
    for a in A:
        ans *= a
        if ans > INF:
            is_INF = True
            break
    if is_INF:
        if 0 in A:
            print(0)
        else:
            print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    T = input().rstrip()
    T_list = []
    for i, c in enumerate(T):
        if i == 0:
            T_list.append(c)
            continue
        if c == "?":
            if T_list[i-1] == "P":
                T_list.append("D")
            elif T_list[i-1] == "D":
                T_list.append("P")
            continue
        T_list.append(c)
    print("".join(T_list))
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    T = list(input().rstrip())
    ans = ["D" if c == "?" else c for c in T]
    print("".join(ans))
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    A, B, C, K = map(int, input().split())
    nums = []
    for _ in range(A):
        nums.append(1)
    for _ in range(B):
        nums.append(0)
    for _ in range(C):
        nums.append(-1)
    nums.sort(reverse=True)
    print(sum(nums[:K]))
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    A, B, C, K = map(int, input().split())
    rest = K
    ans = 0
    ans += min(A, rest)
    if K > A:
        rest -= A
        if rest > B:
            rest -= B
            ans -= min(rest, C)
    print(ans)
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    A, B, C, K = map(int, input().split())
    nums = [1] * A + [0] * B + [-1] * C
    nums.sort(reverse=True)
    print(sum(nums[:K]))
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
    A, B, C, K = map(int, input().split())
    rest = K
    ans = 0
    ans += min(A, rest)
    if K > A:
        rest -= A
        if rest > B:
            rest -= B
            ans -= min(rest, C)
    print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import Counter
from collections import defaultdict
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        d = defaultdict(int)
        d[0] += 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
            d[D[i+1]] += 1
        for v in d.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10
            tenpow %= P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10 % P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10
            tenpow %= P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def main():
    N = int(input())
    S = input().rstrip("\r\n")
    R = []
    G = []
    B = []
    for i, s in enumerate(S):
        if s == "R":
            R.append(i)
        elif s == "G":
            G.append(i)
        else:
            B.append(i)
    ans = len(R) * len(G) * len(B)
    for i in range(len(R)):
        for j in range(len(G)):
            diff = G[j] - R[i]
            left = 0
            right = len(B)
            exists_same = False
            while left < right:
                m = (left + right) // 2
                if B[m] - G[j] == diff:
                    exists_same = True
                    break
                elif B[m] - G[j] > diff:
                    right = m
                elif B[m] - G[j] < diff:
                    left = m + 1
            if exists_same:
                ans -= 1
    for i in range(len(R)):
        for j in range(len(B)):
            diff = B[j] - R[i]
            left = 0
            right = len(G)
            exists_same = False
            while left < right:
                m = (left + right) // 2
                if G[m] - B[j] == diff:
                    exists_same = True
                    break
                elif G[m] - B[j] > diff:
                    right = m
                elif G[m] - B[j] < diff:
                    left = m + 1
            if exists_same:
                ans -= 1
    for i in range(len(B)):
        for j in range(len(G)):
            diff = B[j] - R[i]
            left = 0
            right = len(R)
            exists_same = False
            while left < right:
                m = (left + right) // 2
                if R[m] - B[j] == diff:
                    exists_same = True
                    break
                elif R[m] - B[j] > diff:
                    right = m
                elif R[m] - B[j] < diff:
                    left = m + 1
            if exists_same:
                ans -= 1
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def main():
    N = int(input())
    S = input().rstrip("\r\n")
    R = []
    G = []
    B = []
    for i, s in enumerate(S):
        if s == "R":
            R.append(i)
        elif s == "G":
            G.append(i)
        else:
            B.append(i)
    ans = len(R) * len(G) * len(B)
    for i in range(N):
        for j in range(i+1, N):
            k = 2 * j - i
            if k >= N:continue
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1
    print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    K = int(input())
    for i in range(1,10**8):
        r = True
        s = str(i)
        if len(s) != 1:
            for j in range(len(s)-1):
                if abs(int(s[j])-int(s[j+1])) > 1:
                    r = False
                    break
        if r:
            K -= 1
            if K == 0:
                print(i)
                break
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def f(v,i,ans):
    if i == 0:return
    if str(v)[-1] != "0":
        x = int(str(v)+str(int(str(v)[-1])-1))
        ans.add(x)
        f(x,i-1,ans)
    y = int(str(v)+str(v)[-1])
    ans.add(y)
    f(y,i-1,ans)
    if str(v)[-1] != "9":
        z = int(str(v)+str(int(str(v)[-1])+1))
        ans.add(z)
        f(z,i-1,ans)
def main():
    K = int(input())
    ans = set()
    for i in range(1,10):
        ans.add(i)
        f(i,10,ans)
    ans = list(ans)
    ans.sort()
    print(ans[K-1])
if __name__ == "__main__":
    main()