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: Accepted

Solution code:
N = int(input())
dp = [float('inf')]*(N+1)
dp[0] = 0
for i in range(N+1):
    if i >= 1:
        dp[i] = min(dp[i-1]+1,dp[i])
    for j in range(1,N+1):
        if i < 6**j:
            break
        dp[i] = min(dp[i-6**j]+1,dp[i])
    for k in range(1,N+1):
        if i < 9**k:
            break
        dp[i] = min(dp[i-9**k]+1,dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [float('inf')]*(N+1)
dp[0] = 0
for i in range(N+1):
    if i+1 <= N:
        dp[i+1] = min(dp[i+1],dp[i]+1)
    for j in range(1,N+1):
        if i + 6**j > N:
            break
        dp[i+6**j] = min(dp[i+6**j],dp[i]+1)
    for k in range(1,N+1):
        if i + 9**k > N:
            break
        dp[i+9**k] = min(dp[i+9**k],dp[i]+1)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

dp = [10**6 for _ in range(n+1)]
dp[0] = 0

for i in range(n+1):
    j6 = 1
    while i+j6<=n:
        dp[i+j6] = min(dp[i]+1,dp[i+j6])
        j6 *= 6
    j9 = 1
    while i+j9<=n:
        dp[i+j9] = min(dp[i]+1,dp[i+j9])
        j9 *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
def f(x):
    ans=0
    while x>0:
        ans+=x%6
        x=x//6
    return ans
def g(x):
    ans=0
    while x>0:
        ans+=x%9
        x=x//9
    return ans
ans=n
for i in range(n+1):
    ans=min(ans,f(i)+g(n-i))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
table=[-1]*100001
table[0]=0
d=deque()
d.append(0)
can=[]
can.append(1)
for i in range(1,50):
    if 6**i<=100000:
        can.append(6**i)
    else:
        break
    if 9**i<=100000:
        can.append(9**i)
while d:
    w=d.popleft()
    for i in can:
        if w+i>100000:
            continue
        if not table[w+i]==-1:
            continue
        table[w+i]=table[w]+1
        d.append(w+i)
print(table[n])

Submission status: Accepted

Solution code:
n = int(input())

dp = [0]*(n+10)

for i in range(n+1):
    dp[i+1] = dp[i] +1
    

for i in range(1,n+1):
    k = 6
    while k <=n:
        if i-k>=0:
            dp[i] = min(dp[i],dp[i-k]+1)
            #print(dp[i-1],dp[i-k])
        k *=6

        #print(dp)
    k = 9
    while k <=n:
        if i-k>=0:
            dp[i] = min(dp[i],dp[i-k]+1)
           
        k *=9

print(dp[n])

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())


#@njit
def main(n):
    dp = []
    for i in range(10**5+1):
        dp.append(i)
    dp = np.array(dp)
    powers = [1]
    i = 1
    while True:
        if 6**i>10**5:
            break
        powers.append(6**i)
        if 9**i<=10**5:
            powers.append(9**i)
        i += 1
    powers.sort()
    for i in range(1,10**5+1):
        for j in range(len(powers)):
            if powers[j]>i:
                break
            dp[i] = min(dp[i],dp[i-powers[j]]+1)

    print(dp[n])            

if __name__=="__main__":
    main(N)

Submission status: Accepted

Solution code:
def main3():
    import sys
    sys.setrecursionlimit(100000000)

    N=int(input())
    dp=[-1 for n in range(N+1)]
    dp[0]=0
    dp[1]=1
    def rec(x,dp):
        if x==1:
            return dp[1]
        elif x==0:
            return dp[0]
        else:
            l=[]
            i=0
            j=0
            while 9**(i+1)<=x:
                i+=1
            while 6**(j+1)<=x:
                j+=1
            for k in reversed(range(i+1)):
                tmp=x-9**k
                if dp[tmp]!=-1:
                    l.append(dp[tmp]+1)
                else:
                    l.append(rec(tmp,dp)+1)
            for k in reversed(range(j+1)):
                tmp=x-6**k
                if dp[tmp]!=-1:
                    l.append(dp[tmp]+1)
                else:
                    l.append(rec(tmp,dp)+1)
            dp[x]=min(l)
            return dp[x]

    return rec(N,dp)
        
if __name__=="__main__":
    print(main3())

Submission status: Accepted

Solution code:
N=int(input())
inf=100000
dp=[inf for _ in range(N+1)]
dp[0]=0
for n in range(1,N+1):
    num=100000
    i=0
    j=0
    while 9**(i+1)<=n:
        i+=1
    while 6**(j+1)<=n:
        j+=1
    for k in range(i+1):
        num=min(num,dp[n-9**k]+1)
    for k in range(j+1):
        num=min(num,dp[n-6**k]+1)
    dp[n]=min(dp[n],num)
print(dp[N])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

dp = [-1 for _ in range(10**6)]
dp[0] = 0

que = deque([0])

while que:
    v = que.popleft()
    j6 = 1
    while v+j6 <= n:
        if dp[v+j6] == -1:
            dp[v+j6] = dp[v]+1
            que.append(v+j6)
        j6 *= 6
            
    j9 = 1
    while v+j9 <= n:
        if dp[v+j9] == -1:
            dp[v+j9] = dp[v]+1
            que.append(v+j9)
        j9 *= 9
            
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

dp = [10**6 for _ in range(10**6)]
dp[0] = 0

for i in range(1,n+1):
    j6 = 1
    while 0 <= i-j6:
        dp[i] = min(dp[i-j6]+1,dp[i])
        j6 *= 6
    j9 = 1
    while 0 <= i-j9:
        dp[i] = min(dp[i-j9]+1,dp[i])
        j9 *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

dp = [10**6 for _ in range(10**6)]
dp[0] = 0

for i in range(n):
    j6 = 1
    while j6 <= n:
        dp[i+j6] = min(dp[i+j6],dp[i]+1)
        j6 *= 6
    j9 = 1
    while j9 <= n:
        dp[i+j9] = min(dp[i+j9],dp[i]+1)
        j9 *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

# a進法でのnの桁和
def func(n,a):
    res = 0
    while n > 0:
        res += n%a
        n //= a
    return res

mini = n

for i in range(n+1):
    tmp = func(i,6) + func(n-i,9)
    mini = min(mini,tmp)
print(mini)

Submission status: Accepted

Solution code:
def f(a,x):
    l=[]
    while x!=0:
        l.append(x%a)
        x//=a
    return sum(l)

def main():
    N=int(input())
    MIN=100000
    for k in range(N+1):
        MIN=min(MIN,f(9,k)+f(6,(N-k)))
    return MIN

if __name__=="__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import njit, i8

@njit(i8(i8))
def dp(N):
    dp = np.full(100005, INF, dtype=np.int64)
    dp[0] = 0
    
    for n in range(1, N + 1):
        pow6 = 1
        while pow6 <= n:
            dp[n] = min(dp[n], dp[n - pow6] + 1)
            pow6 *= 6
        pow9 = 1
        while pow9 <= n:
            dp[n] = min(dp[n], dp[n - pow9] + 1)
            pow9 *= 9
    
    return dp[n]

def Main():
    n = read_int()
    print(dp(n))    

if __name__ ==  '__main__':
    Main()

Submission status: Accepted

Solution code:
n = int(input())

dp=[0]
#dp[n]を求める

for i in range(1,n+1):
    c = []
    c.append(dp[i-1]+1)
    p6=1
    while i >=6**p6:
        c.append(dp[i-6**p6]+1)
        p6 +=1

    p9=1
    while i >=9**p9:
        c.append(dp[i-9**p9]+1)
        p9 +=1

    dp.append(min(c))

print(dp[n])

Submission status: Accepted

Solution code:
import math

n = int(input())

dp = [n] * (n+1)

dp[0] = 0
dp[1] = 1

p = int(math.log(n, 6))
q = int(math.log(n, 9))

for i in range(1, n+1):
    dp[i] = min(dp[i-1]+1, dp[i])
    for x in range(1, p+10):
        y = pow(6, x)
        if i - y >= 0:
            dp[i] = min(dp[i-y] + 1, dp[i])
        else:
            break
    for x in range(1, q+10):
        y = pow(9, x)
        if i - y >= 0:
            dp[i] = min(dp[i-y] + 1, dp[i])
        else:
            break

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [N] * 110000
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
import math
power_6 = [6 ** i for i in range(int(math.log(100000, 6)) + 1)]
power_9 = [9 ** i for i in range(int(math.log(100000, 9)) + 1)]
p = list(set(power_6 + power_9))
p.sort()
p.append(100001)

N = int(input())
 
idx = 0
cnt = [0]
i = 1
while i < N + 1:
  if p[idx] <= i < p[idx + 1]:
    c = 0
    if idx == 0:
      cnt.append(i)
    else:
      c = [cnt[i - p[j]] + 1 for j in range(idx + 1)]
      cnt.append(min(c))
    i += 1
  else:
    idx += 1

print(cnt[N])

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:
import math
N=int(input())
dp=[math.inf for _ in range(N+1)]
dp[0]=0
for i in range(1,N+1):
	p=1
	q=1
	while p<=i:
		dp[i]=min(dp[i],dp[i-p]+1)
		p*=6
	while q<=i:
		dp[i]=min(dp[i],dp[i-q]+1)
		q*=9
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())

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

inf=float('inf')
dp=[inf for _ in range(100000+1)]
dp[0]=0
dp[1]=1

for x in range(1,100001):
  for b in a:
    if b<=x:
      dp[x]=min(dp[x],dp[x-b]+1)
      
print(dp[n])

Submission status: Accepted

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    dp = [math.inf]*(N+1)
    dp[0] = 0
    for i in range(N):
        if i+1 <= N:
            dp[i+1] = min(dp[i+1], dp[i]+1)
            six = 6
            while i+six <= N:
                dp[i+six] = min(dp[i+six], dp[i]+1)
                six *= 6
            nine = 9
            while i+nine <= N:
                dp[i+nine] = min(dp[i+nine], dp[i]+1)
                nine *= 9
    return dp[N]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
N = int(input())

patterns = []
patterns.append(1)

f = 6
a = 6
while a <= N:
    patterns.append(a)
    a *= f

f = 9
a = 9
while a <= N:
    patterns.append(a)
    a *= f

dp = [float('inf')] * (N + 1)
dp[0] = 0
for n in range(1, N + 1):
    for p in patterns:
        if n - p < 0:
            continue

        dp[n] = min(dp[n - p] + 1, dp[n])


print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
tab=[10**8 for i in range(n+1)]
tab[0]=0

for i in range(n):
    now=1
    while i+now<=n:
        tab[i+now]=min(tab[i+now],tab[i]+1)
        now*=6
    now=9
    while i+now<=n:
        tab[i+now]=min(tab[i+now],tab[i]+1)
        now*=9

print(tab[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# import math
n = int(input())

ans = [-1]*(n+1)

ans[0] = 0
for i in range(1, n+1):
    num = i
    data = ans[i-1]+1
    for j in range(8):
        index = i-6**j
        if index < 0:
            break
        data = min(data, ans[index]+1)
    for j in range(8):
        index = i-9**j
        if index < 0:
            break
        data = min(data, ans[index]+1)
    ans[i] = data
print(ans[-1])

Submission status: Accepted

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

dp = [math.inf] * (n+1)

for i in range(n+1):
    dp[i] = min(dp[i],i)
    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)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

INF = 10 ** 9


def base(x, y):
    ret = 0
    while x >= y:
        ret += x % y
        x //= y
    ret += x
    return ret
        

def main():
    ans = INF
    for i in range(N + 1):
        v = base(i, 6) + base(N - i, 9)
        ans = min(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

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

    power = 9
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9

print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    dp = [float('inf') for _ in range(n + 100)]
    dp[0] = 0

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

        six = 6

        while six <= i:
            dp[i] = min(dp[i - six] + 1, dp[i])
            six *= 6

        nine = 9

        while nine <= i:
            dp[i] = min(dp[i - nine] + 1, dp[i])
            nine *= 9

    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())

ss = set()
n = 6
while n <= 10**5:
    ss.add(n)
    n *= 6
n = 9
while n <= 10**5:
    ss.add(n)
    n *= 9

dp = [None] * (N+1)

def rec(n):
    if dp[n] is not None:
        return dp[n]
    tmp = n
    for s in ss:
        if s > n: continue
        if s == n:
            tmp = 1
            break
        tmp = min(tmp, 1 + rec(n-s))
    dp[n] = tmp
    return tmp

print(rec(N))

Submission status: Accepted

Solution code:
N = int(input())

dp = [0] * 100001

dp[1] = 1

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def f(n, a):
    ans = 0
    while n > 0:
        ans += n % a
        n //= a
    return ans


def main():
    N = int(readline())

    ans = INF
    for i in range(N + 1):
        ans = min(ans, f(i, 6) + f(N - i, 9))

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    amt = [1]
    a = 6
    while a <= N:
        amt.append(a)
        a *= 6
    a = 9
    while a <= N:
        amt.append(a)
        a *= 9

    dp = [INF] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        for a in amt:
            if i >= a and dp[i] > dp[i - a]:
                dp[i] = dp[i - a] + 1

    print(dp[N])

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sinsuuton(X, n): #10進数の Xをn進数に
    if (int(X/n)):
        return sinsuuton(int(X/n), n)+str(X%n)
    return str(X%n)
def sinsuutoo10(X,n): #n進数のX(str)を10進数に
    return sum([ X[-i-1]*n**i for i in range(len(X)) ])
n=int(input())
ans=float("inf")
for i in range(n+1):
    t=i
    now=0
    t6= sinsuuton(t, 6)
    now+= sum([int(i) for i in t6])
    t=n-i
    t9= sinsuuton(t, 9)
    now+= sum([int(i) for i in t9])
    ans=min(ans,now)

print(ans)

Submission status: Accepted

Solution code:
# thought greedy was better i am noob
# classical problem no explanation needed
def main():
	n = int(input())
	dp = [0 for i in range(n+4)]
	dp[0]=0
	for i in range(1, n+2):
		p = 1
		dp[i]=1000000000000000
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p =p*9
		p=1
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p = p*6
	print(dp[n])
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
# thought greedy was better i am noob
def main():
	n = int(input())
	dp = [0 for i in range(n+4)]
	dp[0]=0
	for i in range(1, n+2):
		p = 1
		dp[i]=1000000000000000
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p =p*9
		p=1
		while i>=p:
			dp[i]=min(dp[i] , dp[i-p]+1)
			p = p*6
	print(dp[n])
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
N = int(input())
Cash = sorted([1]+[6**T for T in range(1,7)]+[9**T for T in range(1,6)])
DPList = [0]*(N+1)
for TN in range(1,N+1):
    DPList[TN] = min(DPList[TN-TC]+1 if TN>=TC else 1000000 for TC in Cash)
print(DPList[N])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
cnt = 0
d = {n:0}
q = deque([n])
while q[0] > -5:
    t = q.popleft()
    cnt = d[t]
    # print(t)
    a = 1
    b = 1
    while 6**a <= t:
        a += 1
    while 9**b <= t:
        b += 1
    a -= 1
    b -= 1
    # print(t,a,b)
    if t-6**a in d:
        if d[t-6**a] > cnt+1:
            d[t-6**a] = cnt+1
            q.append(t-6**a)
    else:
        d[t-6**a] = cnt+1
        q.append(t-6**a)
    if t-9**b in d:
        if d[t-9**b] > cnt+1:
            d[t-9**b] = cnt+1
            q.append(t-9**b)
    else:
        d[t-9**b] = cnt+1
        q.append(t-9**b)
    # print(q)
print(d[0])
# print(d)

Submission status: Accepted

Solution code:
def sub_cnt(c, b):
    cnt = 0
    for i in b:
        while c >= i:
            c -= i
            cnt += 1
    return cnt

n = int(input())

b6 = [6**i for i in range(6, -1, -1)]
b9 = [9**i for i in range(5, -1, -1)]

ans = 10**9
n9 = n // 9
for c9 in range(n9+1):
    cnt = 0
    cn = n - c9*9
    c6 = cn // 6
    c1 = cn % 6
    
    cnt += sub_cnt(c9, b9)
    cnt += sub_cnt(c6, b6)
    cnt += c1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def sub_cnt(c, b):
    cnt = 0
    for i in b:
        while c >= i:
            c -= i
            cnt += 1
    return cnt

n = int(input())

b6 = [6**i for i in range(6, -1, -1)]
b9 = [9**i for i in range(5, -1, -1)]

ans = 10**9
n9 = n // 9
for c9 in range(n9+1):
    cnt = 0
    cn = n - c9*9
    c6 = cn // 6
    c1 = cn % 6
    
    cnt += sub_cnt(c9, b9)
    cnt += sub_cnt(c6, b6)
    cnt += c1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
dp=[None]*(n+1)
dp[0]=0

a=1

lst=[]

while a<=n:
  dp[a]=1
  lst+=[a]
  a*=6

a=1

while a<=n:
  dp[a]=1
  lst+=[a]
  a*=9

for i in range(n):
  if dp[i]!=None:
    for j in lst:
      if i+j<=n:
        if dp[i+j]!=None:
          dp[i+j]=min(dp[i+j],dp[i]+1)
        else:
          dp[i+j]=dp[i]+1

print(dp[n])

Submission status: Accepted

Solution code:
import math

n = int(input())
t = 100000 + 10

dp = [10**18] * (t+10)
dp[0] = 0

for i in range(1, t+1):
    dp[i] = dp[i-1] + 1

for i in range(t-1):
    s = t-i
    for j in range(int(math.log(s, 9)+1)):
        dp[i+9**j] = min(dp[i+9**j], dp[i]+1)
    for k in range(int(math.log(s, 6)+1)):
        dp[i+6**k] = min(dp[i+6**k], dp[i]+1)


print(dp[n])

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())

pow6 = [pow(6, i + 1) for i in range(6)]
pow9 = [pow(9, i) for i in range(6)][::-1]

ans = n
for l in product(range(6), repeat=6):
    cnt = sum(l)
    num = n - sum(pi * li for pi, li in zip(pow6, l))
    if num >= 0:
        tmp = 0
        while num > 0:
            if pow9[tmp] > num:
                tmp += 1
            elif pow9[tmp] <= num:
                num -= pow9[tmp]
                cnt += 1
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:

        
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    n = int(input())
    inf = 1 << 18
    dp = [inf]*(n+1)
    dp[0] = 0
    for i in range(n):
        dp[i+1] = min(dp[i+1], dp[i]+1)
        k = 1
        while i+6**k <= n:
            dp[i+6**k] = min(dp[i+6**k], dp[i]+1)
            k += 1
        k = 1
        while i+9**k <= n:
            dp[i+9**k] = min(dp[i+9**k], dp[i]+1)
            k += 1
    print(dp[n])


    




                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache

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: Accepted

Solution code:
n=int(input())
import bisect
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
def draw(x,y):
    ind=bisect.bisect_right(l,x)-1
    if ind==0:
        return y+x
    else:
        y += 1
        x1=x-l[ind]
        x2=x-l[ind-1]
        if x1==0 or x2==0:
            return y
        else:
            return(min(draw(x1,y),draw(x2,y)))
print(draw(n,0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**9

if __name__ == "__main__":
    n = int(input())
    m = [1]
    dp = [101010]*201010
    t = 6
    q = 9
    while t<=n:
        m.append(t)
        t*=6
    while q<=n:
        m.append(q)
        q*=9
    for i in m:
        dp[i] = 1
    
    for i in range(1,n):
        for j in m:
            dp[i+j] = min(dp[i+j],dp[i]+1)
    print(dp[n])

Submission status: Accepted

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: Accepted

Solution code:
from math import log

N=int(input())

dp = [0]*(N+1)

e6 = 0
e9 = 0
for i in range(1,N+1):
  for j in range(e6,12):
    if 6**j>i:
      e6 = j-1
      break
  for j in range(e9,12):
    if 9**j>i:
      e9 = j-1
      break
  dp[i] = min(dp[i-1],dp[i-int(6**e6)],dp[i-int(9**e9)])+1
  
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
min_time = [float('inf')] * (n+1)
min_time[0] = 0
for i in range(n):
    min_time[i+1] = min(min_time[i+1],min_time[i]+1)
    times_6 = 1
    while i+6**times_6<=n:
        min_time[i+6**times_6] = min(min_time[i+6**times_6],min_time[i]+1)
        times_6 += 1
    times_9 = 1
    while i+9**times_9<=n:
        min_time[i+9**times_9] = min(min_time[i+9**times_9],min_time[i]+1)
        times_9 += 1
print(min_time[-1])

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=[0]*14
a[0]=1
a[8]=9
for i in range(1,8):
    a[i]=a[i-1]*6
for i in range(9,14):
    a[i]=a[i-1]*9
inf=10**6
dp=[[inf]*(n+1) for _ in range(15)]
dp[0][0]=0
for i in range(14):
    for j in range(n+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+a[i]<n+1:
          dp[i+1][j+a[i]]=min(dp[i+1][j]+1,dp[i+1][j+a[i]])
print(dp[-1][-1])

Submission status: Accepted

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
    j=N-i
    while j>0:
        cnt+=j%9
        j//=9
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    # 引き出せる金額リスト
    l = [1]
    a = 6
    b = 9
    while a <= N or b <= N:
        if a < b:
            l.append(a)
            a *= 6
        else:
            l.append(b)
            b *= 9

    # ナップザック
    dp = [INF] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        for j in l:
            if i - j >= 0:
                dp[i] = min(dp[i - j] + 1, dp[i])

    print(dp[-1])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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: Accepted

Solution code:
A = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
N = int(input())

dp = [N] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in A:
        if i >= j:
            dp[i] = min(dp[i], dp[i - j] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def get_num_draw(n, x):
    res = 0
    while n > 0:
        res += n % x
        n = n // x
    return res


def main():
    N = NI()
    ans = 10**10
    for i in range(0, N+1, 6):
        ans = min(get_num_draw(N-i, 9) + get_num_draw(i//6, 6), ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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)
kouho_cnt = len(kouho)
INF = 10 ** 9
dp = [INF] * ((10 ** 5) + 1)
dp[0] = 0
for i in range(1, N + 1):
    for k in kouho:
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + 1)
#print(dp)
print(dp[N])
# cur = 0
# ans = 0
# while N > 0:
#     if N >= kouho[cur]:
#         N -= kouho[cur]
#         ans += 1
#     else:
#         cur += 1
# print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())

N = I()

A = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]  # 引き出せる金額

dp = [0]*(N+1)  # dp[i] = i円引き出すのに必要な操作の回数
for i in range(N+1):
    if i == 0:
        continue
    else:
        a = N
        for j in A:
            if i >= j:
                a = min(a,dp[i-j]+1)
        dp[i] = a

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
a_6 = [int(6**i) for i in range(1,10) if 6**i <= 10**5]
a_9 = [int(9**i) for i in range(1,10) if 9**i <= 10**5]
a = [1]
for i in a_6:
    a.append(i)
for i in a_9:
    a.append(i)
a.sort(reverse = True)
dp = [i for i in range(n+1)]
dp[0] = 0
for i in range(n+1):
    for j in a:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
#coding: utf-8

N = int(input())

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

dp[0] = 0

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

print(dp[N])

Submission status: Accepted

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

money.sort()
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: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = n
for i in range(n + 1):
    j = n - i
    c = 0
    while i > 0:
        c += i % 6
        i //= 6
    while j > 0:
        c += j % 9
        j //= 9
    a = min(a, c)
print(a)

Submission status: Accepted

Solution code:
N = int(input())
ans = N

# n = 6で取り出すお金
for n in range(N + 1):
    c = 0
    price_by_6 = n
    while price_by_6 > 0:
        c += price_by_6 % 6  # これを繰り返すと必要な回数になる。まず初回にあまりがある場合には1円が必要な分だけ足される。
        price_by_6 //= 6
    price_by_9 = N - n
    while price_by_9 > 0:
        c += price_by_9 % 9  # これを繰り返すと必要な回数になる。まず初回にあまりがある場合には1円が必要な分だけ足される。
        price_by_9 //= 9
    ans = min(ans, c)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

lst = [1]
i = 1
while 6**i <= N:
  lst.append(6**i)
  i += 1
i = 1
while 9**i <= N:
  lst.append(9**i)
  i += 1

lst.sort()

dp = [100001]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  for k in lst:
    if i - k >= 0:
      dp[i] = min(dp[i],dp[i-k]+1)
      
print(dp[N])