(LightOj) 1199 – Partitioning Game

Posted on May 9, 2016 by Hasib Al Muhaimin


/***********Template Starts Here***********/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <string>
#include <iostream>
#include <cctype>
#include <set>
#include <climits>
#include <iomanip>
#include <cassert>
//#include <unordered_map>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((int)(x).size())
#define NORM(x) if(x>=mod)x-=mod;

using namespace std;

typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

#ifdef forthright48
     #include <ctime>
     clock_t tStart = clock();
     #define debug(args...) {dbg,args; cerr<<endl;}
     #define timeStamp printf("Execution Time: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#else
    #define debug(args...)  // Just strip off all debug tokens
    #define timeStamp
#endif

struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
}dbg;

//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}

vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
    vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    *X = x2; *Y = y2;
    return r2;
}

inline vlong modInv ( vlong a, vlong m ) {
    vlong x, y;
    ext_gcd( a, m, &x, &y );
    if ( x < 0 ) x += m; //modInv is never negative
    return x;
}

inline vlong power ( vlong a, vlong p ) {
    vlong res = 1, x = a;
    while ( p ) {
        if ( p & 1 ) res = ( res * x );
        x = ( x * x ); p >>= 1;
    }
    return res;
}

inline vlong bigmod ( vlong a, vlong p, vlong m ) {
    vlong res = 1 % m, x = a % m;
    while ( p ) {
        if ( p & 1 ) res = ( res * x ) % m;
        x = ( x * x ) % m; p >>= 1;
    }
    return res;
}

/***********Template Ends Here***********/

/*********** Hasib Templates Starts Here**********/

#include<bits/stdc++.h>
using namespace std;

#define loop(i, n) for(int i=0; i<(n); i++)
#define sf scanf
#define pf printf
#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, val) memset(ara, val, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define vdump(x) cerr<<#x<<" = "<<x<<endl;
#define dump(args...) cerr,args; cerr<<endl

template<typename T>
ostream& operator<<(ostream& out, vector<T> v)
{
    out<<"[ ";

    loop(i, SZ(v))
    {
        if(i) out<<", ";
        out<<v[i];
    }

    out<<" ]";
    return out;
}

template<typename T1, typename T2>
ostream& operator<<(ostream &out, pair<T1, T2> p)
{
    out<<"( "<<p.fr<<", "<<p.sc<<")";
    return out;
}

template<typename T>
ostream& operator,(ostream &out, T x)
{
    out<<x<<" ";
    return out;
}


/**********Hasib Templates Ends Here**************/

/**
 *  WARTNING for me:
 *     Never use    FOR
 *     Never use    pii, pll, vi, vi
 *     Never use    ff, ss, phl, sp, nl
 */



#define MAXX 10007

int ara[107], N;


int g[10007];


void precalc()
{
        g[0] = g[1] = 0;

        int marked[MAXX];
        int x;

        mem(marked, 0);

        for(int i=2; i<MAXX; i++)
        {
                for(int j=1, k = i-1; j<k; j++, k--)
                {
                        x = g[j] ^ g[k];

                        marked[x] = i;
                }

                for(int j=0; j<MAXX; j++)
                {
                        if(marked[j] != i)
                        {
                                g[i] = j;
                                break;
                        }
                }
        }
}




void solve()
{
        int x = 0;

        loop(i, N)
        {
                x ^= g[ ara[i] ];
        }

        if(x == 0)
        {
                pf("Bob\n");
        }
        else
        {
                pf("Alice\n");
        }

}


int main ()
{
    #ifdef hasibpc
        //read("input.txt");
        //write("output.txt");
    #endif // hasibpc


    precalc();


    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
            sf("%d", &N);

            loop(i, N)
            {
                    sf("%d", &ara[i]);
            }

            pf("Case %d: ", ++kaseno);

            solve();

    }




    return 0;
}

(LightOj) 1126 – Building Twin Towers

Posted on November 26, 2015 by Hasib Al Muhaimin

The main idea is: dp[i][j] represent what is the maximum sum of two towers when the difference is j.


/***********Template Starts Here***********/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <functional>
#include <string>
#include <iostream>
#include <cctype>
#include <set>
#include <climits>
#include <iomanip>
#include <cassert>
//#include <unordered_map>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((int)(x).size())
#define NORM(x) if(x>=mod)x-=mod;

using namespace std;

typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

#ifdef forthright48
     #include <ctime>
     clock_t tStart = clock();
     #define debug(args...) {dbg,args; cerr<<endl;}
     #define timeStamp printf("Execution Time: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#else
    #define debug(args...)  // Just strip off all debug tokens
    #define timeStamp
#endif

struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
}dbg;

//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}

vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
    vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    *X = x2; *Y = y2;
    return r2;
}

inline vlong modInv ( vlong a, vlong m ) {
    vlong x, y;
    ext_gcd( a, m, &x, &y );
    if ( x < 0 ) x += m; //modInv is never negative
    return x;
}

inline vlong power ( vlong a, vlong p ) {
    vlong res = 1, x = a;
    while ( p ) {
        if ( p & 1 ) res = ( res * x );
        x = ( x * x ); p >>= 1;
    }
    return res;
}

inline vlong bigmod ( vlong a, vlong p, vlong m ) {
    vlong res = 1 % m, x = a % m;
    while ( p ) {
        if ( p & 1 ) res = ( res * x ) % m;
        x = ( x * x ) % m; p >>= 1;
    }
    return res;
}

/***********Template Ends Here***********/

/*********** Hasib Templates Starts Here**********/

#include<bits/stdc++.h>
using namespace std;

#define loop(i, n) for(int i=0; i<(n); i++)
#define sf scanf
#define pf printf
#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, val) memset(ara, val, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define vdump(x) cerr<<#x<<" = "<<x<<endl;
#define dump(args...) cerr,args; cerr<<endl

template<typename T>
ostream& operator<<(ostream& out, vector<T> v)
{
    out<<"[ ";

    loop(i, SZ(v))
    {
        if(i) out<<", ";
        out<<v[i];
    }

    out<<" ]";
    return out;
}

template<typename T1, typename T2>
ostream& operator<<(ostream &out, pair<T1, T2> p)
{
    out<<"( "<<p.fr<<", "<<p.sc<<")";
    return out;
}

template<typename T>
ostream& operator,(ostream &out, T x)
{
    out<<x<<" ";
    return out;
}


/**********Hasib Templates Ends Here**************/

/**
 *  WARTNING for me:
 *     Never use    FOR
 *     Never use    pii, pll, vi, vi
 *     Never use    ff, ss, phl, sp, nl
 */

 #define MAXX 57
 #define MAXSUM 500007

 int ara[MAXX];
 int N;

int dp[2][MAXSUM];

int solve()
{
    mem(dp, -1);

    dp[0][0] = 0;

    int now, pre;

    now = 1, pre = 0;


    loop(i, N)
    {
        loop(j, MAXSUM)
        {
            if(dp[pre][j] != -1)
            {
                dp[now][j] = max(dp[now][j], dp[pre][j]);

                int diff = abs(j - ara[i]);

                dp[now][diff] = max(dp[now][diff], max(dp[pre][diff], dp[pre][ j ] + ara[i] ));

                //pf("dp[%d] = %d\n", diff, dp[now][diff]);

                diff = j + ara[i];

                dp[now][diff] = max(dp[now][diff], max(dp[pre][diff], dp[pre][ j ] + ara[i] ));

                //pf("dp[%d] = %d\n", diff, dp[now][diff]);

            }
        }

        swap(now, pre);
    }

    return max(dp[now][0], dp[pre][0]);




}


int main ()
{
    #ifdef hasibpc
        read("input.txt");
        //write("output.txt");
    #endif // hasibpc


    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d", &N);
        loop(i, N)
        {
            sf("%d", &ara[i]);
        }


        sort(ara, ara+N); ///optimization 😀

        int ret = solve();

        if(ret != 0)
        {
            pf("Case %d: %d\n",++kaseno, ret/2);
        }
        else
        {
            pf("Case %d: impossible\n", ++kaseno);
        }


    }



    return 0;
}

(CodeForces) B. Symmetric and Transitive

Posted on August 11, 2015 by Hasib Al Muhaimin

comp[k] = How many ways a set of k elements can be written as a summation of few component.

Suppose S = {1, 2, 3}.
Here k = 3;

S = {1, 2, 3}
= {1, 2} + {3}
= {1, 3} + {2}
= {2, 3} + {1}
= {1} + {2} + {3}

So, comp[3] = 5.


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#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 take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



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;



//Header ends here





#define MAXX 4007
#define MOD 1000000007

#define POWMAX 7998007

int n;

ll nCr[MAXX][MAXX];

ll ara[MAXX][MAXX];

ll comp[MAXX];


void calc()
{
	ara[1][1] = 1;
	
	comp[0] = 1;
	comp[1] = 1;

	for(int i=2; i<MAXX; i++)
	{
		comp[i] = 1;

		ara[i][1] = 1;

		for(int j=2; j<=i; j++)
		{
			ara[i][j] = (ara[i-1][j-1]  + (j * ara[i-1][j])%MOD )%MOD;

			comp[i] =  (comp[i] + ara[i][j])%MOD;
		}
	}


}



int main()
{
	calc();

	nCr[1][0] = nCr[1][1] = 1;


	for(int i=2; i<MAXX; i++)
	{
		nCr[i][0] = 1;

		for(int j=1; j<=i; j++)
		{
			nCr[i][j] = (nCr[i-1][j] + nCr[i-1][j-1])%MOD;
		}
	}

	cin>>n;

	ll ret = 0;

	for(int i=0; i<n; i++)
	{
		ll tmp = nCr[n][i] * comp[i];
		ret = (ret + tmp%MOD)%MOD;
	}

	cout<<ret<<endl;


}

(UVA) 10347 – Medians

Posted on February 16, 2015 by Hasib Al Muhaimin


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#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 take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



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;



//Header ends here




void init()
{

}


int main()
{
    init();

    double u, v, w;

    while(cin>>u>>v>>w)
    {
        double tmp = 2*(u*u*v*v + v*v*w*w + w*w*u*u) - (u*u*u*u + v*v*v*v + w*w*w*w);
        if(tmp <= 0)
        {
            pf("-1.000\n");
        }
        else
        {
            double area = sqrt( tmp ) / 3.0;
            pf("%.3lf\n", area);
        }


    }



    return 0;
}

(LightOj) 1221 – Travel Company

Posted on January 20, 2015 by Hasib Al Muhaimin

Bellman Ford can’t find a cycle if it’s not reachable from starting node. So, Floyd-Warshall is much safer option!

Never use INFINITY. If you add something with INFINITY it will overflow.


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#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) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}


#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,(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;


//Header ends here

#define MAXX 107


int N, R, P;

ll dist[MAXX][MAXX];



int main()
{
    //read("input");
    int kases, kaseno=0;

    ll u, v, income, expense;

    cin>>kases;

    while(kases--)
    {
        cin>>N>> R>> P;


        loop(i, MAXX)
        {
            loop(j, MAXX)
            {
                dist[i][j] = (1<<29);
            }
            dist[i][i] = 0;
        }


        loop(i, R)
        {
            cin>>u>> v>> income>> expense;
            dist[u][v] = P*expense - income;
        }


        bool negetiveCycle = false;

        loop(k, N)
        {
            loop(i, N)
            {
                loop(j, N)
                {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        loop(i, N)
        {
            if(dist[i][i] < 0)
            {
                //dump(i);
                negetiveCycle = true;
                break;
            }
        }


        pf("Case %d: %s\n", ++kaseno, negetiveCycle?"YES":"NO");


    }



}

[/code]

(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) 1028 – Trailing Zeroes (I)

Posted on December 6, 2013 by Hasib Al Muhaimin

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

#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

bool isPrime[MAXX];
vector<int>primes;

void generate()
{
    primes.pb(2);
    mem(isPrime, 1);
    for(int i=3; i<1002; i+=2)
    {
        if(isPrime[i])
        {
            for(int j=i*i; j<MAXX; j+=i+i)
            {
                isPrime[j] = false;
            }
        }
    }
    for(int i=3; i<MAXX; i+=2)
    {
        if(isPrime[i])
        {
            primes.pb(i);
        }
    }
}

int main()
{
    generate();
    int kases, kaseno = 0;
    ll n;

    take(kases);
    ll cnt;
    ll gun;
    while(kases--)
    {
        take(n);
        cnt = 1;


        for(int i=0; i<SZ(primes) && primes[i]*primes[i]<=n; i++ )
        {
            gun = 1;
            while(n % primes[i] == 0)
            {
                gun++;
                n /= primes[i];
            }
            cnt = cnt*gun;
        }

        if(n != 1)
        {
            cnt *= 2;
        }

        pf("Case %d: %lld\n", ++kaseno, cnt-1);

    }


}

(LightOj) 1085 – All Possible Increasing Subsequences

Posted on December 6, 2013 by Hasib Al Muhaimin

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

#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 100003
#define MOD 1000000007

int seg[4*MAXX];
int get(int idx, int st, int ed, int i, int j)
{
    if(st == i && ed == j)
    {
        return seg[idx];
    }

    int l = idx<<1;
    int r = l + 1;
    int mid = (st+ed)/2;

    if(j <= mid)
    {
        return get(l, st, mid, i, j);
    }
    else if(mid < i)
    {
        return get(r, mid+1, ed, i, j);
    }
    else
    {
        return ( get(l, st, mid, i, mid) + get(r, mid+1, ed, mid+1, j) ) % MOD;
    }
}

void update(int idx, int st, int ed, int pos, int val)
{
    if(st == pos && pos == ed)
    {
        seg[idx] += val;
        seg[idx] %= MOD;
        return;
    }


    int mid = (st+ed)/2;
    int l = idx<<1;
    int r = l+1;

    if(pos <= mid)
    {
        update(l, st, mid, pos, val);
    }
    else
    {
        update(r, mid+1, ed, pos, val);
    }

    seg[idx] = (seg[l] + seg[r]) % MOD;

}


int main()
{
//    int k = 1000000007;
//    cout<<k;
    int kases, kaseno = 0;
    take(kases);
    int n;
    int ara[MAXX];



    while(kases--)
    {
        take(n);
        loop(i, n)
        {
            take(ara[i]);
        }
        set<int>idx(ara, ara+n);
        vector<int>v(all(idx));

        mem(seg, 0);
        int num;
        int low, high, mid;
        loop(i, n)
        {
            num = ara[i];
            low = 0;
            high = SZ(v)-1;

            while(low<=high)
            {
                mid = (low+high)/2;
                if(v[mid] < num)
                {
                    low = mid + 1;
                }
                else
                {
                    high = mid -1;
                }
            }

            //dump(low);
            //dump(SZ(v));



            if(low == 0)
            {
                update(1, 1, SZ(v), 1, 1);
            }
            else
            {
                int res = get(1, 1, SZ(v), 1, low) + 1;
                res %= MOD;
                //dump(res);
                update(1, 1, SZ(v), low +1, res);
            }

            /*

            FOR(j, 1, 4)
            {
                cout<<seg[j]<<"  ";
            }
            cout<<endl;

            dump(val[i]);
            */

            //cout<<endl<<endl;
        }
        pf("Case %d: %d\n", ++kaseno, seg[1]);


    }

}

Hello world!

Posted on October 21, 2012 by Hasib Al Muhaimin

Hello Coders!!!

Here I may post my UnLucky Codes which will Never Works!!! So Keep calm and Gangnam Style!!!

and The last thing, Y U NO comment??

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Category Archives: Uncategorized