(Spoj) 6256. Inversion Count (INVCNT)

Posted on December 31, 2013 by Hasib Al Muhaimin


#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 10000002
#define lowBit(x) (x & -(x))


int tree[MAXX];


void update(int pos, int val)
{
    while(pos<= MAXX)
    {
        tree[pos] += val;
        pos = pos + lowBit(pos);
    }
}

ll get(int pos)
{
    ll sum = 0;
    while(pos>0)
    {
        sum += tree[pos];
        pos -= lowBit(pos);
    }
    return sum;
}


int main()
{
    int ara[200000+2];
    int kases;

    take(kases);

    int n;

    while(kases--)
    {
        mem(tree, 0);
        ll res = 0;
        take(n);

        loop(i, n)
        {
            take(ara[i]);
        }

        for(int i=n-1; i>-1; i--)
        {
            update(ara[i], 1);
            res += get(ara[i]-1);
        }

        cout<<res<<endl;


    }


}

(LightOj) 1145 – Dice (I)

Posted on December 29, 2013 by Hasib Al Muhaimin

//link: http://lightoj.com/volume_showproblem.php?problem=1145

#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 15002
#define MOD (100000007)

int dp[2][MAXX];
int N, K, S;

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

    take(kases);

    while(kases--)
    {
        take(N, K, S);
        int now = 0, previous = 1;
        mem(dp, 0);
        dp[0][0] = 1;

        loop(fao, N)
        {
            swap(now, previous);

            dp[now][0] = 0;
            for(int i=1; i<=S; i++)
            {
                dp[now][i] = (dp[now][i-1] + dp[previous][i-1] - ( i-K-1<0?0:dp[previous][i-K-1] ) ) %MOD;
                //dump(dp[now][i]);
                //testing

                //if(dp[now][i] < 0) break;



            }


        }

        pf("Case %d: %d\n", ++kaseno, (dp[now][S]+MOD)%MOD);
    }

    return 0;


}

(LightOj) 1122 – Digit Count

Posted on December 17, 2013 by Hasib Al Muhaimin


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

int m, n;

vector<int>graph[MAXX];

vector<int>st;

ll dp[MAXX][MAXX];


ll rec(int toUse, int lastUsedInteger)
{
    if(toUse == n) return 1;

    ll &ret = dp[toUse][lastUsedInteger];

    if(ret != -1) return ret;

    ret = 0;
    toUse++;
    loop(i, SZ(graph[lastUsedInteger]))
    {
        ret += rec(toUse, graph[lastUsedInteger][i] );
    }

    return ret;
}



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

    while(kases--)
    {
        take(m, n);
        loop(i, MAXX) graph[i].clear();
        st.clear();
        st.resize(m);


        loop(i, m)
        {
            take(st[i]);
        }

        sort(all(st));



        {
            int mm;
            loop(i, SZ(st))
            {
                graph[ st[i] ].pb(st[i]);

                mm = min(i+3, SZ(st));

                for(int j=i+1; j<mm; j++)
                {
                    if( st[j] - st[i]  < 3 )
                    {
                        graph[ st[i] ].pb( st[j] );
                        graph[ st[j] ].pb( st[i] );
                    }
                }

            }
        }


        /*
        {//debug
            loop(i, SZ(st))
            {
                debug(graph[st[i]]);
            }

        }

        */




        mem(dp, -1);

        ll res = 0;

        loop(i, m)
        {
            res += rec(1, st[i]);
        }


        pf("Case %d: %lld\n", ++kaseno, res);





    }

    return 0;

}

(LightOj) 1102 – Problem Makes Problem

Posted on December 15, 2013 by Hasib Al Muhaimin


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

#define MOD (1000000007)
#define int32 ll

int32 fac[MAXX];



int32 BigMod(int32 a, int32 p)
{
    if(p==0) return 1;

    int32 half = p/2;
    int32 res;

    res = BigMod(a, half);
    res = (res*res)%MOD;

    if((p&1) != 0 )
    {//bijor
        res = (res*a)%MOD;
    }

    //cerr<<a<<"^"<<p<<" = "<<res<<endl;


    return res;
}


int main()
{

    //cerr<<BigMod(2, 10000);
    fac[0] = 1;
    FOR(i, 1, MAXX) fac[i] = (fac[i-1]*i)%MOD;

    int kases, kaseno=0;
    int32 n, k;

    take(kases);

    while(kases--)
    {
        take(n, k);
        k--;

        //cerr<<n<<"    "<<k<<endl;

        int32 result = (fac[k] *fac[n])%MOD;

        result = BigMod(result, MOD-2);

        result = (result*fac[n+k])%MOD;

        //cerr<<result<<endl;

        pf("Case %d: %lld\n", ++kaseno, result);

    }

    return 0;


}

(LightOj) 1090 – Trailing Zeroes (II)

Posted on December 15, 2013 by Hasib Al Muhaimin


#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
ll n, r, p, q;


ll count(ll N, ll K)
{
    ll res;
    ll gun = 1;
    ll cnt = 0;
    do{
        gun *= K;
        res = N / gun;
        //dump(res);
        cnt+= res;

    }while(res);

    return cnt;
}


ll countDivisor(ll N, ll a)
{
    ll cnt = 0;
    while(N%a == 0)
    {
        cnt++;
        N /= a;
    }
    return cnt;
}





int main()
{
    /*
    dump(count(1000000, 2));
    dump(count(500000, 2)*2);
    dump(count(1000000, 5));
    dump(count(500000, 5));
    */
    int kases, kaseno = 0;

    take(kases);

    while(kases--)
    {
        take(n, r, p, q);

        ll res = min( countDivisor(p, 5)*q + count(n, 5) - count(r, 5) - count(n-r, 5), countDivisor(p,2)*q + count(n, 2) - count(r, 2) - count(n-r, 2)  );

        pf("Case %d: %lld\n", ++kaseno, res);
    }

    return 0;


}

(LightOj) 1067 – Combinations

Posted on December 14, 2013 by Hasib Al Muhaimin


#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 1000002
#define MOD 1000003


ll fac[MAXX];


ll BigMod(ll a, int p)
{
    if(p == 0)
    {
        return 1;
    }

    int half = p/2;

    ll res = BigMod(a, half);
    res = (res*res) % MOD;
    if((p & 1) > 0)
    {
        res = (res*a)%MOD;
    }
    //cerr<<a<<"^"<<p<<" = "<<res<<endl;
    return res;
}

int main()
{
    //cerr<<(BigMod(2, 1024));
    fac[0] = 1;

    FOR(i, 1, 1000001)
    {
        fac[i] = (fac[i-1]*i)%MOD;
    }

    int kases, kaseno = 0;
    int n, r;
    take(kases);

    while(kases--)
    {
        take(n, r);
        ll nice = (fac[r] * fac[n-r])% MOD;
        nice = BigMod(nice, MOD-2);

        ll res = (fac[n]*nice)%MOD;

        pf("Case %d: %lld\n", ++kaseno, res);

    }
    return 0;


}

(LightOj) 1064 – Throwing Dice

Posted on December 10, 2013 by Hasib Al Muhaimin


#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);



    }


}

(LightOj) 1281 – New Traffic System

Posted on December 10, 2013 by Hasib Al Muhaimin


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

struct graphNode{
    int weight;
    int v;
    bool isProposedRoad;
};
struct node{
    int cost;
    int used;
    int u;

    bool operator<(const node &ob) const
    {
        return this->cost > ob.cost;
    }
};



vector<graphNode>graph[MAXX];
int n, m, k, d;
int dist[11][MAXX];



int dijkstra()
{
    //cerr<<endl;
    node u, v;
    u.u = u.cost = u.used = 0;

    mem(dist, 1);
    dist[0][0] = 0;


    priority_queue<node>Q;
    Q.push(u);


    while(!Q.empty())
    {
        u = Q.top(); Q.pop();
        //cerr<<"dist["<<u.u<<"]["<<u.used<<"] = "<<u.cost<<endl;
        if(u.cost != dist[u.used][u.u]) continue;
        if(u.u == n-1)
        {
            //dump(u.cost);
            return u.cost;
        }

        loop(i, SZ(graph[u.u]))
        {
            //cerr<<u.u<<" -->"<<graph[u.u][i].v<<endl;
            v.u = graph[u.u][i].v;
            v.cost = graph[u.u][i].weight + u.cost;
            v.used = u.used + (graph[u.u][i].isProposedRoad?1:0);


            if(v.used <= d && v.cost < dist[v.used][v.u] )
            {
                dist[v.used][v.u] = v.cost;
                Q.push(v);
                //cerr<<"pushing "<<v.u<<" with cost "<<v.cost<<endl;
            }
        }
    }

    return -1;
}




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

    take(kases);

    while(kases--)
    {



        graphNode aNode;
        take(n, m, k, d);


        loop(i, n) graph[i].clear();

        int u, v, w;
        aNode.isProposedRoad = false;
        loop(i, m)
        {
            take(u, v, w);
            aNode.weight = w;
            aNode.v = v;
            graph[u].pb(aNode);
        }

        aNode.isProposedRoad = true;

        loop(i, k)
        {
            take(u, v, w);
            aNode.weight = w;
            aNode.v = v;
            graph[u].pb(aNode);
        }

        int res = dijkstra();
        if(res == -1) pf("Case %d: Impossible\n", ++kaseno);
        else pf("Case %d: %d\n", ++kaseno, res);


    }



}

(LightOj) 1043 – Triangle Partitioning

Posted on December 9, 2013 by Hasib Al Muhaimin


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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#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 paii pair<int, int>
#define pall pair<ll, ll>
#define PI acos(-1.0)
#define INF (1<<29)
#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



struct ASDF{

    ASDF& operator,(int &a)
    {
        sf("%d", &a);
        return *this;
    }

    ASDF& operator,(long int &a)
    {
        sf("%ld", &a);
        return *this;
    }

    ASDF& operator,(ll &a)
    {
        sf("%lld", &a);
        return *this;
    }

    ASDF& operator,(char &c)
    {
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(dd &d)
    {
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a)
    {
        cin>>a;
        return *this;
    }
}asdf;




int main()
{
    dd a, b, r;
    int kases, kaseno = 0;

    take(kases);

    while(kases--)
    {
        take(b, r, r,r);
        a = ((b*b*r)/ (1+r));
        a = sqrt(a);
        pf("Case %d: %.10lf\n", ++kaseno, a);
    }

}

(LightOj) 1033 – Generating Palindromes

Posted on December 7, 2013 by Hasib Al Muhaimin

//link: http://lightoj.com/volume_showproblem.php?problem=1033

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

char str[MAXX];

int dp[MAXX][MAXX];
int len;


int min_cost(int i, int j)
{
    if(i < 0) return len - j;
    if(j >= len) return i+1;

    int &ret = dp[i][j];
    if(ret != -1) return ret;


    if(str[i] == str[j])
    {
        return ret = min_cost(i-1, j+1);
    }
    else
    {
        return ret = 1 + min( min_cost(i-1, j), min_cost(i, j+1) );
    }

}



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



    while(kases--)
    {
        scanf("%s", str);
        len = strlen(str);
        mem(dp, -1);
        int res = 1<<29;
        for(int i=0; i<len-1; i++)
        {
            res = min( res, min_cost(i, i) );
            res = min(res, min_cost(i, i+1));
        }
        pf("Case %d: %d\n", ++kaseno, len==1?0:res);
    }

}

Another solution using LCS directly


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

char str[MAXX];

int dp[MAXX][MAXX];
int len;

int LCS(int i, int j)
{
    if(i<0 || j>=len) return 0;
    int &ret = dp[i][j];
    if(ret != -1) return ret;

    if(str[i] == str[j]) return ret = 1 + LCS(i-1, j+1);
    return ret = max(LCS(i-1, j), LCS(i, j+1));
}




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



    while(kases--)
    {
        scanf("%s", str);
        len = strlen(str);
        mem(dp, -1);
        int res = 1<<29;
        for(int i=0; i<len-1; i++)
        {
            res = min(res, len+1 - 2*LCS(i, i));
            res = min(res, len - 2*LCS(i, i+1));
        }

        pf("Case %d: %d\n", ++kaseno, len==1?0:res);
    }

}

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Monthly Archives: December 2013

(Spoj) 6256. Inversion Count (INVCNT)

(LightOj) 1145 – Dice (I)

(LightOj) 1122 – Digit Count

(LightOj) 1102 – Problem Makes Problem

(LightOj) 1090 – Trailing Zeroes (II)

(LightOj) 1067 – Combinations

(LightOj) 1064 – Throwing Dice

(LightOj) 1281 – New Traffic System

(LightOj) 1043 – Triangle Partitioning

(LightOj) 1033 – Generating Palindromes