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:
n=int(input())
ans=n

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

Submission status: Wrong Answer

Solution code:
l=[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]
l.sort()
n=int(input())
count=0
while n!=0:
  for i in range(1,15):
    if n>=l[-i]:
      n-=l[-i]
      count+=1
      break
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

def calculate(n):

    memo =  [-1 for i in range(N)]

    for index in range(n):
        if index < 6:
            memo[index] = index + 1
        elif index == 5:
            memo[index] = 1
        elif index == 8:
            memo[index] = 1
        else:
            values = []

            pow6 = 6
            while pow6 <= index:
                values.append(1 + memo[index - pow6])
                pow6 = pow6 * 6
            pow9 = 9
            while pow9 <= index:
                values.append(1 + memo[index - pow9])
                pow9 = pow9 * 9

            values.append(1+memo[index-1])
            minValue = min(values)

            memo[index] = minValue

    return memo

result = calculate(N)

print(result[N-1])

Submission status: Wrong Answer

Solution code:
import math,sys
sys.setrecursionlimit(20000000)
N = int(input())
memo = [-1 for i in range(110000)]
def calculate(n):

    if n == 0:
        memo[n] = 0
        return 0

    if memo[n] != -1:
        return memo[n]

    res = n

    pow6Num = math.floor(math.log(n,6))
    pow9Num = math.floor(math.log(n,9))

    for i in range(1,pow6Num+1):
        res = min(res,calculate(n - 6 ** i) + 1)

    for i in range(1,pow9Num+1):
        res = min(res,calculate(n - 9 ** i) + 1)

    memo[n] = int(res)
    return int(res)



result = calculate(N)
print(memo[N])

Submission status: Wrong Answer

Solution code:
import math,sys
sys.setrecursionlimit(20000000)
N = int(input())
memo = [-1 for i in range(100000+1)]
def calculate(n):

    if n == 0:
        memo[n] = 0
        return 0

    if memo[n] != -1:
        return memo[n]

    res = n

    pow6Num = math.floor(math.log(n,6))
    pow9Num = math.floor(math.log(n,9))

    for i in range(1,pow6Num+1):
        res = min(res,calculate(n - 6 ** i) + 1)

    for i in range(1,pow9Num+1):
        res = min(res,calculate(n - 9 ** i) + 1)

    memo[n] = int(res)
    return int(res)



result = calculate(N)
print(memo[N])

Submission status: Wrong Answer

Solution code:
import math,sys
sys.setrecursionlimit(20000000)
N = int(input())
memo = [-1 for i in range(N+1)]
def calculate(n):

    if n == 0:
        memo[n] = 0
        return 0

    if memo[n] != -1:
        return memo[n]

    res = n

    pow6Num = math.floor(math.log(n,6))
    pow9Num = math.floor(math.log(n,9))

    for i in range(1,pow6Num+1):
        res = min(res,calculate(n - 6 ** i) + 1)

    for i in range(1,pow9Num+1):
        res = min(res,calculate(n - 9 ** i) + 1)

    memo[n] = int(res)
    return int(res)



result = calculate(N)
print(memo[N])

Submission status: Wrong Answer

Solution code:
def cash(a,N):
    ans = 0
    for i in reversed(range(len(a))):
        num = N//a[i]
        N -= a[i]*num
        ans += num
    return ans


N = int(input())

cash6 = []
cash9 = []
for i in range(1000):
    tmp = 6**i
    if tmp>N:
        break
    cash6.append(tmp)
for j in range(1000):
    tmp = 9**j
    if tmp>N:
        break
    cash9.append(tmp)

ans = 1e9
for i in range(N):
    ans = min(ans,cash(cash6,i)+cash(cash9,N-i))
print(ans)

Submission status: Wrong Answer

Solution code:
import math

dp = [float('inf') for _ in range(200000)]
withdraw = []

N = int(input())

#引き出し可能な金額の配列にする
withdraw.append(1)

for i in range( math.floor(math.log(N,6)) + 1):
    withdraw.append(6**i)

for i in range( math.floor(math.log(N,9)) + 1):
    withdraw.append(9**i)

withdraw = sorted(list(set(withdraw)))

dp[0] = 0

for i in range(N+1):
    for j in withdraw:
        dp[i+j] = min(dp[i+j],dp[i]+1)
        
print(dp[N])

Submission status: Wrong Answer

Solution code:
N=int(input())
g = []
a = 6
while a <= 100000:
  g.append(a)
  a *= 6
a = 9
while a <= 100000:
  g.append(a)
  a *= 9
g.sort(reverse=True)
ans = 0
for a in g:
  while N > a:
    N -= a
    ans += 1
print(ans+N)

Submission status: Wrong Answer

Solution code:
n=int(input())

n9=9**5
n6=6**6

#n9=9**3
#n6=6**4

k9=5
k6=6
n9=9**k9
smin=n
for i9 in range(n9):
    ii9=i9
    s=0
    m=0
    astr=""
    for ii in range(1,k9+1):
        r9=ii9%9
        ii9=(ii9-r9)//9    
        s=s*9+r9
        m=m+r9
        astr=astr+str(r9)
#    print("i9",i9,"astr",astr,"s",s,"m",m)
    
    nr=n-s
    nr1=nr
#    print("nr",nr,"m",m)
    
    if nr==0:
        snra=m
#        print(nr,m)
    elif nr>0:
        snra=m
        for jj in range(k6,-1,-1):
            nra=nr1//(6**jj)
            nr1=nr1%(6**jj)
            snra=snra+nra
#        print("jj",jj,"nra",nra,"nr1",nr1)
    if smin>snra:
        smin=snra
print(smin)

Submission status: Wrong Answer

Solution code:
n=int(input())

#n=44852
n9=9**5
n6=6**6

#n9=9**3
#n6=6**4

k9=5
k6=6
n9=9**k9
smin=n
for i9 in range(n9):
    ii9=i9
    s=0
    m=0
    astr=""
    for ii in range(1,k9+1):
        r9=ii9%9
        ii9=(ii9-r9)//9    
        s=s*9+r9
        m=m+r9
        astr=astr+str(r9)
#    print("i9",i9,"astr",astr,"s",s,"m",m)
    
    nr=n-s
    nr1=nr
#    print("nr",nr,"m",m)
    
    if nr<=0:
        print(m)
    else:
        snra=m
        for jj in range(k6,-1,-1):
            nra=nr1//(6**jj)
            nr1=nr1%(6**jj)
            snra=snra+nra
#        print("jj",jj,"nra",nra,"nr1",nr1)
        if smin>snra:
            smin=snra
        print(smin)

Submission status: Wrong Answer

Solution code:
n=int(input())

#n=44852
n9=9**5
n6=6**6

#n9=9**3
#n6=6**4

k9=5
k6=6
n9=9**k9
smin=n
for i9 in range(n9):
    ii9=i9
    s=0
    m=0
    astr=""
    for ii in range(1,k9+1):
        r9=ii9%9
        ii9=(ii9-r9)//9    
        s=s*9+r9
        m=m+r9
        astr=astr+str(r9)
#    print("i9",i9,"astr",astr,"s",s,"m",m)
    
    nr=n-s
    nr1=nr
#    print("nr",nr,"m",m)
    
    snra=m
    for jj in range(k6,-1,-1):
        nra=nr1//(6**jj)
        nr1=nr1%(6**jj)
        snra=snra+nra
#        print("jj",jj,"nra",nra,"nr1",nr1)
    if smin>snra:
        smin=snra
print(smin)

Submission status: Wrong Answer

Solution code:
n = int(input())

def solve(num, c):
    if num == 0:
        return c
    result = []
    for i in [9, 6]:
        j = 0
        while i**(j+1) <= num:
            j += 1
        result.append(solve(num%(i**j), c+(num//(i**j))))
    return min(result)

print(solve(n, 0))

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    mon6=[6]
    mon9=[1]
    for i in range(5):
        mon6.append(6*mon6[i])
        mon9.append(9*mon9[i])
    mon=mon6+mon9
    mon.sort()

    inf=10**9
    dp=[[inf]*n for i in range(13)]
    
    dp[0][0]=1
    for i in range(12):
        for j in range(n):
            if j-mon[i]>=0:
                dp[i+1][j]=min(dp[i+1][j-mon[i]]+1,dp[i][j])
            else:
                dp[i+1][j]=dp[i][j]
    print(dp[-1][-1]) 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
n6 = 1
n9 = 1
li = []
while 9**n9 < N:
    li.append(9**n9)
    n9 += 1
while 6**n6 < N:
    li.append(6**n6)
    n6 += 1

li.sort()
INF = 10**10
# 1円の場合はね
dp = [[i for i in range(N+1)] for i in range(len(li) + 1)]
dp = [i for i in range(N+1)]


for i,l in enumerate(li):
    for j in range(N+1):
        if j+l > N : continue
        dp[j+l] = min(dp[j+l], dp[j]+1)
    # print(dp)
print(dp[N])

Submission status: Wrong Answer

Solution code:
N = int(input())
dp = [0] * (N+1)
import math
import heapq
for i in range(1,N+1):
    A = []
    heapq.heapify(A)
    k = dp[i-1] +1
    heapq.heappush(A,k)
    s6 = int(math.log(i,6))
    s9 = int(math.log(i,9))
    for j in range(1,s6+1):
        d = i - 6**j
        l = dp[d] + 1
        heapq.heappush(A,l)
    for j in range(1,s9+1):
        dl = i - 9**j
        lu = dp[dl] + 1
        heapq.heappush(A,lu)
    dp[i] = heapq.heappop(A)
print(dp[N])

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=n
for i in range(n):
    buf=0
    j=n-i
    while i>0:
        i0=i%6
        i=(i-i0)//6
        buf+=i0
    while j>0:
        j0=j%9
        j=(j-j0)//9
        buf+=j0
    if buf<ans:
        ans=buf
print(ans)

Submission status: Wrong Answer

Solution code:
list1=[6**i for i in range(1,7)]
list2=[9**i for i in range(1,6)]
data=[1]
data+=list1+list2
data.sort()
N=int(input())
count=0
dp=[10**7 for i in range(0,N+1)]
dp[1]=1
for i in range(2,N+1):
    max=0
    start=0
    end=11
    while end-start>1:
        test=(start+end)//2
        if N>=data[test]:
            start=test
        else:
            end=test
    if N>=data[end]:
        max=end
    else:
        max=start
    dp[i]=1+min(dp[i-data[j]] for j in range(0,max+1))
print(dp[N])

Submission status: Wrong Answer

Solution code:
'''
DPで解く
操作を以下2パターンとして考える
 6 ** 0(= 1), 6 ** 1, 6 ** 2...
 9 ** 0(= 1), 9 ** 1, 9 ** 2...
'''

N = int(input())

# DPテーブル
dp = [10 ** 5] * N

# 6 or 9 の累乗のリスト
six = []
c = 0
while True:
    w = 6 ** c
    if w > N:
        break
    six.append(w)
    c += 1 
nine = []
c = 0
while True:
    w = 9 ** c
    if w > N:
        break
    nine.append(w)
    c += 1 

# 初期値
dp[0] = 1

# ループ
for i in range(N):
    # 6の累乗を引き出すケース
    for s in six:
        if i + s >= N:
            break
        dp[i + s] = min(dp[i + s], dp[i] + 1)
    # 9の累乗を引き出すケース
    for n in nine:
        if i + n >= N:
            break
        dp[i + n] = min(dp[i + n], dp[i] + 1)

# 解を出力
print(dp[N - 1])

Submission status: Wrong Answer

Solution code:
'''
DPで解く
操作を以下2パターンとして考える
 6 ** 0(= 1), 6 ** 1, 6 ** 2...
 9 ** 0(= 1), 9 ** 1, 9 ** 2...
'''

N = int(input())

# DPテーブル
dp = [10 ** 5] * N
six = [6 ** x for x in range(8)]
nine = [9 ** x for x in range(6)]

# 初期値
dp[0] = 1

# ループ
for i in range(1, N):
    # 6の累乗を引き出すケース
    for s in six:
        if i + s >= N:
            break
        dp[i + s] = min(dp[i + s], dp[i] + 1)
    # 9の累乗を引き出すケース
    for n in nine:
        if i + n >= N:
            break
        dp[i + n] = min(dp[i + n], dp[i] + 1)

# 解を出力
print(dp[N - 1])

Submission status: Wrong Answer

Solution code:
'''
DPで解く
操作を以下2パターンとして考える
 6 ** 0(= 1), 6 ** 1, 6 ** 2...
 9 ** 0(= 1), 9 ** 1, 9 ** 2...
'''

N = int(input())

# DPテーブル
dp = [10 ** 5] * N
six = [6 ** x for x in range(8)]
nine = [9 ** x for x in range(6)]

# 初期値
dp[0] = 1

# ループ
for i in range(N):
    # 6の累乗を引き出すケース
    for s in six:
        if i + s >= N:
            break
        dp[i + s] = min(dp[i + s], dp[i] + 1) 
    # 9の累乗を引き出すケース
    for n in nine:
        if i + n >= N:
            break
        dp[i + n] = min(dp[i + n], dp[i] + 1)
    
# 解を出力
print(dp[N - 1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

n=int(input())
maxn=110000
memo=[-1 for i in range(maxn)]
def rec(n):
    if n==0:
        return 0
    if memo[n]!=-1:
        return memo[n]
    res=n
    i=1
    while i<=n:
        res=min(res,rec(n-i)+1)
        i*=6
    j=1
    while i<=n:
        res=min(res,rec(j-i)+1)
        j*=9
    memo[n]=res
    return memo[n]
print(rec(n))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [6,9,36,81,216,729,1296,6561,7776,46656,59049]
money = n
hiki = 0
while money >= 6:
    for i in range(len(a)):
        if money >= 59049:
            money = money-59049
            hiki += 1
            break
        else:
            if money >= a[i]:
                pass
            else:
                money = money-a[i-1]
                hiki += 1
                break
print(hiki+money)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
dp[6:9]=range(1,4)
for n in range(9,N+1):
  k6=int(math.log(n,6))
  k9=int(math.log(n,9))
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
for n in range(6,N+1):
  k6=int(math.log(n,6))
  k9=int(math.log(n,9))
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Submission status: Wrong Answer

Solution code:
# 貪欲的だが「6^i円で払う分」と「9^i円で払う分」にNを分割してN+1通り全探索．


def how_many_times_withdraw(withdraw, base, limit):
    result = 0
    while withdraw > base:
        result += withdraw // (base ** limit)
        withdraw = withdraw % (base ** limit)
        limit -= 1
    return result + withdraw


def main():
    N = int(input())
    limit = []
    answer = float("inf")
    for yen in [6, 9]:
        i = 1
        while yen ** i <= N:
            i += 1
        if yen ** i == N:
          limit.append(i)
        else:
          limit.append(i - 1)
    for i in range(N + 1):
        answer = min(answer, how_many_times_withdraw(i, 6, limit[0]) + how_many_times_withdraw(N - i, 9, limit[1]))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 貪欲的だが「6^i円で払う分」と「9^i円で払う分」にNを分割してN+1通り全探索．


def how_many_times_withdraw(withdraw, base, limit):
    result = 0
    while withdraw > base:
        result += withdraw // (base ** limit)
        withdraw = withdraw % (base ** limit)
        limit -= 1
    return result + withdraw


def main():
    N = int(input())
    limit = []
    answer = float("inf")
    for yen in [6, 9]:
        i = 1
        while yen ** i <= N:
            i += 1
        limit.append(i - 1)
    for i in range(N + 1):
        answer = min(answer, how_many_times_withdraw(i, 6, limit[0]) + how_many_times_withdraw(N - i, 9, limit[1]))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
#n = 3
inf = float('inf')

dp = [inf]*(n+1000000)
dp[0]=0
#print(dp)
#print(len(dp))

def motome(target):
    tmp = []
    a = int(math.log(target,9))
    b = int(math.log(target,6))
    for i in range(a+1):
        tmp.append(9**i)
    for j in range(b+1):
        tmp.append(6**j)
    #print(tmp) 
    #[1, 6, 36, 1, 9, 81]
    #print(dp)
    for k in range(target+1):
        for t in sorted(list(set(tmp))):
            if k-t>=0:
                dp[k] = min(dp[k],1 + dp[k-t])
                #dp[k] = min([dp[k-t] for t in tmp])
                '''
                try:
                    dp[k] = min(dp[k],1 + min([dp[k-t] for t in tmp]))
                except:
                    print(len(dp),dp[k-t],dp[k])
                    pass
                '''
        #print(k)
        #print([t for t in tmp])
        #print([dp[k-t] for t in tmp])

motome(n)
#print(dp[n-1])
print(dp[n])
#print(dp)
#print(dp[n+2])
#print(dp[n-1])
#print(dp[n])

Submission status: Wrong Answer

Solution code:
import math
#n = int(input())
n = 127
inf = float('inf')

dp = [inf]*(n+1000000)
dp[0]=0
#print(dp)
#print(len(dp))

def motome(target):
    tmp = []
    a = int(math.log(target,9))
    b = int(math.log(target,6))
    for i in range(a+1):
        tmp.append(9**i)
    for j in range(b+1):
        tmp.append(6**j)
    #print(tmp) 
    #[1, 6, 36, 1, 9, 81]
    #print(dp)
    for k in range(target+1):
        for t in sorted(list(set(tmp))):
            if k-t>=0:
                dp[k] = min(dp[k],1 + dp[k-t])
                #dp[k] = min([dp[k-t] for t in tmp])
                '''
                try:
                    dp[k] = min(dp[k],1 + min([dp[k-t] for t in tmp]))
                except:
                    print(len(dp),dp[k-t],dp[k])
                    pass
                '''
        #print(k)
        #print([t for t in tmp])
        #print([dp[k-t] for t in tmp])

motome(n)
#print(dp[n-1])
print(dp[n])

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
#n = 44852
inf = float('inf')

dp = [inf]*(n+10000000)
dp[0]=0
#print(dp)
#print(len(dp))

def motome(target):
    tmp = []
    a = int(math.log(target,9))
    b = int(math.log(target,6))
    for i in range(a+1):
        tmp.append(6**i)
    for j in range(b+1):
        tmp.append(9**j)
    #print(tmp) [1, 6, 36, 1, 9, 81]
    #print(dp)
    for k in range(1,target+1):
        for t in sorted(list(set(tmp))):
            if k-t>=0:
                dp[k] = min(dp[k],1 + dp[k-t])
                '''
                try:
                    dp[k] = min(dp[k],1 + min([dp[k-t] for t in tmp]))
                except:
                    print(len(dp),dp[k-t],dp[k])
                    pass
                '''
        #print(k)
        #print([t for t in tmp])
        #print([dp[k-t] for t in tmp])

motome(n)
#print(dp[n-1])
print(dp[n])

Submission status: Wrong Answer

Solution code:
import math
#n = int(input())
n = 44852
inf = float('inf')

dp = [inf]*(n+10000000)
dp[0]=0
#print(dp)
#print(len(dp))

def motome(target):
    tmp = []
    a = int(math.log(target,9))
    b = int(math.log(target,6))
    for i in range(a+1):
        tmp.append(6**i)
    for j in range(b+1):
        tmp.append(9**j)
    #print(tmp) [1, 6, 36, 1, 9, 81]
    #print(dp)
    for k in range(1,target+1):
        for t in sorted(list(set(tmp))):
            if k-t>=0:
                dp[k] = min(dp[k],1 + dp[k-t])
                '''
                try:
                    dp[k] = min(dp[k],1 + min([dp[k-t] for t in tmp]))
                except:
                    print(len(dp),dp[k-t],dp[k])
                    pass
                '''
        #print(k)
        #print([t for t in tmp])
        #print([dp[k-t] for t in tmp])

motome(n)
#print(dp[n-1])
print(dp[n])

Submission status: Wrong Answer

Solution code:
N = int(input())

a = N
for i in range(N):
  cc = 0
  t = i
  while t > 0:
    cc += t%6
    t //= 6
  t = N - i
  while t > 0:
    cc += t%9
    t //= 9
  if a > cc:
    a = cc
    
print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [n]*(n+10)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
    power = 1
    while power < i:
        dp[i] = min(dp[i], 1 + dp[i-power])
        power *= 6
    power = 9
    while power < i:
        dp[i] = min(dp[i], 1 + dp[i - power])
        power *= 9
print(dp[n])

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [n]*(n+10)
dp[0] = 0
for i in range(n+1):
    power = 1
    while power < n:
        dp[i] = min(dp[i], 1 + dp[i-power])
        power *= 6
    power = 9
    while power < n:
        dp[i] = min(dp[i], 1 + dp[i - power])
        power *= 9
print(dp[n])

Submission status: Wrong Answer

Solution code:
N = int(input())

def num_withdraw_ll(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(1, N):
        dp[n + 1] = min(dp[n + 1], dp[n] + 1)
        coin = 6
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 6
        coin = 9
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 9
    return dp[N]    

print(num_withdraw_ll(N))

Submission status: Wrong Answer

Solution code:
a = int(input())
l1 = [6**i for i in range(7)]
l2 = [9**i for i in range(7)]
l = sorted(l1 + l2)
l.pop(0)
l.pop(-1)
cnt = 0
#print(l)
while a != 0:
#  print(a)
  for i in range(len(l)):
    if a - l[i] < 0:
      a -= l[i-1]
      cnt += 1
      break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
a = int(input())
l1 = [6**i for i in range(7)]
l2 = [9**i for i in range(7)]
l = sorted(l1 + l2)
l.pop(0)
l.pop(-1)
cnt = 0
print(l)
while a != 0:
  print(a)
  for i in range(len(l)):
    if a - l[i] < 0:
      a -= l[i-1]
      cnt += 1
      break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

dp = [10 ** 6] * (n+1)

dp[0] = 1

for i in range(n):
    dp[i+1] = min(dp[i+1], dp[i] + 1)
    for j in range(n):
        if i + 6 ** j >= n:
            break
        dp[i + 6 ** j] = min(dp[i + 6 ** j], dp[i] + 1)
        if not i + 9 ** j >= n:
            dp[i + 9 ** j] = min(dp[i + 9 ** j], dp[i] + 1)

print(dp[n-1])

Submission status: Wrong Answer

Solution code:
l = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776]
n = int(input())
ans = [10**9 for _ in range(n+1)]
ans[0] = 0

for i in range(n):
    for j in l:
        if i + j <= n:
            ans[i+j] = min(ans[i] + 1,ans[i+j])
        
print(ans[n])

Submission status: Wrong Answer

Solution code:
import bisect as bs
import sys
input=sys.stdin.readline
NUM=int(input())
li6=[6**i for i in range(7)]
li9=[9**i for i in range(6)]

def s69(N):
    if N<6:
        return N
    else:
        s6=li6[bs.bisect(li6,N)-1]
        s9=li9[bs.bisect(li9,N)-1]
        return min(N//s6+s69(N%s6),N//s9+s69(N%s9))
print(s69(NUM))

Submission status: Wrong Answer

Solution code:
import bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]
print(li6)
print(li9)

def s69(n):
    if n < 6:
        return n
    else:
        s6 = li6[bi.bisect(li6, n) - 1]
        s9 = li9[bi.bisect(li9, n) - 1]
        return min(n // s6 + s69(n % s6), 1 + s69(n - s9))


print(s69(int(input())))

Submission status: Wrong Answer

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

N = int(input())

dp = [10**9] * (N+1)
dp[1] = 1

for n in range(1, N+1):
  for i in range(1, N+1):
    if 6**(i-1) > N+1:
      break
    
    if n - 6**(i-1) < 1:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 6**(i-1)] + 1)
  
  for i in range(1, N+1):
    if 9**(i-1) > N+1:
      break
    
    if n - 9**(i-1) < 1:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 9**(i-1)] + 1)

print(dp[N])

Submission status: Wrong Answer

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

N = int(input())

dp = [10**9] * (N+1)
dp[1] = 1

for n in range(1, N+1):
  for i in range(1, N+1):
    if 6**(i-1) > N:
      break
    
    if n - 6**(i-1) < 1:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 6**(i-1)] + 1)
  
  for i in range(1, N):
    if 9**(i-1) > N:
      break
    
    if n - 9**(i-1) < 1:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 9**(i-1)] + 1)

print(dp[N])

Submission status: Wrong Answer

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

N = int(input())

dp = [10**9] * (N+3)
dp[1] = 1

for n in range(1, N+1):
  for i in range(1, N+1):
    if 6**(i-1) > N:
      break
    
    if n - 6**(i-1) < 0:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 6**(i-1)] + 1)
  
  for i in range(1, N):
    if 9**(i-1) > N:
      break
    
    if n - 9**(i-1) < 0:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 9**(i-1)] + 1)

print(dp[N])

Submission status: Wrong Answer

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

N = int(input())

dp = [10**5] * (N+1)
dp[1] = 1

for n in range(1, N+1):
  for i in range(1, N+1):
    if 6**(i-1) > N:
      break
    
    if n - 6**(i-1) < 0:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 6**(i-1)] + 1)
  
  for i in range(1, N):
    if 9**(i-1) > N:
      break
    
    if n - 9**(i-1) < 0:
      continue
    
    dp[n] = chmin(dp[n], dp[n - 9**(i-1)] + 1)

print(dp[N])

Submission status: Wrong Answer

Solution code:
def knapsack(N,W,weight,value):
  #初期化
  dp=[[10**7 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=i
  
  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
        
  
  return dp[N][W]

N = 12
W = int(input())
weight = [1,6,36,216,1296,7776,46656,9,81,729,6561,590491]
value = [1,1,1,1,1,1,1,1,1,1,1,1,1]

a = knapsack(N,W,weight,value)

print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())

M = []

for i in range(1, 10):
  roku = 6**i
  kyu = 9**i
  if roku < 100000:
    M.append(roku)
  if kyu < 100000:
    M.append(kyu)
    
m = sorted(M)

dp = [0]*(N+1)
dp[0] = 0
dp[1] = 1
for k in range(2, N+1):
  mini = 100000
  for i in m:
    if k - i >= 0:
      mini = min(mini, dp[k-i]+1)
  dp[k] = mini
  
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())

M = []

for i in range(1, 10):
  roku = 6**i
  kyu = 9**i
  if roku < 100000:
    M.append(roku)
  if kyu < 100000:
    M.append(kyu)
    
m = sorted(M)

dp = [0]*(N+1)
dp[0] = 0
dp[1] = 1
for k in range(2, N+1):
  mini = 100000
  for i in m:
    if k - i >= 0:
      print(mini, k, i)
      mini = min(mini, dp[k-i]+1)
  dp[k] = mini
  
print(dp[-1])

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
done = []
#探索スタート地点を「探索候補スタック」に積む
arr =  [N]
ans = 0
stop = 0
  
#while スタックが空っぽになるまで
while arr:
#    スタックから次の探索地点を1つ取り出す（pop）
  a = arr.pop(0)
#    「探索済みリスト」に取り出した地点を格納（ここが現在地点）
  done.append(a)
#　　現在地点から、次に行こうと思えば行けるポイントを全部探し出す
  Next = []
  if a-1 >= 0:
    Next.append(a-1)
  if a-6 >= 0:
    Next.append(a-6)
  if a-36 >= 0:
    Next.append(a-36)
  if a-216 >= 0:
    Next.append(a-216)
  if a-1296 >= 0:
    Next.append(a-1296)
  if a-7776 >= 0:
    Next.append(a-7776)
  if a-46656 >= 0:
    Next.append(a-46656)
  if a-9 >= 0:
    Next.append(a-9)
  if a-81 >= 0:
    Next.append(a-81)
  if a-729 >= 0:
    Next.append(a-729)
  if a-6561 >= 0:
    Next.append(a-6561)
  if a-59049 >= 0:
    Next.append(a-59049)
    
  for i in Next:
    if i in done:
      continue
    elif i in arr:
      continue
    else:
      arr.append(i)
      if i == 0:
        stop = 1
        break
  ans += 1
  if stop == 1:
    break

print(ans)

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(1, n+1):
        if i == num:
            dp[i] = 1
        elif i > num:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
dp[0] = 0
for num in nums:
    for i in range(1, n+1):
        if i >= num:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
dp[0] = 0
for num in nums:
    for i in range(1, n+1):
        if i == num:
            dp[i] = 1
        elif i > num:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(1, n+1):
        if i == num:
            dp[i] = 1
        else:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(n+1):
        if i <= num and i % num == 0:
            dp[i] = min(dp[i], i // num)
        else:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(1, n+1):
        if i <= num and i % num == 0:
            dp[i] = min(dp[i], i // num)
        else:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

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


def make_list(n, x):
    return [x ** i for i in range(1, int(log(n, x))+1)]


sixes = make_list(n, 6)
nines = make_list(n, 9)
nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(1, n+1):
        if i <= num:
            dp[i] = min(dp[i], num)
        else:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
wt = int(input())
w = [1]
for i in range(7):
    w.append(6 ** (i + 1))
for i in range(5):
    w.append(9 ** (i + 1))
print(w)
n = len(w)
dp = [[float("inf") for i in range(wt + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(wt + 1):
        if j >= w[i]:
            dp[i + 1][j] = min(dp[i + 1][j - w[i]] + 1, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][wt])

Submission status: Wrong Answer

Solution code:
n = int(input())
l9 = [9**i for i in range(0,6)]
l6 = [6**i for i in range(0,6)]
l = sorted(l9+l6,reverse=True)
print(l)
i = 0
ans = 0
while(n>0):
  if n - l[i] < 0:
    i += 1
    n = n
  else:
    ans+=1
    #print(n,"-",l[i],"=",n-l[i],"ans=",ans)
    n = n - l[i]
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
a = b = 1
while True:
    a *= 6
    b *= 9
    if a > 100000:
        break
    l.append(a)
    l.append(b)

l.sort(reverse=True)
count = 0
for i in range(len(l)):
    if n >= l[i]:
        n -= l[i]
        count += 1
    if n==0:
        print(count)
        exit()
if n > 0:
    print(count+n)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
can=set()

can.add(1)
i=1
ans=0
while True:
  ans=6**i
  if ans<=100000:
    can.add(ans)
    i+=1
  else:
    break
    
j=1
ans=0
while True:
  ans=9**j
  if ans<=100000:
    can.add(ans)
    j+=1
  else:
    break

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

for k in range(2,N+1):
  mini=1000000
  for item in can:
    if k-item>=1:
      mini=min(mini, dp[k-item]+1)
  dp[k]=mini

print(dp[-1])