Problem:


Score : 300 points

Problem Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

1 yen (the currency of Japan)

6 yen, 6^2(=36) yen, 6^3(=216) yen, ...

9 yen, 9^2(=81) yen, 9^3(=729) yen, ...

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

1 \leq N \leq 100000

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Sample Input 1

127

Sample Output 1

4

By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.

Sample Input 2

3

Sample Output 2

3

By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.

Sample Input 3

44852

Sample Output 3

16



Sample input:
127


Sample output:
4

Submission status: Wrong Answer

Solution code:
from math import log
from itertools import product

n = int(input())

pow6 = [pow(6, i + 1) for i in range(int(log(n, 6)))]
ans = n
for l in product(range(0, 6), repeat=int(log(n, 6))):
    cnt = sum(l)
    num = n - sum(li * pow6[i] for i, li in enumerate(l))
    if num >= 0:
        while num > 0:
            num -= pow(9, int(log(num, 9)))
            cnt += 1
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log
from itertools import product

n = int(input())

pow6 = [pow(6, i + 1) for i in range(int(log(n, 6)))]
ans = n
for l in product(range(0, 6), repeat=int(log(n, 6))):
    cnt = sum(l)
    num = n - sum(li * pow6[i] for i, li in enumerate(l))
    if num > 0:
        while num > 0:
            num -= pow(9, int(log(num, 9)))
            cnt += 1
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    dp=[float("inf")]*(n+1)
    dp[0]=0
    for i in range(n):
        dp[i+1] = min(dp[i+1], dp[i]+1)
        j,k = 6,9
        while i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
            j *= 6
        while i+k < n:
            dp[i+k] = min(dp[i+k], dp[i]+1)
            k *= 9
    print(dp[-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

# dp[i] i円引き出すのに必要な手数
dp = [101010] * 201010
money = [1]
t = 6
q = 9
while t < N:
    money.append(t)
    t*=6
while q < N:
    money.append(q)
    q*=9

for m in money:
    dp[m] = 1

for i in range(1,N):
    for m in money:
        dp[i+m] = min(dp[i+m], dp[i]+1)

print(dp[N])

Submission status: Wrong Answer

Solution code:
from math import log

N=int(input())

dp = [0]*(N+1)

for i in range(1,N+1):
  e6 = log(i)//log(6)
  e9 = log(i)//log(9)
  dp[i] = min(dp[i-1],dp[i-int(6**e6)],dp[i-int(9**e9)])+1
  
print(dp[-1])

Submission status: Wrong Answer

Solution code:
a = int(input())

res = a
temp=0
while res >0:
    b=1
    c=1
    while b*6 <=res:
        b = b*6
    while c*9 <= res:
        c = c*9
    if c>b and res >= c*4/3 and res <b+c:
        res -= b
        temp +=1
    else:
        res -= max(b,c)
        temp +=1
    
print(temp)

Submission status: Wrong Answer

Solution code:
a = int(input())

res = a
temp=0
while res >0:
    b=1
    c=1
    while b*6 <=res:
        b = b*6
    while c*9 <= res:
        c = c*9
    if res>=12 and res <=14:
        temp += res-10
        print(temp)
        exit()
    res -= max(b,c)
    temp +=1
    
print(temp)

Submission status: Wrong Answer

Solution code:
N = int(input())
Dp = [a for a in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1,7):
        if i > (6 ** j):
            Dp[i] = min(Dp[i], Dp[i-6**j] + 1)
    for h in range(1,6):
        if i > (9 ** h):
            Dp[i] = min(Dp[i], Dp[i-9**h] + 1)
print(Dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
kouho = [1]
for i in range(1, 100):
    t = 6 ** i
    if t <= 10 ** 5:
        kouho.append(t)
    else:
        break
for i in range(1, 100):
    t = 9 ** i
    if t <= 10 ** 5:
        kouho.append(t)
    else:
        break
#print(kouho)

kouho.sort(reverse=True)

ans = 0
cur = 0
while N > 0:
    if N >= kouho[cur]:
        N -= kouho[cur]
        ans += 1
    else:
        cur += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
six = [6**i for i in range(7)]
nine = [9**i for i in range(6)]
L = []
for s in six:
  L.append(s)
for s in nine[1:]:
  L.append(s)
L.sort(reverse=True)
ans = 0
for l in L:
  ans += N // l
  N %= l
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
money=[1]
dp=[0]*(n+1)
dp[1]=1
m=6
i=1
while m<n:
  money.append(m)
  i+=1
  m=6**i
m=9
i=1
while m<n:
  money.append(m)
  i+=1
  m=9**i

for m in money:
  dp[m]=1
for i in range(1,n+1):
  for m in money:
    if i+m>=n+1:
      continue
    if dp[i]+1<=dp[i+m] or dp[i+m]==0:
      dp[i+m]=dp[i]+1
print(dp[n])

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = [inf]*100001

a[0] = 0
for i in range(1,100001):
    a[i] = a[i-1]+1
    j = 1
    while i - 6**j > 0:
        a[i] = min(a[i], a[i-6**j]+1)
        j += 1
    j = 1
    while i - 9**j > 0:
        a[i] = min(a[i], a[i-9**j]+1)
        j += 1

print(a[n])

Submission status: Wrong Answer

Solution code:
x = int(input())
count=0
if x >= 9**5:
    x -= 9**5
    count +=1
for i in range(6,1,-1):
    if x >= 9**i:
        while x >=9**i:
            x -= 9**i
            count +=1
    if x >= 6**i:
        while x >=6**i:
            x -= 6**i
            count +=1          
a = x
p = x
for i in range(x):
    for j in range(x):
        for l in range(x):
            if 9*i+6*j+1*l==x:
                b=i+j+l
                p= min(p,b)
print(count+p)

Submission status: Wrong Answer

Solution code:
x = int(input())
count=0
if x >= 9**5:
    x -= 9**5
    count +=1
for i in range(6,1,-1):
    if x >= 9**i:
        while x >=9**i:
            x -= 9**i
            count +=1
    if x >= 6**i:
        while x >=6**i:
            x -= 6**i
            count +=1          
a = x
p = x
for i in range(x):
    for j in range(x):
        for l in range(x):
            if 9*i+6*j+1*l==23:
                b=i+j+l
                p= min(p,b)
print(count+p)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [None] * (n+1)
dp[1] = 1
dp[0] = 0
sixs = [6]
nines = [9]
i = 1
while sixs[i-1] * 6 <= n:
    sixs.append(sixs[i-1]*6)
    i += 1

i = 1
while nines[i-1] * 6 <= n:
    nines.append(nines[i-1]*9)
    i += 1
for current in range(2, n+1):
    smin = n
    for six in sixs:
        if current - six >= 0 and dp[current-six] != None:
            smin = min(smin, dp[current-six] + 1)
    nmin = n
    #print (smin, nmin)
    for nine in nines:
        if current - nine > 0 and dp[current-nine] != None:
            nmin = min(nmin, dp[current-nine] + 1)
    #print (dp)
    dp[current] = min(dp[current-1] + 1, nmin, smin)
print (dp[n])
#print (dp)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [None] * (n+1)
dp[1] = 1
dp[0] = 0
sixs = [6]
nines = [9]
i = 1
while sixs[i-1] * 6 <= n:
    sixs.append(sixs[i-1]*6)
    i += 1

i = 1
while nines[i-1] * 6 <= n:
    nines.append(nines[i-1]*9)
    i += 1
for current in range(2, n+1):
    smin = n
    for s in sixs:
        if current - s > 0 and dp[current-s] != None:
            smin = min(smin, dp[current-s] + 1)
    nmin = n
    #print (smin, nmin)
    for nine in nines:
        if current - nine > 0 and dp[current-nine] != None:
            nmin = min(nmin, dp[current-nine] + 1)
    #print (dp)
    dp[current] = min(dp[current-1] + 1, nmin, smin)
print (dp[n])
#print (dp)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())

coins = [(9 ** i) for i in range(1, 7)] + [(6 ** i) for i in range(1, 8)] + [1]
print(coins)
dp = [INF] * (N + 1)
dp[0] = 0
for i in range(len(coins)):
    for j in range(N + 1):
        if j + coins[i] > N:
            continue
        dp[j + coins[i]] = min(dp[j + coins[i]], dp[j] + 1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ans = float("inf")
def sub(x, base):
    if x==0:
        return 0
    i = 0
    while pow(base, i+1)<=x:
        i += 1
    return sub(x-pow(base,i), base) + 1
for i in range(n):
    ans = min(ans, sub(i,6)+sub(n-i,9))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
c=[]
d=[]
f=[]
l=[]
for i in range(1,100):
  m = n - 9**i
  c.append(9**(i-1))
  if m < 0:
    break

for j in range(1,100):
  o = n - 6**j
  d.append(6**(j-1))
  if o < 0:
    break

e=c+d
e.sort()
e.remove(1)
e.remove(1)
e.reverse()

for i in range(len(e)):
  w = n // e[i]
  n -= w*e[i]
  if n > 0:
    f.append(w)
    if n < 6:
      l.append(w)
  else:
    break
ans_1 = sum(f)+3
ans_2 = sum(f)+n
print(min(ans_1,ans_2))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [1]+[pow(6,i) for i in range(1,7)]+[pow(9,i) for i in range(1,6)]
D = [1]+[-1]*(n-1)
for i in range(1,n):
    D[i] = D[i-1]+1
    for j in range(1,7):
        if pow(6,j)>i: break
        D[i] = min(D[i], D[i-pow(6,j)]+1)
    for j in range(1,6):
        if pow(9,j)>i: break
        D[i] = min(D[i], D[i-pow(9,j)]+1)
print(D[-1])

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
ans = float('inf')
for x in product([0,1], repeat=6):
  for y in product([0,1], repeat=7):
    num = 0
    cur = 0
    for i, j in enumerate(x):
      if j == 1:
        num += pow(9, i+1)
        cur += 1
        if num > n:
          continue
    for i, j in enumerate(y):
      if j == 1:
        num += pow(6, i+1)
        cur += 1
        if num > n:
          continue
    if num > n:
      continue
    cur += n - num
    ans = min(ans, cur)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []

# 1
a.append(1)

# 6**n
b = 6
while b <= N:
    a.append(b)
    b *= 6

# 9**n
b = 9
while b <= N:
    a.append(b)
    b *= 9

a.sort(reverse=True)
# print(a)

dp=[N]*(N+1)
dp[0]=0
for i in range(N):
    for v in a:
        if i+v > N:
            break
        dp[i+v] = min(dp[i]+1, dp[i+v])
print(dp[N])

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    
    readline = sys.stdin.readline

    def func(n: int, a: int):
        res = 0
        while n > 0:
            res += n % a
            n = int(n / a)
        return res

    N = int(readline())

    res = N
    for i in range(N):
        tmp = func(i, 6) + func(N - i, 9)
        res = min(res, tmp)
    print(res)

resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
dp=list(range(n+1))
dp[0]=0
a=[]
b=[]
i=1
while True:
  if 6**i>n:break
  a.append(6**i)
  i+=1
i=1
while True:
  if 9**i>n:break
  b.append(9**i)
  i+=1
for i in a:
  for j in range(i+1,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
for i in b:
  for j in range(i+1,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
N = int(input())

yendama = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]

def calc_dp(n):
    initial = 10**7
    dp=[initial for _ in range(100100)]#dp用の配列はすこし大きめに作る
    dp[0] = 0

    for i in range(100000):
        count = 0
        while 6**count <= n:
            power_six = 6**count
            count += 1
            if i - power_six >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_six])
                
        count = 1
        while 9**count <= n:
            power_nine = 9**count
            count += 1
            if i - power_nine >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_nine])

    return dp[N]

print(calc_dp(N))

Submission status: Wrong Answer

Solution code:
N = int(input())

yendama = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]

def calc_dp(n):
    initial = 10**7
    dp=[initial for _ in range(100100)]#dp用の配列はすこし大きめに作る
    dp[0] = 0

    for i in range(100000):
        count = 0
        while 6**count < n:
            power_six = 6**count
            count += 1
            if i - power_six >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_six])
                
        count = 1
        while 9**count < n:
            power_nine = 9**count
            count += 1
            if i - power_nine >= 0:
                dp[i] = min(dp[i],1 + dp[i-power_nine])

    return dp[N]

print(calc_dp(N))

Submission status: Wrong Answer

Solution code:
N = int(input())

yendama = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]

def calc_dp(n):
    initial = 10**7
    dp=[initial for _ in range(100100)]#dp用の配列はすこし大きめに作る
    dp[0] = 0

    for i in range(100000):
        for y in range(len(yendama)):
            if i-yendama[y]>=0:
                dp[i] = min(dp[i],1 + dp[i-yendama[y]])
    return dp[N]

print(calc_dp(N))

Submission status: Wrong Answer

Solution code:
N = int(input())

yendama = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]

def calc_dp(n):
    initial = 10**7
    dp=[initial for _ in range(100010)]#dp用の配列はすこし大きめに作る
    dp[0] = 0

    for i in range(100000):
        for y in range(len(yendama)):
            if i-yendama[y]>=0:
                dp[i] = min(dp[i],1 + dp[i-yendama[y]])
    return dp[N]

print(calc_dp(N))

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = float('inf')
for i in range(1,N+1):
    j = i
    count = 0
    t=N-i
    while j > 0:
        count += j%6
        j=j//6
    while t > 0:
        count += t%9
        t=t//9
    ans = min(ans,count)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
# n < 100000
res = n

for i in range(n):
    c = 0
    t = i
    while t > 0:
        c += t % 6
        t //= 6
    t = n - i
    while t > 0:
        c += t % 9
        t //= 9
    if res > c:
        res = c

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
# n < 100000

# 9**3 = 729
# 9**4 = 6561
# 9**5 = 59049

# 6**4 = 1296
# 6**5 = 7776
# 6**6 = 46656

i = 6
j = 5
ans = 0
while n != 0:
    if n < 6:
        ans += n
        n -= n
        break
    if i > 0 or j > 0:
        if 6**i > 9**j:
            if 6**i < n:
                ans += 1
                n = n - 6**i
            elif 9**j < n:
                ans += 1
                n = n - 9**j
            else:
                if i > 0:
                    i -= 1
                if j > 0:
                    j -= 1
        elif 6**i < 9**j:
            if 9**j < n:
                ans += 1
                n = n - 9**j
            elif 6**i < n:
                ans += 1
                n = n - 6**i
            else:
                if i > 0:
                    i -= 1
                if j > 0:
                    j -= 1
        else:
            if i > 0:
                i -= 1
            if j > 0:
                j -= 1
    else:
        if i > 0:
            i -= 1
        if j > 0:
            j -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())

six = []
nine = []

now = 6
while now < 100001:
  six.append(now)
  now *= 6
  
now = 9
while now < 100001:
  nine.append(now)
  now *= 9  

#print(six, nine)  
#[6, 36, 216, 1296, 7776, 46656] [9, 81, 729, 6561, 59049]

def coin(n):
  if n < 6:
    return n
  else:
    index_six = bisect.bisect_right(six, n)
    index_nine = bisect.bisect_right(nine, n)
    #print(n, index_six, index_nine, count)
    #print(n, n - six[index_six - 1], n - nine[index_nine - 1])
    if n - six[index_six - 1] > 0:
      alpha = coin(n - six[index_six - 1]) + 1
    else:
      alpha = 10 ** 7
    if n - nine[index_nine - 1] > 0:
      beta = coin(n - nine[index_nine - 1]) + 1
    else:
      beta = 10 ** 7
    return min(alpha, beta)
  
print(coin(N))

Submission status: Wrong Answer

Solution code:
N = int(input())

coin = [1, 6, 9, 6**2, 9**2, 6**3, 9**3, 6**4, 9**4, 6**5]
#try DP with
count = [N]*(N+1)

count[0] = 0
for c in range(len(coin)):
    for i in range(N-coin[c] + 1):
        if count[i + coin[c]] > count[i] + 1:
            count[i + coin[c]] = count[i] + 1

print(count[N])

Submission status: Wrong Answer

Solution code:
import sys
INFTY=sys.maxsize

def readinput():
    n=int(input())
    return n

def main(n):
    dp=[INFTY]*(n+1)
    dp[0]=0
    dp[1]=1
    for i in range(2,n+1):
        dp[i]=min(dp[i],dp[i-1]+1)  # 1円
        k=1
        while(i-6**k>0):
            dp[i]=min(dp[i],dp[i-6**k]+1)
            k+=1
        k=1
        while(i-9**k>0):
            dp[i]=min(dp[i],dp[i-9**k]+1)
            k+=1
    return dp[n]

if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def to_n(X, n):
    if (int(X / n)):  return to_n(int(X / n), n) + str(X % n)
    return str(X % n)

ans = 10 ** 9 + 7
for i in range(N):
    N6 = to_n(N - i, 6)
    N9 = to_n(i, 9)
    res = 0
    for j in N6:  res += int(j)
    for j in N9:  res += int(j)
    ans = min(res, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def Base(X, n):
    if (int(X/n)):
        return Base(int(X/n), n)+str(X%n)
    return str(X%n)

def main():
    N = ii()
    m = 10**100
    for i in range((N+1)//2):
        a = sum(map(int, Base(i, 6)))
        b = sum(map(int, Base(N-i, 9)))
        m = min(m, a+b)
    print(m)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    if dp[i] == float("Inf"):
        pass
    else:
        for j in range(1,n//6):
            if i + 6**j > n:
                break
            dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        for j in range(1,n//9):
            if i + 9**j > n:
                break
            dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
ans = n
for i in range(max(0, n-5), n+1):
    ans = min(ans, dp[i]+n-i)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    if dp[i] == float("Inf"):
        pass
    else:
        for j in range(1,n//6):
            if i + 6**j > n:
                break
            dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        for j in range(1,n//9):
            if i + 9**j > n:
                break
            dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
ans = n
for i in range(max(0, n-5), n+1):
    ans = min(ans, dp[i]+n-i)
print(ans)
print(dp)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
dp= [0] * (N+1)

dp[0] = 0

for i in range(1,N+1):
    A = dp[i-1] + 1
    
    k = int(math.log(i, 6))
    B = dp[i - 6 ** k] + 1
    
    k = int(math.log(i, 9))
    C = dp[i - 9 ** k] + 1

    dp[i] = min(A,B,C)

print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())
ans=n
for i in range(n+1):
  cnt=0
  t=i
  while t>0:
    cnt+=t%6
    t//=6
  s=n-i
  while s>0:
    cnt+=s%9
    s//=9
  min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
N = int(input())
P = defaultdict(int)
def rev(A):
    if A == 0:
        return 0
    elif A in P:
        return P[A]
    else:
        a = int(math.log(A, 9))
        b = int(math.log(A, 6))
        if A > 9:
            k = min([rev(A - 9 ** a) + 1, rev(A - 6 ** b) + 1])
            P[A] = k
            return k
        elif a >= 0 and b >= 0:
            k = min([rev(A - 9 ** a) + 1, rev(A - 6 ** b) + 1, rev(A - 1) + 1])
            P[A] = k
            return k
        elif a >= 0:
            k = min([rev(A - 9 ** a) + 1, rev(A - 1) + 1])
            P[A] = k
            return k
        elif b >= 0:
            k = min([rev(A - 6 ** b) + 1, rev(A - 1) + 1])
            P[A] = k
            return k
        else:
            k = rev(A - 1) + 1
            P[A] = k
            return k

print(rev(N))

Submission status: Wrong Answer

Solution code:
N = int(input())
num_lis =[1,6,6**2,6**3,6**4,6**5,6**6,6**7,9,9**2,9**3,9**4,9**5,9**6]
num_lis = sorted(num_lis,reverse = True)
counter = 0
for _ in range(100000):
    for i in range(len(num_lis)):
        if 12<=N<=14:
            N = N-6
            counter += 1
        
        elif N-num_lis[i] >=0:
            N = N-num_lis[i]
            counter += 1
            #print('num_lis='+str(num_lis[i]))
            #print('N='+str(N))
            break
    if N == 0:
        break
print(counter)

Submission status: Wrong Answer

Solution code:
a = int(input())
lst_l = [6, 9]
counter = 0
while a!=0:
  lst = [0, 0]
  for j in range(2):
    for i in range(0, 20):
      if a < lst_l[j]**i:
        break
      lst[j] = lst_l[j]**i
  a -= max(lst)
  counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=n
for n1 in range(n+1):
  n2=n-n1
  cnt1=0
  while n1>0:
    cnt1+=n1%6
    n1=n1//6
  cnt2=0
  while n2>0:
    cnt2+=n2%9
    n2=n2//9
  ans=min(ans,n1+n2)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

count = 0
while n >= 36:
    i = 0
    while 9**(i+1) <= n:
        i += 1

    j = 0
    while 6**(j+1) <= n:
        j += 1

    n -= max([9**i, 6**j])
    count += 1

def func(x, c, memo):
    if x == 0:
        memo.append(c)
    else:
        for i in [9, 6, 1]:
            if x >= i:
                func(x-i, c+1, memo)

memo = []
func(n, count, memo)

print(min(memo))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())

def l(k,x):
  if x == 0:
    return(0)
  else:
    return(int(math.floor(math.log(x)/math.log(k))))

ans = 0
p = n
while True:
  if 0<= p <= 5:
    ans += p
    break
  elif 6 <= p <= 8:
    ans += p-6+1
    break
  else:
    q = l(9,p)
    a = p - 9**q
    r = l(6,a)
    if r == 0:
      ans += 1
      p = a
    else:
      ans += 2
      p = a - 6**r
   
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

price = {1}
for i in range(1, 100):
    tmp = 6**i
    if tmp > 10**5:
        break
    price.add(tmp)

for i in range(1, 100):
    tmp = 9**i
    if tmp > 10**5:
        break
    price.add(tmp)

price = list(price)
price.sort(reverse=True)

INF = 1 << 60

dp = [INF] * 2 * 10**5
dp[1] = 1

for i in range(1, n + 1):
    for p in price:
        dp[i + p] = min(dp[i] + 1, dp[i + p])

print(dp[n])

Submission status: Wrong Answer

Solution code:
n = int(input())

price = {1}
for i in range(1, 100):
    tmp = 6**i
    if tmp > 10**5:
        break
    price.add(tmp)

for i in range(1, 100):
    tmp = 9**i
    if tmp > 10**5:
        break
    price.add(tmp)

price = list(price)
price.sort(reverse=True)

INF = 1 << 60

dp = [INF] * 2 * 10**5
dp[1] = 1

for i in range(1, n):
    for p in price:
        dp[i + p] = min(dp[i] + 1, dp[i + p])

print(dp[n])

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
q=deque([[1,1],[6,1],[9,1]])
b=set()
while q:
    a=q.popleft()
    if a[0] in b:
        continue
    b.add(a[0])
    if a[0]==n:
        print(a[1])
        break
    if a[0]>n:
        continue
    q.append([a[0]+1,a[1]+1])
    for i in range(10):
        q.append([a[0]+6**i,a[1]+1])
        q.append([a[0]+9**i,a[1]+1])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[6**i for i in range(10)]+[9**i for i in range(10)]
dp=[10**5]*(10**5+1)
dp[1]=1
for i in range(n):
    for j in a:
        if i+j<10**5+1:
            dp[i+j]=min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())+1
a=[6**i for i in range(7)]+[9**i for i in range(1,6)]
dp=[10**5]*n
dp[1]=1
for i in range(n):
    for j in a:
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
dp = [999999] * 100100
n = int(input())
dp[0] = 0
for i in range(0, 100010):
    dp[i+1] = min(dp[i+1], dp[i] + 1)
    for j in range(1,100):
        c = i + 6**j
        if (i+c) > 100000:
            break
        dp[c] = min(dp[c], dp[i] + 1)

    for j in range(1,100):
        c = i + 9**j
        if (i+c) > 100000:
            break
        dp[c] = min(dp[c], dp[i] + 1)

#print(dp[:100])
print(dp[n])

Submission status: Wrong Answer

Solution code:
n=int(input())
cnt=0
for i in range(6,-1,-1):
  if 9**i<=n<6**(i+1):
    cnt+=n//9**i
    n%=9**i
  if 6**i<=n<9**i:
    cnt+=n//6**i
    n%=6**i
  
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[1,6,36,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
l.sort(reverse=True)
dp=[float("inf")]*1000000
dp[0]=0
for i in range(1,n+1):
    for j in l:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys 
n=int(input())
l=[1,6,36,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
l.sort(reverse=True)
dp=[float("inf")]*(n+1)
dp[0]=0
dp[1]=1
if n==1:
    print(1)
    sys.exit()
for i in range(2,n+1):
    for j in l:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys 
n=int(input())
l=[1,6,36,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
dp=[float("inf")]*(n+1)
dp[0]=0
dp[1]=1
if n==1:
    print(1)
    sys.exit()
for i in range(2,n+1):
    for j in l[::-1]:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

n = int(input())

six = [0] + [6**i for i in range(1,8)]
nine = [0] + [9**i for i in range(1,7)]

dp = [float("inf")] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    j = bisect_left(six, i) - 1
    if j: dp[i] = min(dp[i], dp[i-six[j]] + 1)
    k = bisect_left(nine, i) - 1
    if k: dp[i] = min(dp[i], dp[i-nine[k]] + 1)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

n = int(input())

six = [0] + [6**i for i in range(1,7)]
nine = [0] + [9**i for i in range(1,6)]

dp = [float("inf")] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    j = bisect_left(six, i)
    if j: dp[i] = min(dp[i], dp[i-six[j-1]] + 1)
    k = bisect_left(nine, i)
    if k: dp[i] = min(dp[i], dp[i-nine[k-1]] + 1)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

n = int(input())

six = [0] + [6**i for i in range(7)]
nine = [0] + [9**i for i in range(6)]

dp = [float("inf")] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    j = bisect_left(six, i)
    if j: dp[i] = min(dp[i], dp[i-six[j-1]] + 1)
    k = bisect_left(nine, i)
    if k: dp[i] = min(dp[i], dp[i-nine[k-1]] + 1)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=867:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 1674<=N<=1727:
        N-=1674
        ans+=3
    if 2187<=N<=2240:
        N-=2187
        ans+=3
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=867:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 1674<=N<=1727:
        N-=1674
        ans+=3
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=867:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=869:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=868:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=870:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
while N:
    if 12<=N<=14:
        N-=12
        ans+=2
    if 864<=N<=890:
        N-=864
        ans+=4
    if 1458<=N<=1511:
        N-=1458
        ans+=2
    if 7857<=N<=7937:
        N-=7857
        ans+=2
    if 13122<=N<=14336:
        N-=13122
        ans+=2
    if 93312<=N:
        N-=93312
        ans+=2
    i=0
    while 9**i<=N:
        i+=1
    i-=1
    j=0
    while 6**j<=N:
        j+=1
    j-=1
    N-=max(9**i,6**j)
    ans+=1

print(ans)