stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



const int MAX_N = 110000;



int dp[MAX_N]; // dp[i] が i についての答え



int main() {

	int N;

	cin >> N;



	// 初期化

	for (int i = 0; i < MAX_N; ++i) dp[i] = N; // INF の気持ち

	dp[0] = 0;



	// 集める DP --- dp[n] に遷移を集める

	for (int n = 1; n <= N; ++n) {

		for (int pow6 = 1; pow6 <= n; pow6 *= 6) {

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

		}

		for (int pow9 = 1; pow9 <= n; pow9 *= 9) {

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

		}

	}



	cout << dp[N] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

using namespace std;



// a 進法で n の桁和

int func(int n, int a) {

	int res = 0;

	while (n > 0) {

		res += n%a;

		n /= a;

	}

	return res;

}



int main() {

	int N;

	cin >> N;



	int res = N; // INF

	for (int i = 0; i <= N; ++i) {

		int tmp = func(i, 6) + func(N - i, 9);

		res = min(res, tmp);

	}



	cout << res << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <queue>

using namespace std;



const int MAX_N = 110000;



int dp[MAX_N]; // dp[i] が i についての答え



int main() {

	int N;

	cin >> N;



	// 初期化

	for (int i = 0; i < MAX_N; ++i) dp[i] = -1;

	dp[0] = 0;

	queue<int> que;

	que.push(0);



	// BFS

	while (!que.empty()) {

		int v = que.front();

		que.pop();



		for (int pow6 = 1; v + pow6 <= N; pow6 *= 6) {

			if (dp[v + pow6] == -1) {

				dp[v + pow6] = dp[v] + 1;

				que.push(v + pow6);

			}

		}

		for (int pow9 = 1; v + pow9 <= N; pow9 *= 9) {

			if (dp[v + pow9] == -1) {

				dp[v + pow9] = dp[v] + 1;

				que.push(v + pow9);

			}

		}

	}



	cout << dp[N] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

using namespace std;



// a 進法で n の桁和

int func(int n, int a) {

	int res = 0;

	while (n > 0) {

		res += n%a;

		n /= a;

	}

	return res;

}



int main() {

	int N;

	cin >> N;



	int res = N; // INF

	for (int i = 0; i <= N; ++i) {

		int tmp = func(i, 6) + func(N - i, 9);

		res = min(res, tmp);

	}



	cout << res << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

using namespace std;



// DPテーブル

const int MAX_N = 15;

const int MAX_W = 110000;

int dp[MAX_N][MAX_W]; // 12 種類だが余裕をもつ



int main() {

	int W;

	cin >> W;



	// 品物を列挙 (価値はすべて 1)

	vector<int> weight;

	for (int i = 1; i <= W; i *= 6) weight.push_back(i);

	for (int i = 9; i <= W; i *= 9) weight.push_back(i); // 1 が重複しないように (しても問題はない)

	int n = (int)weight.size();



	// DP初期条件: dp[i][0] = 0

	for (int i = 0; i < MAX_N; ++i) for (int w = 0; w < MAX_W; ++w) dp[i][w] = 1 << 29; // INF

	for (int i = 0; i <= n; ++i) dp[i][0] = 0;



	// DPループ

	for (int i = 0; i < n; ++i) {

		for (int w = 0; w <= W; ++w) {

			if (w >= weight[i]) dp[i + 1][w] = min(dp[i + 1][w - weight[i]] + 1, dp[i][w]);

			else dp[i + 1][w] = dp[i][w];

		}

	}



	cout << dp[n][W] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

using namespace std;



// DPテーブル

const int MAX_W = 110000;

int dp[MAX_W];



int main() {

	int W;

	cin >> W;



	// 品物を列挙 (価値はすべて 1)

	vector<int> weight;

	for (int i = 1; i <= W; i *= 6) weight.push_back(i);

	for (int i = 9; i <= W; i *= 9) weight.push_back(i); // 1 が重複しないように (しても問題はない)

	int n = (int)weight.size();



	// DP初期条件: dp[i][0] = 0

	for (int w = 0; w < MAX_W; ++w) dp[w] = 1 << 29; // INF

	dp[0] = 0;



	// DPループ

	for (int i = 0; i < n; ++i) {

		for (int w = weight[i]; w <= W; ++w) {

			dp[w] = min(dp[w], dp[w - weight[i]] + 1);

		}

	}



	cout << dp[W] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

using namespace std;



// DPテーブル

const int MAX_N = 15;

const int MAX_W = 110000;

int dp[MAX_N][MAX_W]; // 12 種類だが余裕をもつ



int main() {

	int W;

	cin >> W;



	// 品物を列挙 (価値はすべて 1)

	vector<int> weight;

	for (int i = 1; i <= W; i *= 6) weight.push_back(i);

	for (int i = 9; i <= W; i *= 9) weight.push_back(i); // 1 が重複しないように (しても問題はない)

	int n = (int)weight.size();



	// DP初期条件: dp[i][0] = 0

	for (int i = 0; i < MAX_N; ++i) for (int w = 0; w < MAX_W; ++w) dp[i][w] = 1 << 29; // INF

	for (int i = 0; i <= n; ++i) dp[i][0] = 0;



	// DPループ

	for (int i = 0; i < n; ++i) {

		for (int w = 0; w <= W; ++w) {

			dp[i + 1][w] = min(dp[i + 1][w], dp[i][w]);

			if (w >= weight[i]) dp[i + 1][w] = min(dp[i + 1][w], dp[i + 1][w - weight[i]] + 1);

		}

	}



	cout << dp[n][W] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

using namespace std;



// DPテーブル

const int MAX_W = 110000;

int dp[MAX_W];



int main() {

	int W;

	cin >> W;



	// 品物を列挙 (価値はすべて 1)

	vector<int> weight;

	for (int i = 1; i <= W; i *= 6) weight.push_back(i);

	for (int i = 9; i <= W; i *= 9) weight.push_back(i); // 1 が重複しないように (しても問題はない)

	int n = (int)weight.size();



	// DP初期条件: dp[i][0] = 0

	for (int w = 0; w < MAX_W; ++w) dp[w] = 1 << 29; // INF

	dp[0] = 0;



	// DPループ

	for (int i = 0; i < n; ++i) {

		for (int w = weight[i]; w <= W; ++w) {

			dp[w] = min(dp[w], dp[w - weight[i]] + 1);

		}

	}



	cout << dp[W] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

#include<queue>

#include<random>

#include<map>

#include<functional>

using namespace std;

#define int long long

#define inf 21000000145141919

#define rep(i,n) for(int i=0;i<n;i++)

typedef pair<int, int>P;

struct edge { int to, cost; };

int dp[114514];

signed main() {

	int n; cin >> n;

	vector<int>Q;

	int a = 1;

	rep(i, 10) {

		Q.push_back(a);

		a *= 6;

	}a = 1; rep(i, 10) {

		Q.push_back(a);

		a *= 9;

	}

	int ans = 0;

	sort(Q.begin(), Q.end());

	fill(dp, dp + 114514, 1145141919);

	dp[0] = 0;

	dp[1] = 1;

	rep(i, Q.size()) {

		for (int j= 2; j <= n; j++) {

			int b = j - Q[i];

			if (b >= 0)dp[j] = min(dp[j], dp[b] + 1);

		}

	}

	cout << dp[n] << endl;

}

// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"

#include<assert.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)

#define int long long

const int inf = 1e17;

const int mod = 1000000007;

typedef pair<int, int> P;

typedef pair<int, P> PP;

int dp[100006];

vector<int>K;

signed main() {

	int n; cin >> n;

	int now = 1;

	rep(i, 7){K.push_back(now); now *= 6;

}

	now = 1;

	rep(i, 7) {

		K.push_back(now); now *= 9;

	}

	fill(dp, dp + n + 1, inf);

	dp[0] = 0;

	rep(i, n) {

		rep(j, K.size()) {

			if (i + K[j] <= n)dp[i + K[j]] = min(dp[i + K[j]], dp[i] + 1);

		}

	}

	cout << dp[n] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(n);i++)

#define ALL(v) (v).begin(),(v).end()

#define int long long

using namespace std;

typedef vector<int>   vint;

typedef pair<int,int> pint;



int memo[110000];



int rec(int N){

    if(N==0) return 0;

    if(memo[N]!=-1) return memo[N];



    int res=N;

    for(int i=1;i<=N;i*=6)

        res=min(res,rec(N-i)+1);

    for(int i=1;i<=N;i*=9)

        res=min(res,rec(N-i)+1);

    return memo[N]=res;

}



signed main()

{

    int N; cin>>N;

    REP(i,110000) memo[i]=-1;

    cout<<rec(N)<<endl;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(n);i++)

#define ALL(v) (v).begin(),(v).end()

#define int long long

using namespace std;

typedef vector<int>   vint;

typedef pair<int,int> pint;



signed main()

{

    int N; cin>>N;

    vint dp(N+1,N);



    dp[0]=0;

    for(int i=1;i<=N;i++){

        for(int j=1;j<=i;j*=6){

            dp[i]=min(dp[i],dp[i-j]+1);

        }

        for(int j=1;j<=i;j*=9){

            dp[i]=min(dp[i],dp[i-j]+1);

        }

    }

    cout<<dp[N]<<endl;

 

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

using namespace std;



// DPテーブル

const int MAX_N = 15;

const int MAX_W = 110000;

int dp[MAX_N][MAX_W]; // 12 種類だが余裕をもつ



int main() {

    int W;

    cin >> W;



    // 品物を列挙 (価値はすべて 1)

    vector<int> weight;

    for (int i = 1; i <= W; i *= 6) weight.push_back(i);

    for (int i = 9; i <= W; i *= 9) weight.push_back(i); // 1 が重複しないように (しても問題はない)

    int n = (int)weight.size();



    // DP初期条件: dp[i][0] = 0

    for (int i = 0; i < MAX_N; ++i) for (int w = 0; w < MAX_W; ++w) dp[i][w] = 1 << 29; // INF

    for (int i = 0; i <= n; ++i) dp[i][0] = 0;



    // DPループ

    for (int i = 0; i < n; ++i) {

        for (int w = 0; w <= W; ++w) {

            dp[i + 1][w] = min(dp[i + 1][w], dp[i][w]);

            if (w >= weight[i]) dp[i + 1][w] = min(dp[i + 1][w], dp[i + 1][w - weight[i]] + 1);

        }

    }



    cout << dp[n][W] << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

using namespace std;



// DPテーブル

const int MAX_W = 110000;

int dp[MAX_W];



int main() {

    int W;

    cin >> W;



    // 品物を列挙 (価値はすべて 1)

    vector<int> weight;

    for (int i = 1; i <= W; i *= 6) weight.push_back(i);

    for (int i = 9; i <= W; i *= 9) weight.push_back(i); // 1 が重複しないように (しても問題はない)

    int n = (int)weight.size();



    // DP初期条件: dp[i][0] = 0

    for (int w = 0; w < MAX_W; ++w) dp[w] = 1 << 29; // INF

    dp[0] = 0;



    // DPループ

    for (int i = 0; i < n; ++i) {

        for (int w = weight[i]; w <= W; ++w) {

            dp[w] = min(dp[w], dp[w - weight[i]] + 1);

        }

    }



    cout << dp[W] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int INF = 100000009;

const int DP_SIZE = 1000006;



int dp[DP_SIZE];



int main(){

	int N;

	cin >> N;

	

	for(int i=0; i<DP_SIZE; i++) dp[i] = INF;

	dp[0] = 0;

	

	for(int n=0; n<=N; n++){

		for(int pow6=1; n+pow6<=N; pow6*=6) dp[n+pow6] = min(dp[n+pow6], dp[n]+1);

		for(int pow9=1; n+pow9<=N; pow9*=9) dp[n+pow9] = min(dp[n+pow9], dp[n]+1);

	}

	

	cout << dp[N] << endl;

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main(){

    int n;

    cin >> n;

    int ans = n;

    for(int i=0; i<=n; i++){

        int t = i;

        int cc = 0;

        while(t > 0) cc += t%6, t/= 6;

        t = n - i;

        while(t > 0) cc += t%9, t/=9;

        ans = min(ans, cc);

    }

    cout << ans << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll, ll> P;



#define fi first

#define se second

#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)

#define rep(i,n) repl(i,0,n)

#define all(x) (x).begin(),(x).end()

#define dbg(x) cout<<#x"="<<x<<endl

#define mmax(x,y) (x>y?x:y)

#define mmin(x,y) (x<y?x:y)

#define maxch(x,y) x=mmax(x,y)

#define minch(x,y) x=mmin(x,y)

#define uni(x) x.erase(unique(all(x)),x.end())

#define exist(x,y) (find(all(x),y)!=x.end())

#define bcnt __builtin_popcount



#define INF INT_MAX/3

#define mod 1000000007



int n;

int dp[100010];



int main(){

  cin>>n;

  rep(i,100001)dp[i]=INF;

  dp[0]=0;

  rep(i,n){

    for(int j=1;i+j<=n;j*=6)minch(dp[i+j],dp[i]+1);

    for(int j=1;i+j<=n;j*=9)minch(dp[i+j],dp[i]+1);

  }

  cout<<dp[n]<<endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll, ll> P;



#define fi first

#define se second

#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)

#define rep(i,n) repl(i,0,n)

#define all(x) (x).begin(),(x).end()

#define dbg(x) cout<<#x"="<<x<<endl

#define mmax(x,y) (x>y?x:y)

#define mmin(x,y) (x<y?x:y)

#define maxch(x,y) x=mmax(x,y)

#define minch(x,y) x=mmin(x,y)

#define uni(x) x.erase(unique(all(x)),x.end())

#define exist(x,y) (find(all(x),y)!=x.end())

#define bcnt __builtin_popcount



#define INF INT_MAX/3

#define mod 1000000007



int n;



int main(){

  cin>>n;

  int res=INF;

  rep(i,n+1){

    if(i%6!=0)continue;

    int ni=i,nj=n-i;

    int sum=0;

    ni/=6;

    while(ni>0){

      sum+=ni%6;

      ni/=6;

    }

    while(nj>0){

      sum+=nj%9;

      nj/=9;

    }

    minch(res,sum);

  }

  cout<<res<<endl;

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#define REP(i, n) for(i=0; i<n; i++)

#define REPR(i, n) for(i=n; i>=0; i--)

#define FOR(i, m, n) for(i=m; i<n; i++)

using namespace std;

typedef long long ll;

typedef pair<ll, ll> p;



ll memo[100001]={0};



ll rec(ll n);



int main(void) {

    ll n;

    cin >> n;

    

    for(int i=0; i<100001; i++)

        memo[i]=-1;

    cout << rec(n) << endl;

}



ll rec(ll n) {

    if(n==0)

        return 0;

    else if(memo[n]!=-1)

        return memo[n];

    

    ll res=n;

    

    for(int i=1; i<=n; i*=6)

        res=min(res, rec(n-i)+1);

    for(int i=1; i<=n; i*=9)

        res=min(res, rec(n-i)+1);

    

    return memo[n]=res;

}


// Optimized solution to the same problem (faster):
//もらうdp

#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N;

    cin >> N;

    ll dp[MAX];

    ll i, j;

    

    for(i=1; i<=N; i++) dp[i]=INF;

    

    dp[0]=0;

    for(i=1; i<=N; i*=6) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    for(i=1; i<=N; i*=9) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    pt(dp[N]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define pye cout << "Yes" << endl;

#define pno cout << "No" << endl;

#define prin(num) cout << num << endl;

#define sprin(str) cout << "str" << endl;

#define INF 1000000000

#define MOD 1000000007LL

#define MAX 100001

#define NIL -1

#define WHITE 0

#define GRAY 1

#define BLACK 2

using namespace std;

typedef long long ll;

typedef pair<ll, ll> PA;

typedef priority_queue<ll> PQ;

typedef pair<double, double> doup;

//typedef vector<ll> vec;

//typedef vector<vec> mat;





int main() {

    ll W;

    cin >> W;

    vector<ll> weight;

    ll dp[MAX];

    ll i, w;

    for(i=1; i<=W; i*=6) weight.push_back(i);

    for(i=9; i<=W; i*=9) weight.push_back(i);

    ll n=weight.size();

    

    for(w=0; w<MAX; w++) {

            dp[w]=INF;

    }

    dp[0]=0;

    

    for(i=0; i<n; i++) {

        for(w=weight[i]; w<=W; w++) {

            dp[w]=min(dp[w-weight[i]]+1, dp[w]);

        }

    }

    

    

    prin(dp[W]);

}


// Optimized solution to the same problem (faster):
//もらうdp

#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N;

    cin >> N;

    ll dp[MAX];

    ll i, j;

    

    for(i=1; i<=N; i++) dp[i]=INF;

    

    dp[0]=0;

    for(i=1; i<=N; i*=6) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    for(i=1; i<=N; i*=9) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    pt(dp[N]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define pr(num) cout << num << "\n"

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 100010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;



ll N;

ll memo[MAX];



ll rec(ll m) {

    if(m==0) return 0;

    if(memo[m]!=-1) return memo[m];

    

    ll res=m;

    

    for(ll i=1; i<=m; i*=6) {

        res=min(res, rec(m-i)+1);

    }

    

    for(ll i=1; i<=m; i*=9) {

        res=min(res, rec(m-i)+1);

    }

    

    return memo[m]=res;

}







int main(void) {

    cin >> N;

    memset(memo, -1, sizeof(memo));

    pr(rec(N));

    

}
















































// Optimized solution to the same problem (faster):
//もらうdp

#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N;

    cin >> N;

    ll dp[MAX];

    ll i, j;

    

    for(i=1; i<=N; i++) dp[i]=INF;

    

    dp[0]=0;

    for(i=1; i<=N; i*=6) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    for(i=1; i<=N; i*=9) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    pt(dp[N]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define pr(num) cout << num << "\n"

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 100010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;



ll memo[MAX];

ll N;



ll rec(ll n) {

    if(n==0) return 0;

    if(memo[n]!=-1) return memo[n];

    

    ll res=n;

    for(ll i=1; i<=n; i*=6) {

        res=min(res, rec(n-i)+1);

    }

    for(ll i=1; i<=n; i*=9) {

        res=min(res, rec(n-i)+1);

    }

    

    return memo[n]=res;

}





int main() {

    cin >> N;

    memset(memo, -1, sizeof(memo));

    

    pr(rec(N));

    

    

    

    

}


// Optimized solution to the same problem (faster):
//もらうdp

#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N;

    cin >> N;

    ll dp[MAX];

    ll i, j;

    

    for(i=1; i<=N; i++) dp[i]=INF;

    

    dp[0]=0;

    for(i=1; i<=N; i*=6) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    for(i=1; i<=N; i*=9) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    pt(dp[N]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//メモ再帰

#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define mCalc(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;



ll N;

ll dp[MAX];



ll rec(ll n) {

    if(n==0) return 0;

    if(dp[n]!=-1) return dp[n];

    

    ll i;

    ll res=INF;

    for(i=1; i<=n; i*=6)

        res=min(res, rec(n-i)+1);

    

    for(i=1; i<=n; i*=9)

        res=min(res, rec(n-i)+1);

    

    

    return dp[n]=res;

}





int main(void) {;

    cin >> N;

    memset(dp, -1, sizeof(dp));

    

    pt(rec(N));

}




// Optimized solution to the same problem (faster):
//もらうdp

#include <iostream>

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp make_pair

#define fi first

#define se second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

#define max(a, b) ((a)>(b) ? (a):(b))

#define min(a, b) ((a)<(b) ? (a):(b))

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N;

    cin >> N;

    ll dp[MAX];

    ll i, j;

    

    for(i=1; i<=N; i++) dp[i]=INF;

    

    dp[0]=0;

    for(i=1; i<=N; i*=6) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    for(i=1; i<=N; i*=9) {

        for(j=i; j<=N; j++) {

            chmin(dp[j], dp[j-i]+1);

        }

    }

    

    pt(dp[N]);

}


// Fastest known solution for this problem: