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:
import sys
sys.setrecursionlimit(10**9)

n=int(input())
l=[]
for i in range(1,10):
    if 6**i>n:
        break
    l.append(6**i)
for i in range(1,10):
    if 9**i>n:
        break
    l.append(9**i)

l.sort()

if n in l:
    print(1)
    exit()

inf=float("inf")
dp=[inf]*(n+1)

def dfs(n):
    if dp[n]!=inf:
        return dp[n]
    if n<6:
        return n
    m=inf
    for d in l:
        if n-d<0:
            break
        m=min(m,dfs(n-d)+1)
    dp[n]=m
    return m

print(dfs(n))
print(dp)

Submission status: Wrong Answer

Solution code:
n=int(input())

ans=n

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

    t=n-i
    while t>0:
        c+=t%6
        t//=6
    if ans>c:
        ans=c
print(ans)

Submission status: Wrong Answer

Solution code:
import math

import numpy as np


def get_choices(n, p):
    choices = set()
    for i in range(1, n):
        powered = int(math.pow(p, i))
        if powered <= n:
            choices.add(powered)
        else:
            break
    return choices


def main(n):
    choices = {1}
    choices |= get_choices(n, 6)
    choices |= get_choices(n, 9)

    dp = np.full(shape=n + 1, fill_value=n, dtype=int)
    dp[1] = 1

    for i in range(1, n + 1):
        for choice in choices:
            if i - choice > 0:
                if dp[i] > dp[i - choice] + 1:
                    dp[i] = dp[i - choice] + 1
            else:
                break

    return dp[-1]


if __name__ == '__main__':
    N = int(input())
    print(main(N))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
Nu = len(unit)

ans = N
state_pool = [(0, 0, 0, Nu-1)]
while state_pool:
    n, i, parent, pk = state_pool.pop()
    if N - n >= (ans-i)*unit[pk]:
        continue
    elif pk > 0:
        state_pool.append((parent+unit[pk-1], i, parent, pk-1))

    k = bisect_right(unit, N-n, 0, pk+1) - 1
    c = n + unit[k]
    if c == N:
        if i + 1 < ans:
            ans = i + 1
    else:
        state_pool.append((c, i+1, n, k))
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

def saiki(tgt,i,count,ans):
    #print(tgt,i,count)
    num=tgt//temp[i]
    if i==0 or tgt==0:
        ans=min((tgt+count),ans)
        return ans
    elif ans<count:
        return ans
        
    while num>=0:
        count+=num
        ans=saiki(tgt-num*temp[i],i-1,count,ans)
        num-=1
    return ans

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()

print(saiki(N,len(temp)-1,0,10**9))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

def saiki(tgt,i,count,ans):
    num=0
    if i==0:
        ans=min((tgt+count),ans)
        return ans
    elif ans<count:
        return ans
        
    while tgt-num*temp[i]>=0:
        count+=num
        ans=saiki(tgt-num*temp[i],i-1,count,ans)
        num+=1
    return ans

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()


print(saiki(N,len(temp)-1,0,10**9))
    
#ほぞん

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
six_ls = []
nine_ls = []
def nine_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 9:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            break
    return base

def six_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 6:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            break
    return base

six_sinsu = [0 for i in range(math.floor(math.log(n, 6)) + 1)]
nine_sinsu = [0 for i in range(math.floor(math.log(n, 9)) + 1)]

for i in range(n+1):
    six_ls.append(sum(six_sinsu))
    nine_ls.append(sum(nine_sinsu))
    six_sinsu = six_plus(six_sinsu)
    nine_sinsu = nine_plus(nine_sinsu)
hoge = [a + b for a, b in zip(six_ls, nine_ls[::-1])]
print(min(hoge))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

ans=[]

def saiki(tgt,i,count):
    print(i)
    num=0
    if i==0:
        ans.append(tgt+count)
        print("終わり")
        return
    while tgt-num*temp[i]:
        count+=num
        saiki(tgt-num*temp[i],i-1,count)
        num+=1
    return

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()

saiki(N,len(temp)-1,0)

print(ans)
    
#ほぞん

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
six_ls = []
nine_ls = []
def nine_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base)-1, -1, -1):
        if base[num] + kuriagari >= 9:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            kuriagari = 0
    return base

def six_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 6:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            kuriagari = 0
    return base

six_sinsu = [0 for i in range(math.floor(math.log(n, 6)) + 1)]
nine_sinsu = [0 for i in range(math.floor(math.log(n, 9)) + 1)]

for i in range(n+1):
    six_ls.append(sum(six_sinsu))
    nine_ls.append(sum(nine_sinsu))
    six_sinsu = six_plus(six_sinsu)
    nine_sinsu = nine_plus(nine_sinsu)
print(min([a + b for a, b in zip(six_ls, nine_ls[::-1])]))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
six_ls = []
nine_ls = []
def nine_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base)-1, -1, -1):
        if base[num] + kuriagari >= 9:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            kuriagari = 0
    return base

def six_plus(base):
    "base : list of int"
    kuriagari = 1
    for num in range(len(base) - 1, -1, -1):
        if base[num] + kuriagari >= 6:
            base[num] = 0
            continue
        else:
            base[num] += kuriagari
            kuriagari = 0
    return base

six_sinsu = [0 for i in range(math.ceil(math.log(n, 6)))]
nine_sinsu = [0 for i in range(math.ceil(math.log(n, 9)))]

for i in range(n+1):
    six_ls.append(sum(six_sinsu))
    nine_ls.append(sum(nine_sinsu))
    six_sinsu = six_plus(six_sinsu)
    nine_sinsu = nine_plus(nine_sinsu)
print(min([a + b for a, b in zip(six_ls, nine_ls[::-1])]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [6**i for i in range(6)]
b = [9**i for i in range(1,7)]
c = 0
while n>0:
  a = list(filter(lambda x: n>=x, a))
  b = list(filter(lambda x: n>=x, b))
  if len(a):
    ma = max(a)
  else:
    ma = 0
  if len(b):
    mb = max(b)
  else:
    mb = 0
  n -= max(ma,mb)
  c += 1
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0

while True:
    if n < 9:
        break
    #n = n // 9 + n % 9
    n -= 9
    ans += 1

while True:
    if n < 6:
        break
    #n = n // 6 + n % 6
    n -= 6
    ans += 1

ans += n

print(ans)

Submission status: Wrong Answer

Solution code:
n= int(input())
ninesix = [9**i for i in range(1,6) if 9**i <= n]+[6**i for i in range(1,7) if 6**i <= n]+[1]
ninesix.sort(reverse=True)

def coin(ns,max_res):
  if not ns or max_res < 6:
    return max_res
  remainder = max_res//ns[0]
  if remainder>0 and remainder<9:
    c = 1000000
    for i in range(1,remainder+1):
      nnss = ns[1:]
      c = min(coin(nnss,max_res-ns[0]*i)+i,c)
    return c
  elif remainder == 0:
    nnss = ns[1:]
    return coin(nnss,max_res)
  else:
    return 10000
   
print(coin(ninesix,n))

Submission status: Wrong Answer

Solution code:
n= int(input())
ninesix = [9**i for i in range(1,6) if 9**i <= n]+[6**i for i in range(1,7) if 6**i <= n]
ninesix.sort(reverse=True)

def coin(ns,max_res):
  if not ns:
    return max_res
  remainder = max_res//ns[0]
  if remainder>0 and remainder<ns[0]:
    c = 1000000
    for i in range(1,remainder+1):
      nnss = ns[1:]
      c = min(coin(nnss,max_res-ns[0]*i)+i,c)
    return c
  elif remainder == 0:
    nnss = ns[1:]
    return coin(nnss,max_res)
  else:
    return 10000
   
print(coin(ninesix,n))

Submission status: Wrong Answer

Solution code:
n= int(input())
ninesix = [9**i for i in range(1,6) if 9**i <= n]+[6**i for i in range(1,7) if 6**i <= n]
ninesix.sort(reverse=True)

def coin(ns,max_res):
  if not ns:
    return max_res
  remainder = max_res//ns[0]
  if remainder>0 and remainder<ns[0]:
    c = 1000000
    for i in range(1,remainder+1):
      nnss = ns[1:]
      c = min(coin(nnss,max_res-ns[0]*i)+i,c)
    return c
  elif remainder == 0:
    nnss = ns[1:]
    return coin(nnss,max_res)
  else:
    return 10000
  return count
   
print(coin(ninesix,n))

Submission status: Wrong Answer

Solution code:
n= int(input())
ninesix = [9**i for i in range(1,6) if 9**i <= n]+[6**i for i in range(1,7) if 6**i <= n]
ninesix.sort(reverse=True)

def coin(ns,max_res):
  if not ns:
    return max_res
  remainder = max_res//ns[0]
  if remainder>0 and remainder<ns[0]:
    count = 0
    c = 10000
    for i in range(1,remainder+1):
      nnss = ns[1:]
      c = min(coin(nnss,max_res-ns[0]*i)+i,c)
    count += c
    return count
  elif remainder == 0:
    nnss = ns[1:]
    return coin(nnss,max_res)
  else:
    return 10000
  return count
   
print(coin(ninesix,n))

Submission status: Wrong Answer

Solution code:
n= int(input())
ninesix = [9**i for i in range(1,6) if 9**i <= n]+[6**i for i in range(1,7) if 6**i <= n]
ninesix.sort(reverse=True)

def coin(ns,max_res):
  if not ns:
    return max_res
  remainder = max_res//ns[0]
  if remainder>0 and remainder<ns[0]:
    count = 0
    c = 100
    for i in range(1,remainder+1):
      nnss = ns[1:]
      c = min(coin(nnss,max_res-ns[0]*i)+i,c)
    count += c
    return count
  elif remainder == 0:
    nnss = ns[1:]
    return coin(nnss,max_res)
  else:
    return 100
  return count
   
print(coin(ninesix,n))

Submission status: Wrong Answer

Solution code:
n=int(input())
last = n
count = 0
while  last > 0:
	c_i= 0
	s_i= 0
	for i in range(1,7):
		if last > 9**i:
			c_i=9**i
			for j in range(1,8):
				if last > 6**j:
					s_i=6**j
	if c_i != 0 or s_i != 0:
		last = last-max(c_i,s_i)
		count += 1
	else:
		count += last
		last = 0
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

def f9(x):
    c = 0
    while True:
        if x >= (9 ** (c+1)):
            c += 1
        else:
            break
    return c

def f6(x):
    c = 0
    while True:
        if x >= (6 ** (c+1)):
            c += 1
        else:
            break
    return c

cnt = 0
while True:
    x = f9(N)
    y = f6(N)

    # print(N, x, y, '|', 9 ** x, 6 ** y)

    if x == 0 and y == 0:
        break

    if 9 ** x > 6 ** y:
        N -= 9 ** x
    else:
        N -= 6 ** y
    
    cnt += 1

print(cnt + N)

Submission status: Wrong Answer

Solution code:
s=[1]
n=int(input())
for i in range(1,7):
    s.append(6**i)
for i in range(1,6):
    s.append(9**i)
s.sort(reverse=True)
print(s)
c=0;i=0
while n>0:
    if n<s[i]:
        i+=1
    else:
        n-=s[i]
        c+=1
print(c)
#108とかでwaになる

Submission status: Wrong Answer

Solution code:
def run():
  N = int(input())
  dp = [1] * (N+1)
  for n in range(1, N+1):
    if n == 1: continue
    dp[n] = dp[n-1]+1
    draw_money = 6
    while True:
      if n <= draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 6
    draw_money = 9
    while True:
      if n <= draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 9
  print(dp[N])
  
if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
def run():
  N = int(input())
  dp = [1] * N
  for n in range(N):
    if n == 0: continue
    dp[n] = dp[n-1]+1
    draw_money = 6
    while True:
      if n < draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 6
    draw_money = 9
    while True:
      if n < draw_money: break
      dp[n] = min(dp[n], dp[n-draw_money]+1)
      draw_money *= 9
  print(dp[N-1])
  
if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
n=int(input())
k=[59049,46646,7776,6561,1296,729,216,81,36,9,6]
c=0
while n>=6:
  for i in k:
    if n==14 or n==13 or n==12:
      c+=2
      n=n-12
      break
    if n-i>0:
      n=n-i
      c+=1
      break
c+=n
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=[59049,46646,7776,6561,1296,729,216,81,36,9,6]
c=0
while n>6:
  for i in k:
    if n-i>0:
      n=n-i
      c+=1
c+=n
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=[59049,46646,7776,6561,1296,729,216,81,36,9,6]
c=0
while n>6:
  for i in k:
    if n-i>0:
      n=n-i
      c+1
c+=n
print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
dp = list(range(N+1))

i = 6
while i <= N:
    for j in range(i, N+1):
        dp[j] = min(dp[j], 1+dp[j-i])
    i = i*6
i = 9
while i <= N:
    for j in range(N+1):
        dp[j] = min(dp[j], 1+dp[j-i])
    i = i*9
print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())
six = []
nine = []

for i in range(0, 7):
    if 6 ** i > n:
        break
    else:
        six.append(6 ** i)

for i in range(0, 6):
    if 9 ** i > n:
        break
    else:
        nine.append(9 ** i)

def six_count(count, price):
    tmp = 0
    for k in six:
        if k > price:
            break
        else:
            tmp = k
    count += price // tmp
    return count, price % tmp

def nine_count(count, price):
    tmp = 0
    for l in nine:
        if l > price:
            break
        else:
            tmp = l
    count += price // tmp
    return count, price % tmp

def dfs(output, price):
    if price == 0:
        return output

    count6, price6 = six_count(output, price)
    count9, price9 = nine_count(output, price)
    start_six = dfs(count6, price6)
    start_nine = dfs(count9, price9)

    return min(start_six, start_nine)

print(dfs(0, n))

Submission status: Wrong Answer

Solution code:
n = int(input())
six = []
nine = []

for i in range(0, 7):
    if 6 ** i > n:
        break
    else:
        six.append(6 ** i)

for i in range(0, 6):
    if 9 ** i > n:
        break
    else:
        nine.append(9 ** i)

def six_count(count, price):
    tmp = 0
    for k in six:
        if k > price:
            break
        else:
            tmp = k
    count += price // tmp
    return count, price % tmp

def nine_count(count, price):
    tmp = 0
    for l in nine:
        if l > price:
            break
        else:
            tmp = l
    count += price // tmp
    return count, price % tmp

def dfs(output, price):
    if price == 0:
        return output

    count6, price6 = six_count(output, price)
    count9, price9 = nine_count(output, price)
    start_six = dfs(count6, price6)
    start_nine = dfs(count9, price9)

    return min(start_six, start_nine)

print(dfs(0, n))
print(nine, six)

Submission status: Wrong Answer

Solution code:
N = int(input())
dp=list(range(N+1))

i = 6
while i <= N:
    for j in range(6,N+1):
        dp[j] = min(dp[j],1+dp[j-i])
    i = i*6
i = 9
while i <= N:
    for j in range(9,N+1):
        dp[j] = min(dp[j],1+dp[j-i])
    i = i*9

print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
lis = [9 ** i for i in range(6)]
for i in range(1,7):
    lis.append(6 ** i)
count = 0
lis.sort(reverse=True)
for x in lis:
    while N - x >= 0:
        N -= x 
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = N
    
for i in range(N):
  t = i
  cc = 0
  while t > 0:
    cc += t % 6
    t = t // 6
  t = N - i
  while t > 0:
    cc += t % 9
    t = t // 9
    
  ans = min(cc,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=[0]*n
ans[0]=1
for i in range(n):
    ans[i] = ans[i-1]+1
    m6 = 6
    m9 = 9
    while i>=m6:
        ans[i] = min(ans[i],ans[i-m6]+1)
        m6 *= 6
    while i>=m9:
        ans[i] = min(ans[i],ans[i-m9]+1)
        m9 *= 9
print(ans[-1])

Submission status: Wrong Answer

Solution code:
# テンプレート 
N = int(input())

inf = float('inf')
dp = [inf] * (N+1)
dp[0] = 0

# リストを作って、その回数についてDP適用　この場合は6と9のべき乗を作成

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

for i in range(1, N+1):
    for t in c: #ｃのリストの中だけ繰り返す       
        if i - t >= 0:
            dp[i] = chmin(dp[i], dp[i-t]+1)
        else:
            break
            
print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())
import math
li ,li2= [],[]
a = int(math.log(n)//math.log(9))
b = int(math.log(n)//math.log(6))

for i in range(a+1):
    li.append(9**i)
for j in range(b+1):
    li2.append(6**j)
li.extend(li2)
li.sort(reverse = True)
#print(li)
num = 0
for i in range(len(li)):
    num += n//li[i]
    n = n%li[i]
    #print(n,num,li[i])
    if n == 0:
        break
print(num)

Submission status: Wrong Answer

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(46656)
list.append(59049)
pp=[]
def money(x,y):
  for i in range(12):
    if 0<x//list[i]<6:
      if x%list[i]==0:
        pp.append(y+x//list[i])
        break
      else:
        money(x%list[i],y+x//list[i])
money(a,0)
print(min(pp))

Submission status: Wrong Answer

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(46656)
list.append(59049)
pp=[]
def money(x,y):
  for i in range(12):
    if 0<x//list[i]<6:
      if x%list[i]==0:
        pp.append(y+x//list[i])
        break
      else:
        money(x%list[i],y+1)
money(a,0)
print(min(pp))

Submission status: Wrong Answer

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(46656)
list.append(59049)
pp=[]
def money(x,y):
  for i in range(12):
    if 0<x//list[i]<6:
      if x%list[i]==0:
        pp.append(y+x//list[i])
        break
      else:
        money(x//list[i],y+1)
money(a,0)
print(min(pp))

Submission status: Wrong Answer

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(46656)
list.append(59049)
pp=[]
def money(x,y):
  for i in range(12):
    if 0<=x//list[i]<6:
      if x%list[i]==0:
        pp.append(y+x//list[i])
        break
      else:
        money(x-list[i],y+1)
money(a,0)
print(min(pp))

Submission status: Wrong Answer

Solution code:
s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(46656)
list.append(59049)
pp=[]
def money(x,y):
  for i in range(12):
    if 0<x//list[i]<6:
      if x%list[i]==0:
        pp.append(y+x//list[i])
        break
      else:
        money(x-list[i],y+1)
money(a,0)
print(min(pp))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N = int(input())

dp = [0] * (N+1)
for i in range(N+1):
    dp[i] = i

#print(dp)


for i in range(1, N+1):
    pow6 = 6
    while pow6 < N:
        if i >= pow6:
            dp[i] = min(dp[i], dp[i-pow6]+1)

        pow6 *= 6

    pow9 = 9
    while pow9 < N:
        if i >= pow9:
            dp[i] = min(dp[i], dp[i-pow9]+1)

        pow9 *= 9

print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
for i in range(9):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
for i in range(N):
  n = m = 1
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
for i in range(10):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
  else:
    dp[i] = 1
for i in range(N):
  n = m = 1
  for j in range(i, min(i+6, N)):
    dp[j] = min(dp[j], dp[i] + j - i)
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
for i in range(10):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
  else:
    dp[i] = 1
for i in range(N):
  n = m = 1
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())

counter_min = n

for i in range(n):
  counter = 0
  n_six = i
  n_nine = n-i

  # 6
  j = 1
  while True:
    if  n_six >= 6**j:
      j += 1
    else:
      div_n = 6**(j-1)
      break
  
  while n_six > 0:
    counter += n_six // div_n
    n_six %= div_n
    div_n //= 6 
    
  # 9
  j = 1
  while True:
    if  n_nine >= 9**j:
      j += 1
    else:
      div_n = 9**(j-1)
      break
        
  while n_nine > 0:
    counter += n_nine // div_n
    n_nine %= div_n
    div_n //= 9
  
  counter_min = min(counter, counter_min)

print(counter_min)

Submission status: Wrong Answer

Solution code:
n = int(input())

counter_min = n

for i in range(n):
  counter = 0
  n_six = i
  n_nine = n-i

  # 6
  j = 1
  while True:
    if  n_six > 6**j:
      j += 1
    else:
      div_n = 6**(j-1)
      break
  
  while n_six > 0:
    counter += n_six // div_n
    n_six %= div_n
    div_n //= 6 
    
  # 9
  j = 1
  while True:
    if  n_nine > 9**j:
      j += 1
    else:
      div_n = 9**(j-1)
      break
        
  while n_nine > 0:
    counter += n_nine // div_n
    n_nine %= div_n
    div_n //= 9
  
  counter_min = min(counter, counter_min)

print(counter_min)

Submission status: Wrong Answer

Solution code:
# テンプレート
N = int(input())

inf = float('inf')
dp = [inf] * N
dp[0] = 1

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

for i in range(1, N):
    for t in c: 
        if i - t >= 0:
            dp[i] = chmin(dp[i], dp[i-t]+1)
        else:
            break
print(dp[N-1])

Submission status: Wrong Answer

Solution code:
cnt = 0
n = int(input())
res = n - n%9
cnt += int(res/9)
res = res - res%6
cnt += int(res/6)
cnt += res
print(cnt)

Submission status: Wrong Answer

Solution code:
# DP(配るDP)
INF = float('inf')

N = int(input())

c = [1]
t = 6
while t <= N:
    c.append(t)
    t *= 6
t = 9
while t <= N:
    c.append(t)
    t *= 9

dp = [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    t0 = dp[i] + 1
    for j in c:
        t1 = i + j
        if t1 <= N and dp[t1] > t0:
            dp[t1] = t0
    if dp[N] != INF:
        break
print(dp[N])

Submission status: Wrong Answer

Solution code:
n = int(input())

INF = 100010
dp = [INF] * n
dp[0] = 1
for i in range(n):
    if i + 1 < n: dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    
    j = 6
    while i + j < n:
        dp[i + j] = min(dp[i + j], dp[i] + 1)
        j *= 6
    
    j = 9
    while i + j < n:
        dp[i + j] = min(dp[i + j], dp[i] + 1)
        j *= 9

print(dp[n - 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import itertools

N = int(input().split()[0])

# 6を使うパターンを列挙
i = 0
p_6_list = []
while 6 ** i <= N:
    p_6_list.append(6 ** i)
    i += 1

p_6_gen = list(itertools.product(range(0, 6), repeat=len(p_6_list)))
min_count = float("inf")

for p_6 in p_6_gen:
    x = sum([x * i for x, i in zip(p_6_list, list(p_6))])
    c = sum(list(p_6))

    if c >= min_count:
        # この時点ですでに最小記録更新できないとわかるので、
        # あとの計算は実施しない
        continue

    balance = N - x
    if balance < 0:
        continue

    while balance > 0:
        # 9の何乗が必要か
        j = math.floor(math.log(balance, 9))
        c += 1
        balance -= 9 ** j

    min_count = min(min_count, c)

ans = min_count
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import itertools

N = int(input().split()[0])

# 6を使うパターンを列挙
i = 0
p_6_list = []
while 6 ** i <= N:
    p_6_list.append(6 ** i)
    i += 1

p_6_gen = list(itertools.product(range(0, 6), repeat=len(p_6_list)))
min_count = float("inf")

for p_6 in p_6_gen:
    x = sum([x * i for x, i in zip(p_6_list, list(p_6))])
    c = sum(list(p_6))

    if c >= min_count:
        # この時点ですでに最小記録更新できないとわかるので、
        # あとの計算は実施しない
        continue

    balance = N - x
    if balance < 0:
        continue
    while balance > 0:
        # 9の何乗が必要か
        j = math.floor(math.log(balance, 9))
        c += 1
        balance -= 9 ** j

    min_count = min(min_count, c)

ans = min_count
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import itertools

N = int(input().split()[0])

# 6を使うパターンを列挙
i = 0
p_6_list = []
while 6 ** i <= N:
    p_6_list.append(6 ** i)
    i += 1

# 9を使うパターンを列挙
i = 0
p_9_list = []
while 9 ** i <= N:
    p_9_list.append(9 ** i)
    i += 1

p_6_gen = list(itertools.product(range(0, 6), repeat=len(p_6_list)))
p_9_gen = list(itertools.product(range(1, 9), repeat=len(p_9_list)))
min_count = float("inf")

for p_6 in p_6_gen:
    x = sum([x * i for x, i in zip(p_6_list, list(p_6))])
    c = sum(list(p_6))

    if c >= min_count:
        # この時点ですでに最小記録更新できないとわかるので、
        # あとの計算は実施しない
        continue

    balance = N - x
    if balance < 0:
        continue
    while balance > 0:
        # 9の何乗が必要か
        j = math.floor(math.log(balance, 9))
        c += 1
        balance -= 9 ** j

    min_count = min(min_count, c)

ans = min_count
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import itertools

N = int(input().split()[0])

# 6を使うパターンを列挙
i = 0
p_6_list = []
while 6 ** i <= N:
    p_6_list.append(6 ** i)
    i += 1

# 9を使うパターンを列挙
i = 0
p_9_list = []
while 9 ** i <= N:
    p_9_list.append(9 ** i)
    i += 1

p_6_gen = list(itertools.product(range(0, 6), repeat=len(p_6_list)))
p_9_gen = list(itertools.product(range(1, 9), repeat=len(p_9_list)))
min_count = float("inf")

for p_6 in p_6_gen:
    x = sum([x * i for x, i in zip(p_6_list, list(p_6))])
    c = sum(list(p_6))

    if c >= min_count:
        # この時点ですでに最小記録更新できないとわかるので、
        # あとの計算は実施しない
        continue

    balance = N - x
    for p_9 in p_9_gen:
        y = sum([x * i for x, i in zip(p_9_list, list(p_9))])

        if x + y > N:
            # 金額が一致しないので
            # あとの計算は実施しない
            continue

        c += sum(list(p_9))
        # 差分を1円で賄う
        c += N - (x + y)

        min_count = min(min_count, c)

ans = min_count
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [10**6 for i in range(n)]
dp[0] = 1
# print(1,dp[0])
for i in range(1,n):
    dps = [dp[i-1]+1]
    for c in [6,9]:
        j = 0
        while True:
            j += 1
            if c**j > i:
                break
            else:
                dps += [dp[i-c**j]+1]
    # print('DPs are',dps)
    dp[i] = min(dps)
    # print(i+1,'DP is',dp[i])
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
c = [1]
for i in [6,9]:
    j = 0
    k = 0
    while True:
        j += 1
        k = i**j
        if k > 10**5:
            break
        c += [k]
# print(c)
c.sort(reverse=True)
flag = 0
for i in range(len(c)):
    m = int(n//c[i])
    n %= c[i]
    flag += m
    # print('withdraw',c[i],m,'times and sum is',flag)
print(flag)

Submission status: Wrong Answer

Solution code:
n = int(input())
c = [1]
for i in [6,9]:
    j = 0
    k = 0
    while True:
        j += 1
        k = i**j
        if k > 10**5:
            break
        c += [k]
print(c)
c.sort(reverse=True)
flag = 0
for i in range(len(c)):
    m = int(n//c[i])
    n %= c[i]
    flag += m
    # print('withdraw',c[i],m,'times and sum is',flag)
print(flag)

Submission status: Wrong Answer

Solution code:
lists=[]
emptylists=[]
numbers=int(input())

for nums in range(numbers+3):
    
    if nums<6:
        lists.append(int(nums))
         
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7726 or nums==46656:
        lists.append(1)
        
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        
    else:
        power6=0
        power9=0
        for k in range(7):
            if 6**(k)< nums <6**(k+1):
                power6=k
                break   
                
        for j in range(6):
            if 9**(j) <nums< 9**(j+1):
                power9=j
                break
        add=min(min(lists[nums-6**(k)]+1 for k in range(0,power6+1)),min(lists[nums-9**(j)]+1 for j in range(0,power9+1)))
        lists.append(add)
print(lists[numbers])

Submission status: Wrong Answer

Solution code:
n = int(input())
payable = [1] + [6**(int(x)+1) for x in range(7)] + [9**(int(x)+1) for x in range(6)]
payable.sort()
ans = 0
while n > 0:
    for i in range(1,len(payable)+1):
        if payable[-1] > n:
            payable.pop()
        else:
            break
    n -= max(payable)
    ans += 1
print(ans)