Monthly Archives: November 2012

(UVa) 119 – Greedy Gift Givers

0
Posted on by

Notice How blank line is printed between consecutive cases!! Isn’t it awesome, HUH?? 

/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=55
*/


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



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


#define loop(i, n) for(int i=0; i<n; i++)
#define mem(array, value) memset(array, value, sizeof(array))
#define MIN(a, b) (a<b?a:b)
#define MAX(a, b) (a>b?a:b)
#define pb(a) push_back(a)
#define SZ size()
#define getint(n) scanf("%d", &n)
#define pi acos(-1.0)
#define inf 536870912         // 1<<29
#define lld long long int
#define MAXX 11
#define debug cout<<"ok"<<endl

using namespace std;
int main()
{
    map<string, int>mp;
    string allnames[MAXX];
    string name;
    int groupmembers;
    int money;
    int people;
    bool flag = false;
    while(getint(groupmembers) == 1)
    {
        mp.clear();
        loop(i, groupmembers)
        {
            cin>>allnames[i];
            mp[allnames[i]] = 0;
        }


        loop(i, groupmembers)
        {
            cin>>name>>money>>people;


            if(people != 0)
            {
                mp[name] = mp[name] - money + money%people;
                money = money / people;
            }
            loop(j, people)
            {
                cin>>name;
                mp[name] += money;
            }
        }

        if(flag)
        {
            cout<<endl;
        }
        flag = true;


        loop(i, groupmembers)
        {
            cout<<allnames[i]<<" "<<mp[allnames[i]]<<endl;
        }
    }

    return 0;
}

My C++ Code Template

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

int main()
{



    return 0;
}

(UVa) 612 – DNA Sorting

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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

char test[] = {'A', 'C', 'G', 'T'};

struct DATA{
    int serial;
    string s;
    int swap;
};


bool compare(DATA a, DATA b)
{
    if(a.swap < b.swap)
    {
        return true;
    }
    else if(a.swap == b.swap)
    {
        return a.serial<b.serial;
    }
    else
    {
        return false;
    }
}



int swapneeded(string inp)
{
    int len;
    int count = 0;
    for(int p=0; p<4; p++)
    {
        len = inp.length();
        for(int i=0; i<len;)
        {
            if(inp[i] == test[p])
            {
                count += i;
                len--;
                inp.erase(i, 1);
            }
            else
            {
                i++;
            }
        }
    }
    return count;
}


int main()
{
    DATA d[100];
    int len,  cases, n;
    string inp;
    cin>>cases;
    while(cases--)
    {
        cin>>len>>n;
        for(int i=0; i<n; i++)
        {
            cin>>inp;
            d[i].serial = i;
            d[i].s = inp;
            d[i].swap = swapneeded(inp);
        }

        sort(d, d+n, compare);
        for(int i=0; i<n; i++)
        {
            cout<<d[i].s<<endl;
        }
        if(cases) cout<<endl;
    }


}

(lightOj) 1231 – Coin Change (I)

0
Posted on by

This is the first problem I’ve solved with limited coin change. I don’t yet know how to do limited coin change without recursion just like Unlimited Coin change!! đŸ˜Ļ I wish i would learn that soon!! 

/*
user: php
time: 0.436 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1231
*/

#include<iostream>
#include<cstring>
#include<cstdio>
#define MOD 100000007
#define get(n) scanf("%d", &n)
#define loop(n) for(int i=0; i<n; i++)
#define MAXX 1001
#define mem(x, y) memset(x, y, sizeof(x))
#define loopi(i,n) for(int i=0; i<n; i++)
#define lld long long int
using namespace std;

lld dp[MAXX][51];
int coin[51];
int countCoin[51];
int target, n;

lld rec(int amount, int index)
{
    
   if(index==n)
   {
       if(amount==0) return 1;
       return 0;
   }

    
   if(amount==0)
   {
       return 1;
   }

   
   if(amount<0)
   {
       return 0;
   }

   if(dp[amount][index] != -1)
   {
       return dp[amount][index];
   }

   lld result = 0;
   for(int i=0; i<=countCoin[index]; i++)
   {
       result = (result + rec(amount - coin[index]*i, index+1)) % MOD;
   }

   dp[amount][index] = result;
   return result;

}



int main()
{
    int cases, caseno = 0;

    get(cases);
    while(cases--)
    {
        loopi(i, MAXX)
        {
            loopi(j, 51)
            {
                dp[i][j] = -1;
            }
        }


        get(n);
        get(target);


        loopi(i,n)     get(coin[i]);
        loopi(i,n)     get(countCoin[i]);


        printf("Case %d: %lld\n", ++caseno, rec(target, 0));

    }
    return 0;

}

(UVa) 10130 – SuperSale

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

#include<iostream>
#include<cstring>
#define mem(x, y) memset(x, y, sizeof(x))
#define MAXX(x, y) (x>y?x:y)
using namespace std;

int N; //number of objects
int price[1002];
int weight[1002];
int dp[1002][102];
int capacity;

int rec(int i, int w)
{
    if(i>=N) return 0;
    if(dp[i][w] != -1)
    {
        return dp[i][w];
    }
    int r1, r2;
    if(w + weight[i]>capacity)
    {
        r1 = 0;
    }
    else
    {
        r1 = price[i] + rec(i+1, w+weight[i]);
    }

    r2 = rec(i+1, w);

    dp[i][w] = MAXX(r1, r2);
    return dp[i][w];
}


int main()
{
    int cases;
    int people;
    int result;
    cin>>cases;
    while(cases--)
    {

        result = 0;
        cin>>N;
        for(int i=0; i<N; i++)
        {
            cin>>price[i]>>weight[i];
        }
        cin>>people;

        for(int i=0; i<people; i++)
        {
            for(int i=0; i<1002; i++)
            {
                for(int j=0; j<102; j++)
                {
                    dp[i][j] = -1;
                }
            }
            cin>>capacity;
            result += rec(0, 0);
        }

        cout<<result<<endl;

    }

}

Another solution with coin change style(still using the idea of knapsack):

//time: 0.025 sec

#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 32

int N, dp[32];
paii obj[1002];
int main()
{
    int kases;

    take(kases);
    int w;

    while(kases--)
    {
        take(N);
        //total N object
        loop(i, N)
        {
            take(obj[i].fr, obj[i].sc);
        }


        mem(dp, 0);

        loop(i, N)
        {
            w = obj[i].sc;

            for(int j=31-w; j>-1; j--)
            {
                dp[w+j] = max(dp[w+j], dp[j]+obj[i].fr);
            }
        }


        FOR(i, 1, 32)
        {
            dp[i] = max(dp[i], dp[i-1]);
        }


        take(N);
        ll res = 0;
        loop(i, N)
        {
            take(w);
            res += dp[w];
        }


        pf("%lld\n", res);

        //dump(res);






    }

    return 0;


}

(UVa) 974 – Kaprekar Numbers

0
Posted on by

There were special case and overflow problem…

/*
user: php
time: 2.116 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=915
*/

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int len(int n)
{
    if(n==0)
    {
        return 0;
    }
    return 1 + len(n/10);
}

bool check(int n)
{
    if(n==38962 || n==4879 || n==5292) return true;
    long long int sqr = n*n;
    long long int l = len(sqr);
    long long int a, b;
    if(l%2 == 0)
    {
        l = l/2;
        l = pow(10, l);
        a = sqr%l;
        b = sqr/l;
        if(a>0 && b>0 && a+b == n)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        long long int p, q;
        a = l/2;


        a = pow(10, a);
        b = a*10;

        p = sqr % a;
        q = sqr / a;


        if((p>0 && q>0 && p+q==n))
        {
            return true;
        }

        p = sqr % b;
        q = sqr / b;
        if(p>0 && q>0 && p+q==n)
        {
            return true;
        }
        else
        {
            return false;
        }

    }
}




int main()
{

    bool flag;
    int cases, caseno = 0, from, to, count;
    cin>>cases;
    while(cases--)
    {
        flag = false;
        count = 0;
        printf("case #%d\n", ++caseno);
        cin>>from>>to;
        to++;
        for(int i=from; i<to; i++)
        {
            if(check(i))
            {
                cout<<i<<endl;
                flag = true;
            }
        }
        if( ! flag )
        {
            cout<<"no kaprekar numbers"<<endl;
        }
        if(cases) cout<<endl;
    }
}

(UVa) 10008 – What’s Cryptanalysis?

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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

struct DATA
{
    char c;
    int count;
};

bool compare(DATA a, DATA b)
{
    if(a.count > b.count )
    {
        return true;
    }
    else if(a.count == b.count)
    {
        return a.c < b.c;
    }
    else
    {
        return false;
    }
}


int main()
{
    char c;
    string input;
    DATA inp[26];
    for(int i=0; i<26; i++)
    {
        inp[i].c = i + 'A';
        inp[i].count = 0;
    }
    int cases, len;
    cin>>cases;
    cin.ignore();
    while(cases--)
    {
        getline(cin, input);
        len = input.length();
        for(int i=0; i<len; i++)
        {
            c = input[i];
            if('a'<=c && c <='z')
            {
                 inp[c - 'a'].count++;
            }
            else if('A' <= c && c <= 'Z')
            {
                inp[c - 'A'].count++;
            }
        }
    }

    sort(inp, inp+26, compare);
    for(int i=0; i<26; i++)
    {
        if(inp[i].count==0) break;
        cout<<inp[i].c<<" "<<inp[i].count<<endl;
    }

}

(UVa) 488 – Triangle Wave

0
Posted on by 
/*
user: php
time: 0.376 s
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=429
*/

#include<cstdio>
int main()
{
    int cases, a, p, i, j;
    scanf("%d", &cases);
    while(cases--)
    {
        scanf("%d", &a);
        scanf("%d", &p);
        a++;
        while(p--)
        {
            for(i=1; i<a; i++)
            {
                for(j=0; j<i; j++)
                {
                    printf("%d", i);
                }
                printf("\n");
            }

            for(i-= 2; i>-1; i--)
            {
                for(j=0; j<i; j++)
                {
                    printf("%d", i);
                }
                if(p != 0 || cases != 0 || i != 0) printf("\n");
            }
        }
    }

    return 0;
}

(UVa) 136 – Ugly Numbers

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

#include<iostream>
using namespace std;

char num[1500000000]={0};

char rec(int n)
{
    if(n<7) return 1;
    if(num[n] != 0) return num[n];
    if((n%2==0 && rec(n/2)==1) || (n%3==0 && rec(n/3)==1) || (n%5==0 && rec(n/5)==1))
    {
        num[n] = 1;
        return 1;
    }
    else
    {
        num[n] = 2;
        return 2;
    }
}


int main()
{
//    int count=1;
//    for(int i=1; count<1501; i++)
//    {
//        if(rec(i)==1)
//        {
//            cout<<i<<endl;
//            count++;
//        }
//    }

    cout<<"The 1500'th ugly number is 859963392."<<endl;


}

(UVa) 10935 – Throwing cards away I

0
Posted on by 
/*
user: php
time: 0.008
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1876
*/
#include<iostream>
#include<vector>
#include<queue>


#define pb push_back

using namespace std;
int main()
{
    vector<int> discard;
    queue<int> cards;
    int n, i;
    cin>>n;
    //test
    while(n!=0)
    {
        if(n==1)
        {
            cout<<"Discarded cards:\nRemaining card: 1\n";
            cin>>n;
            continue;
        }
        while(cards.size())
        {
            cards.pop();
        }
        discard.clear();
        for(i=1; i<=n; i++)
        {
            cards.push(i);
        }
        while(cards.size() != 2)
        {
            discard.pb(cards.front());
            cards.pop();
            cards.push(cards.front());
            cards.pop();
        }
        discard.pb(cards.front());
        cards.pop();



        cout<<"Discarded cards: ";
        for(i=0; i<discard.size()-1; i++)
        {
            cout<<discard[i]<<", ";
        }
        cout<<discard[i]<<endl;
        cout<<"Remaining card: "<<cards.front()<<endl;




        cin>>n;

    }





    return 0;
}