Category Archives: Coin Change

(LightOj) 1064 – Throwing Dice

0
Posted on by 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here
#define MAXX 152

ll cnt[MAXX];

int main()
{
    int kases, kaseno = 0;

    take(kases);
    int n, x;

    while(kases--)
    {
        take(n, x);
        mem(cnt, 0);

        cnt[0] = 1;
        int mx;
        loop(tt, n)
        {
            mx = 6*tt;

            for(int i=mx; i>-1; i--)
            {
                FOR(j, 1, 7)
                {
                    cnt[i+j] += cnt[i];
                }

                cnt[i] = 0;
            }
        }
        ll upre = 0, nice = 0;
        mx = 6*n;
        for(int i=x; i<=mx; i++) upre += cnt[i];
        for(int i=1; i<x; i++) nice += cnt[i];
        nice += upre;

        ll g = __gcd(upre, nice);
        upre /= g;
        nice /= g;

        pf("Case %d: ", ++kaseno);
        if(nice == 1) pf("%lld\n", upre);
        else pf("%lld/%lld\n", upre, nice);



    }


}

(USACO) Stamps

0
Posted on by 

/*
ID: himuhas1
TASK: stamps
LANG: C++
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<sstream>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define ll long long
#define pb push_back
#define MP make_pair
#define mem(a, v) memset(a,  v, sizeof(a))
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define SZ(a) (int(a.size()))
#define INF (1<<29)
#define paii pair<int, int>
#define sf scanf
#define pf printf


using namespace std;


#define MAXX 2000002

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

int main()
{
    freopen("stamps.in", "r", stdin);
    freopen("stamps.out", "w", stdout);


    int n, k, values[52];

    sf("%d %d", &k, &n);

    loop(i, n)
    {
        sf("%d", &values[i]);
    }

    int dp[MAXX];
    mem(dp, 1);
    dp[0] = 0;
    int mxSum = 0;
    int tmp;

    loop(i, n)
    {
        for(int j=0; j<=mxSum; j++)
        {
            if(dp[j] != 16843009 && dp[j]+1 <=k)
            {
                tmp = j + values[i];
                dp[tmp] = min(dp[tmp], dp[j] + 1);
                mxSum = max(mxSum, tmp);
            }
        }
    }

    int res;
    for(res=0; res<=mxSum; res++)
    {
        if(dp[res] == 16843009 )
        {
            break;
        }
    }
    res--;

    cout<<res<<endl;




}

(USACO) Score Inflation

0
Posted on by 
/*
ID: himuhas1
TASK: inflate
LANG: C++
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here
#define MAXX 10002
ll best[MAXX];

int main()
{
#ifndef henapc
    read("inflate.in");
    write("inflate.out");
#endif // henapc

    int given, cntGroups;
    int points, minitus;
    take(given, cntGroups);
    given++;

    loop(i, cntGroups)
    {
        take(points, minitus);
        FOR(i, minitus, given)
        {
            best[i] = max(best[i], best[i-minitus]+points);
        }
    }
    cout<<best[given-1]<<endl;


    return 0;
}

(USACO) Money Systems

0
Posted on by 
/*
ID: himuhas1
TASK: money
LANG: C++
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)

using namespace std;

#define MAXX 10002

ll dp[MAXX];

int main()
{
    #ifndef hasibpc
        freopen("money.in", "r", stdin);
        freopen("money.out", "w", stdout);
    #endif
    int V, N;
    int coin;
    mem(dp, 0);
    dp[0] = 1;
    cin>>V>>N;
    loop(i, V)
    {
        cin>>coin;
        loop(i, N)
        {
            if(i + coin > N)
                break;
            dp[i+coin] += dp[i];
            //cout<<(i+coin)<<endl;
        }

    }

    cout<<dp[N]<<endl;


    return 0;
}

(USACO) Longest Prefix

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?a=QX6ufTaKJ4D&S=prefix

/*
ID: himuhas1
TASK: prefix
LANG: C++
*/

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<stdio.h>

#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<utility>

#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define all(v) v.begin(), v.end()
#define pb push_back
#define sf scanf
#define pf printf
#define mem(a, v) memset(a, v, sizeof(a))
#define dd double
#define ll long long
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())

using namespace std;


#define NO_CHILD -2
#define NO_MAP -1

#define MAXX 200002

struct Trie{
    map<int, map<int, int> > childNode;
    vector<bool>allNodes;
    int id;
    int *p;
    int zero;


    Trie()
    {
        allNodes.pb(0);
        zero = 0;
    }


    void add(const string &val)
    {
        p = &zero;
        int ch;
        loop(i, SZ(val))
        {
            ch = val[i];
            p = &childNode[*p][ch];
            if(*p == 0)
            {
                *p = SZ(allNodes);
                allNodes.pb(0);
            }
        }

        allNodes[*p] = 1;
    }

    void iniCharByCharSearch()
    {
        id = 0;
    }

    int charByCharSearch(char ch)
    {
        if(childNode[id].find(ch) == childNode[id].end())
        {
            return NO_CHILD;
        }
        else
        {
            id = childNode[id][ch];
            return allNodes[id];
        }
    }
};






int main()
{
    #ifndef hasibpc
        freopen("prefix.in", "r", stdin);
        freopen("prefix.out", "w", stdout);
    #endif // hasibpc

    Trie tr;

    string name;
    string str;
    while(1)
    {
        cin>>name;
        if(name[0] == '.') break;

        tr.add(name);
    }

    while(cin>>name)
    {
        str += name;
    }

    bool dp[MAXX];
    mem(dp, 0);
    int ret;
    int result = 0;
    //dp[0] = 1;
    for(int i=-1; i<SZ(str); i++)
    {
        if(i==-1 || dp[i])
        {
            result = max(result, i+1);
            tr.iniCharByCharSearch();
            FOR(j, i+1, SZ(str))
            {
                ret = tr.charByCharSearch(str[j]);

                //pf("%d %d ==> %d\n", i, j, ret);

                if(ret == 1)
                {
                    //cout<<"j = "<< j<<endl;

                    dp[j] = 1;
                    //result = max(result, j+1);
                }


                if(ret == NO_CHILD)
                    break;

            }
        }
    }

    cout<<result<<endl;




    return 0;
}

(USACO) Subset Sums

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?S=subset&a=bcquvHYkCVC
/*
ID: himuhas1
TASK: subset
LANG: C++
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)

using namespace std;

#define MAXX 392

int main()
{
    //int p = 1512776590;
    //cout<<p<<endl;
    #ifndef hasibpc
        freopen("subset.in", "r", stdin);
        freopen("subset.out", "w", stdout);
    #endif
    int n;
    cin>>n;
    ll int dp[MAXX];
    mem(dp, 0);

    dp[0] = 1;


    int maxn = 0;
    int mid = (n*(n+1))>>1;
    if(mid%2 == 1)
    {
        cout<<0<<endl;
    }
    else
    {
        mid = mid>>1;
        for(int i=1; i<=n; i++)
        {
            for(int j=min(maxn, mid-i); j>-1; j--)
            {
                if(i+j < MAXX)
                dp[i+j] += dp[j];
            }
            maxn += i;
        }

        cout<<(dp[ mid ]>>1)<<endl;
        }



    return 0;
}

(UVa) 222 – Budget Travel

0
Posted on by 
/*
user: php
time: 0.012 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=158
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 10000000000
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 52 + 1

double final_dist;
double tank, miles_per_gallon;

double dist[MAXX];
double cost[MAXX];

double mincost[MAXX][MAXX];

int cnt;

double bfs_style()
{



    loop(i, cnt+1)
    {
        FOR(j, i, cnt+1)
        {
            mincost[i][j] = INF;
        }
    }

    mincost[0][0] = cost[0];



    for(int i=1; i<=cnt; i++)
    {
        double distance = dist[i];
        if(distance <= tank * miles_per_gallon)
        {
            mincost[0][i] = mincost[0][0];
        }


        loop(j, i)
        {
            distance = dist[i] - dist[j];
            if(2 * distance >= tank * miles_per_gallon || ( i < cnt && (dist[i+1] - dist[j])/miles_per_gallon > tank) )
                mincost[i][i] = min(mincost[i][i], mincost[j][i] + cost[i] * (distance/miles_per_gallon) );
        }



       // mincost[i][i] += (cost[i] * tank);

        if(mincost[i][i] >= INF) continue;

        mincost[i][i] += 200;


        for(int j=i+1; j<=cnt; j++)
        {
            distance = dist[j] - dist[i];

            if(distance <= tank * miles_per_gallon)
            {
                mincost[i][j] = mincost[i][i] ;
            }
        }
    }

    loop(i, cnt)
    {
        mincost[cnt][cnt] = min(mincost[cnt][cnt], mincost[i][cnt]);
    }

    return mincost[cnt][cnt];






}


int main()
{
    double result;
    int kaseno = 0;
    while(true)
    {
        cin>>final_dist;
        if(final_dist < 0) break;

        cin>>tank>>miles_per_gallon>>cost[0]>>cnt;
        cnt++;

        cost[0] = cost[0] * 100;
        dist[0] = 0;


        FOR(i, 1, cnt)
        {
            cin>>dist[i]>>cost[i];
        }

        dist[cnt] = final_dist;

        result = bfs_style() + 0.5;
        result = (ll) result;
        result /= 100.0;

        pf("Data Set #%d\nminimum cost = $%.2lf\n", ++kaseno, result);

    }

    return 0;
}

(UVa) 10032 – Tug of War

10
Posted on by 
/*
user: php
time: 0.216 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 45000+2

int cnt, totalsum, half;
ll dp[MAXX];
int weight[101];
ll bit;


int main()
{
    //read();
    bool blank = false;

    int kases;
    getint(kases);
    while(kases--)
    {
        getint(cnt);
        totalsum = 0;
        loop(i, cnt)
        {
            getint(weight[i]);
            totalsum += weight[i];
        }

        mem(dp, 0);
        dp[0] = 1<<0;

        loop(i, cnt)
        {
            for(int j=totalsum; j>-1; j--)
            {
                if(dp[j])
                {
                    dp[j + weight[i] ] |= (dp[j]<<1);
                }
            }
        }

        half = totalsum/2;
        bit = cnt/2;
        bit = 1LL<<bit;

        int aa;

        for(int i=half, j = half; i>-1 && j<=totalsum; i--, j++)
        {
            if((dp[i] & bit) )
            {
                aa = i;
                break;
            }

            if((dp[j] & bit))
            {
                aa = j;
                break;
            }
        }

        if(blank) pf("\n");
        blank = true;

        pf("%d %d\n", min(aa, totalsum-aa), max(aa, totalsum-aa));
    }

    return 0;
}

(UVa) 10036 – Divisibility

0
Posted on by 
/*
user: php
time: 0.080 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=977
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 101

bool dp[MAXX];
int cnt, k;



int main()
{
    int kases;
    getint(kases);
    int n;
    int it;
    vector<int>vv;
    int len;


    while(kases--)
    {
        mem(dp, 0);
        getint(cnt); getint(k);
        getint(n);
        dp[abs(n)%k] = 1;

        FOR(i, 1, cnt)
        {
            getint(n);
            vv.clear();
            loop(i, k)
            {
                if(dp[i])
                {
                    vv.pb(i);
                    dp[i] = 0;
                }
            }
            len = SZ(vv);

            loop(i, len)
            {
                dp[ (abs(vv[i] + n))%k ] = 1;
                dp[ (abs(vv[i] - n))%k ] = 1;

            }

        }



        if(dp[0])
        {
            pf("Divisible\n");
        }
        else
        {
            pf("Not divisible\n");
        }


    }

    return 0;
}

(UVa) 624 – CD

0
Posted on by 
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=565
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 10000

bool dp[MAXX];
int cdused[MAXX];
int tracklen[22];
int total;
int cnt;

int coinchange()
{
    mem(dp, 0);
    mem(cdused, 0);
    dp[0] = 1;
    int k;
    loop(i, cnt)
    {
        for(int j=total-1; j>-1; j--)
        {
            k = j + tracklen[i];
            if(dp[j] == true && dp[k] == false)
            {
                dp[k]  = true;
                cdused[k] = ((1<<i) | cdused[j]);
            }
        }
    }

    for(int i=total; i>-1; i--)
    {
        if(dp[i])
        {
            return i;
        }
    }


}




int main()
{
    int maxposs;

    while(sf("%d", &total) == 1)
    {
        getint(cnt);
        loop(i, cnt)
        {
            getint(tracklen[i]);
        }

        maxposs = coinchange();

        loop(i, cnt)
        {
            if( (cdused[maxposs] & 1<<i) )
            {
                pf("%d ", tracklen[i]);
            }
        }


        pf("sum:%d\n", maxposs);




    }



    return 0;
}