Submission #5118558


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

// 配るDP ver

ll ll_pow(ll a, ll n){
    ll ans = 1;
    FOR(i, 0, n){
        ans *= a;
    }
    return ans;
}

vector<ll> coins;
const int N_MAX = 200010;
ll dp[N_MAX];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin >> N;

    FOR(i, 0, N_MAX){
        dp[i] = inf;
    }

    coins.push_back(1);
    FOR(i, 1, 7){
        coins.push_back(ll_pow(6, i));
    }
    FOR(i, 1, 6){
        coins.push_back(ll_pow(9, i));
    }

    dp[0] = 0;
    FOR(i, 0, 100000){
        for(ll c : coins){
            ll num = dp[i] + 1;
            dp[i+c] = min(dp[i+c], num);
        }
    }

    p(dp[N]);
    
    return 0;
}

Submission Info

Submission Time
Task C - Strange Bank
User peroon
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1058 Byte
Status AC
Exec Time 4 ms
Memory 1792 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 19
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
01.txt AC 4 ms 1792 KB
02.txt AC 4 ms 1792 KB
03.txt AC 4 ms 1792 KB
04.txt AC 4 ms 1792 KB
05.txt AC 4 ms 1792 KB
06.txt AC 4 ms 1792 KB
07.txt AC 4 ms 1792 KB
08.txt AC 4 ms 1792 KB
09.txt AC 4 ms 1792 KB
10.txt AC 4 ms 1792 KB
11.txt AC 4 ms 1792 KB
12.txt AC 4 ms 1792 KB
13.txt AC 4 ms 1792 KB
14.txt AC 4 ms 1792 KB
15.txt AC 4 ms 1792 KB
16.txt AC 4 ms 1792 KB
sample_01.txt AC 4 ms 1792 KB
sample_02.txt AC 4 ms 1792 KB
sample_03.txt AC 4 ms 1792 KB