(LightOj) 1141 – Number Transformation

Posted on March 30, 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



#define MAXX 1007

vector<int>factors[MAXX];

vector<int>primes;

void generatePrimes()
{
    bool isPrime[MAXX];

    mem(isPrime, 1);

    int root = sqrt(MAXX) + 7;

    for(int i=3; i<root; i++)
    {
        if(isPrime[i])
        {
            for(int j=i*i; j<MAXX; j+=(2*i))
            {
                isPrime[j] = false;
            }
        }
    }

    for(int i=2; i<MAXX;)
    {
        if(isPrime[i])
        {
            for(int j=2; i*j < MAXX; j++)
            {
                factors[i*j].pb(i);
            }
        }

        if(i == 2)
        {
            i++;
        }
        else
        {
            i += 2;
        }
    }
}


void init()
{
    generatePrimes();
}




int bfs(int source, int target)
{
    bool visited[MAXX];

    int dist[MAXX];

    mem(dist, -1);

    mem(visited, 0);


    queue<int>Q;

    Q.push(source);

    visited = true;
    dist = 0;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(factors[u]))
        {
            int v = u + factors[u][i];

            if( (v <= target) && !visited[v] )
            {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                if(v == target)
                {
                    break;
                }
                Q.push(v);
            }
        }
    }

    return dist[target];
}


int main()
{
    init();


    int kases, kaseno = 0;

    int s, t;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d %d", &s, &t);
        pf("Case %d: %d\n", ++kaseno, bfs(s, t));
    }

    return 0;
}

(LighOj) 1307 – Counting Triangles

Posted on March 22, 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

#define MAXX 2007


int N;
ll ara[MAXX];



ll solve()
{
    ll cnt = 0;

    sort(ara, ara+N);

    for(int i=N-1; i>-1; i--)
    {
        for(int j=i-1; j>-1; j--)
        {
            int low = 0, high = j - 1, mid;

            while(low <= high)
            {
                mid = (low+high)/2;

                if( ara[mid] + ara[j] > ara[i] )
                {
                    //possible
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }

            cnt += (j - low);


        }
    }

    return cnt;


}



void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    sf("%d", &kases);

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

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

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



    return 0;
}

(LightOj) 1154 – Penguins

Posted on March 22, 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

#define MAXX 208

#define INF (1<<29)





int capacity[MAXX][MAXX], tmpCapacity[MAXX][MAXX];
int N;
double D;
pair<double, double>points[MAXX/2];
vector<int>graph[MAXX];
int source, sink;
int total;

double sq(double x)
{
    return x*x;
}

double dist(pair<double, double>A, pair<double, double>B)
{
    return sqrt( sq(A.fr - B.fr) + sq(A.sc - B.sc) );
}


int findPath()
{
    bool visited[MAXX];

    bool found = false;

    int parent[MAXX];

    mem(parent, -1);
    mem(visited, 0);

    queue<int>Q;

    Q.push(source);
    visited = true;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];

            if(!visited[v] && tmpCapacity[u][v] > 0)
            {
                visited[v] = true;
                parent[v] = u;
                Q.push(v);

                if(v == sink)
                {
                    found = true;
                    break;
                }
            }
        }

        if(found)
        {
            break;
        }
    }

    int pathCapacity = INF;
    int u, v = sink;

    while(parent[v] != -1)
    {
        u = parent[v];

        pathCapacity = min(pathCapacity, tmpCapacity[u][v]);

        v = u;

    }


    v = sink;

    while(parent[v] != -1)
    {
        u = parent[v];

        tmpCapacity[u][v] -= pathCapacity;
        tmpCapacity[v][u] += pathCapacity;

        v = u;
    }

    return found?pathCapacity:0;
}






int FLOW()
{
    loop(i, MAXX)
    {
        loop(j, MAXX)
        {
            tmpCapacity[i][j] = capacity[i][j];
        }
    }

    int ret = 0;

    int pathCapacity;

    while(pathCapacity = findPath())
    {
        ret += pathCapacity;
    }
    return ret;
}





void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    int n, c;

    int u, v;

    sf("%d", &kases);

    while(kases--)
    {

        mem(capacity, 0);
        loop(i, MAXX) graph[i].clear();
        total = 0;

        sf("%d %lf", &N, &D);


        source = 0;


        for(int i=1; i<=N; i++)
        {
            sf("%lf %lf %d %d", &points[i].fr, &points[i].sc, &n, &c);

            total += n;

            v = 2*i;
            u = v - 1;


            graph[u].pb(v);
            graph[v].pb(u);

            capacity[u][v] = c;

            graph.pb(u);
            graph[u].pb(source);

            capacity[u] = n;
        }


        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(i == j) continue;

                if(dist(points[i], points[j]) <= D)
                {
                    u = 2*i;
                    v = 2*j - 1;

                    capacity[u][v] = INF;

                    graph[u].pb(v);
                    graph[v].pb(u);
                }
            }
        }


        vector<int>vv;
        for(int i=1; i<=N; i++)
        {
            sink = 2*i - 1;

            if(FLOW() == total)
            {
                vv.pb(i);
            }
        }

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

        if(SZ(vv) == 0)
        {
            printf(" -1");
        }
        else
        {
            loop(i, SZ(vv))
            {
                printf(" %d", vv[i] - 1);
            }
        }

        pf("\n");











    }



    return 0;
}

(LightOj) 1155 – Power Transmission

Posted on March 20, 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

#define MAXX 207

#define INF (1<<29)

int source, sink;

int N;
int M;

int capacity[MAXX][MAXX];

vector<int>graph[MAXX];

int findPath()
{
    bool visited[MAXX];

    int parent[MAXX];

    mem(parent, -1);

    mem(visited, 0);

    queue<int>Q;

    Q.push(source);

    visited = true;

    bool found = false;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];

            if(!visited[v] && capacity[u][v] > 0)
            {
                visited[v] = true;
                Q.push(v);

                parent[v] = u;

                if(v == sink)
                {
                    found = true;
                    break;
                }
            }
        }

        if(found)
        {
            break;
        }
    }



    int v = sink;

    int pathCapacity = INF;

    while(parent[v] != -1)
    {
        int u = parent[v];
        pathCapacity = min(pathCapacity, capacity[u][v] );

        v = u;
    }

    v = sink;

    while(parent[v] != -1)
    {
        int u = parent[v];

        capacity[u][v] -= pathCapacity;
        capacity[v][u] += pathCapacity;

        v = u;
    }

    if(found)
    {
        return pathCapacity;
    }
    else
    {
        return 0;
    }

}





int FLOW()
{
    int result = 0;

    int pathCapacity;

    while(true)
    {
        pathCapacity = findPath();

        if(pathCapacity == 0)
        {
            break;
        }
        else
        {
            result += pathCapacity;
        }
    }

    return result;
}





int solve()
{
    return FLOW();
}






void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    int B, D;

    int u, v, c;

    sf("%d", &kases);

    while(kases--)
    {
        mem(capacity, 0);


        sf("%d", &N);

        source = 0;

        sink = 2*(N + 1); // A number out of the range of node id.

        for(int i=0; i<=sink; i++)
        {
            graph[i].clear();
        }


        for(int i=1; i<=N; i++)
        {
            u = 2*i - 1;
            v = u + 1;

            graph[u].pb(v);
            graph[v].pb(u);

            sf("%d", &capacity[u][v]);
        }

        sf("%d", &M);

        loop(i, M)
        {
            sf("%d %d %d", &u, &v, &c);

            u = 2*u;
            v = 2*v - 1;

            graph[u].pb(v);
            graph[v].pb(u);

            capacity[u][v] = c;
        }

        sf("%d %d", &B, &D);

        loop(i, B)
        {
            sf("%d", &u);
            u = 2*u  - 1;

            graph.pb(u);
            graph[u].pb(source);

            capacity[ source ][u] = INF;
        }

        loop(i, D)
        {
            sf("%d", &v);
            {
                v = 2*v;

                graph[v].pb(sink);
                graph[sink].pb(v);

                capacity[v][sink] = INF;

            }
        }

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

    }



    return 0;
}

(LightOj) 1153 – Internet Bandwidth

Posted on March 18, 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

#define MAXX 107
#define INF (1<<29)



int capacity[MAXX][MAXX];

int parent[MAXX];

vector<int>graph[MAXX];

int source, sink, N, m;


int findPath()    // BFS
{
    bool visited[MAXX];

    mem(visited, 0);

    queue<int>Q;

    Q.push(source);

    visited = true;

    mem(parent, -1);

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];

            if(!visited[v] && capacity[u][v] > 0)
            {
                Q.push(v);
                visited[v] = true;
                parent[v] = u;

                if(v == sink)
                {
                    break;
                }
            }
        }
    }


    int v = sink, path_capacity = INF;

    while(parent[v] != -1)
    {
        int u = parent[v];

        path_capacity = min(path_capacity, capacity[u][v] );

        v = u;
    }




    v = sink;

    while(parent[v] != -1)
    {
        int u = parent[v];

        capacity[u][v] -= path_capacity;

        capacity[v][u] += path_capacity;

        v = u;
    }

    if(path_capacity == INF)
        return 0;
    else
        return path_capacity;
}




int FLOW()
{
    int result = 0;

    while(true)
    {
        int pathCapacity = findPath();

        if(pathCapacity == 0)
        {
            break;
        }
        else
        {
            result += pathCapacity;
        }
    }

    return result;
}



int solve()
{
    return FLOW();
}



void init()
{

}


int main()
{
    init();


    int kases, kaseno = 0;

    int u, v, c;

    sf("%d", &kases);

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

        for(int i=0; i<=N; i++)
        {
            graph[i].clear();
        }

        mem(capacity, 0);

        loop(i, m)
        {
            sf("%d %d %d", &u, &v, &c);

            graph[u].pb(v);

            graph[v].pb(u);

            capacity[u][v] = capacity[v][u] = capacity[u][v] + c;
        }

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

    }



    return 0;
}

(LightOj) 1129 – Consistency Checker

Posted on March 14, 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


int N;
string str;

bool isPossible;

struct DATA {
    bool endHere;
    bool hasTrace;
    DATA *child[10];

    DATA()
    {
        endHere = false;
        hasTrace = false;
        loop(i, 10) child[i] = NULL;
    }
    ~DATA()
    {
        loop(i, 10)
        {
            if(child[i] != NULL)
                delete child[i];
        }
    }
};

void addString(string &str, DATA *curNode)
{
    if(!isPossible) return;

    loop(i, SZ(str))
    {
        curNode->hasTrace = true;

        str[i] = str[i] - '0';
        if(curNode->child[ str[i] ] == NULL)
            curNode->child[ str[i] ] = new DATA();
        curNode = curNode->child[ str[i] ];


        if(curNode->endHere)
        {
            isPossible = false;
            return;
        }
    }

    if(curNode->hasTrace)
        isPossible = false;

    curNode->endHere = true;
}



void init()
{

}




int main()
{


    init();

    int kases, kaseno = 0;

    sf("%d", &kases);

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

        DATA *head = new DATA();

        isPossible = true;

        loop(i, N)
        {
            cin>>str;
            addString(str, head);
            //dump(head);
        }

        delete head;
        if(isPossible)
        {
            pf("Case %d: YES\n", ++kaseno);
        }
        else
        {
            pf("Case %d: NO\n", ++kaseno);
        }
    }



    return 0;
}

(LightOj) 1334 – Genes in DNA

Posted on March 14, 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

#define MAXX 50007






void calculatePrefixFunction(string &pattern, int pi[], int occur[])
{
    int m = SZ(pattern);
    pi[0] = -1;
    int k = -1;

    occur[0] = 1;

    for(int i=1; i<m; i++)
    {
        while(k > -1 && pattern[k+1] != pattern[i])
            k = pi[k];
        if(pattern[k+1] == pattern[i])
            k++;
        pi[i] = k;

        occur[i] = 1;

        if(k > -1)
            occur[i] += occur[k];
    }
}



void KMP(string &str, string &pattern, int pi[], int occur[], int dp[])
{
    int n = SZ(str);
    int m = SZ(pattern);

    int q = -1;
    loop(i, n)
    {
        while(q>-1 && pattern[q+1] != str[i])
            q = pi[q];
        if(pattern[q+1] == str[i])
            q++;
        if(q == m-1)
            q = pi[q];

        //as the problem says proper
        dp[i] = occur[q];

    }
}







ll solve()
{
    string str, pattern;
    int pi[MAXX];
    int occur[MAXX];

    string revStr, revPattern;
    int revPi[MAXX];
    int revOccur[MAXX];


    cin>>str>>pattern;

    revStr = str;
    revPattern = pattern;

    reverse(all(revStr));
    reverse(all(revPattern));

    calculatePrefixFunction(pattern, pi, occur);
    calculatePrefixFunction(revPattern, revPi, revOccur);

    int dp[2][MAXX];

    KMP(str, pattern, pi, occur, dp[0]);
    KMP(revStr, revPattern, revPi, revOccur, dp[1]);

    //dump(dp[0][9]);
    //dump(dp[1][3]);

    ll res = 0;

    for(int i=0, j=SZ(str)-2; j>-1; i++, j--)
    {
        res += (ll)dp[0][i]*(ll)dp[1][j];
        //pf("[%d] = %lld\n",i, dp[0][i]*dp[1][j]);
    }

    return res;

}




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

    sf("%d", &kases);

    while(kases--)
    {
        pf("Case %d: %lld\n", ++kaseno, solve());
    }



    return 0;
}

(UVa) 10069 – Distinct Subsequences

Posted on March 11, 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




struct BigInteger {
    string num;

    BigInteger operator+(BigInteger other)
    {
        BigInteger ret;

        int maxLen = max( SZ(num), SZ(other.num) );

        int hate = 0;

        loop(i, maxLen)
        {
            int sum = (i<SZ(num)?num[i] : 0) + (i<SZ(other.num) ? other.num[i]:0) + hate;
            ret.num.push_back(sum%10);
            hate = sum/10;
        }
        while(hate != 0)
        {
            ret.num.push_back(hate%10);
            hate /= 10;
        }
        return ret;
    }


    void operator+=(BigInteger other)
    {
        num = (*this + other).num;
    }

};


#define MAXX 10107




string str, pattern;

BigInteger dp[MAXX][107];
bool visited[MAXX][107];



BigInteger rec(int i, int j)
{
    //dump(i);
    //dump(j);
    BigInteger &ret = dp[i][j];

    if( visited[i][j] ) return ret;

    visited[i][j] = true;

    ret.num.clear();

    if(j >= SZ(pattern))
    {
        ret.num.pb(1);
        return ret;
    }
    else if(i >= SZ(str))
    {

        ret.num.pb(0);
        return ret;
    }
    else
    {

        ret = rec(i+1, j);

        if(str[i] == pattern[j])
        {
            ret = ret+ rec(i+1, j+1);
        }

        return ret;
    }

}



void solve()
{
    mem(visited, 0);
    string res = rec(0, 0).num;
    reverse(all(res));
    loop(i, SZ(res))
    {
        res[i] = res[i] + '0';
    }

    cout<<res<<endl;

}



void init()
{

}


int main()
{
    init();

    int kases;

    take(kases);

    while(kases--)
    {
        cin>>str>>pattern;

        solve();
    }



    return 0;
}

(UVa) 572 – Oil Deposits

Posted on March 11, 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



#define MAXX 107


int rows, columns;

char graph[MAXX][MAXX];

bool visited[MAXX][MAXX];

int component;


int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};



void dfs(paii u)
{
    visited[u.fr][u.sc] = true;

    paii v;

    loop(i, 8)
    {
        v = MP(u.fr + dx[i], u.sc + dy[i]);
        if(0<=v.fr && v.fr <rows && 0<= v.sc && v.sc <columns)
        {
            if( ! visited[v.fr][v.sc] && graph[v.fr][v.sc] == '@' )
            {
                dfs(v);
            }
        }
    }
}


void solve()
{
    mem(visited, 0);

    component = 0;

    loop(i, rows)
    {
        loop(j, columns)
        {
            if(!visited[i][j] && graph[i][j] == '@')
            {
                component++;
                dfs(MP(i, j));
            }
        }
    }
}


int main()
{
    while(true)
    {
        sf("%d %d", &rows, &columns);
        if(rows == 0) break;

        loop(i, rows)
        {
            sf("%s", graph[i]);
        }

        solve();
        //dump(component);
        pf("%d\n", component);


    }






}

(LightOj) 1258 – Making Huge Palindromes

Posted on March 10, 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



#define MAXX 1000007

int pi[MAXX];

void computePrefixFunction(string P)
{
    int m = SZ(P);

    pi[0] = -1;

    int k = -1;

    for(int i=1; i<m; i++)
    {
        while(k>-1 && P[k+1] != P[i])
            k = pi[k];
        if(P[k+1] == P[i])
            k++;
        pi[i] = k;
    }
}


int KMP(string T, string P)
{
    int ret = -1; // MAX matched;


    int n = SZ(T);
    int m = SZ(P);

    computePrefixFunction(P);

    int q = -1;

    for(int i=0; i<n; i++)
    {
        while(q >-1 && P[q+1] != T[i])
            q = pi[q];
        if(P[q+1] == T[i])
            q++;

        if(i == (n-1))
            ret = q+1;

        if(q == (m-1))
        {
            q = pi[q];
        }

    }

    return ret;
}




string str;


int solve()
{
    string rev = str;

    reverse(all(rev));

    int matched = KMP(str, rev);

    //dump(matched);

    return 2*SZ(str) - matched;
}


void init()
{

}


int main()
{
    init();

    int kases, kaseno = 0;

    sf("%d", &kases);

    while(kases--)
    {
        cin>>str;

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



    return 0;
}

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Monthly Archives: March 2015

(LightOj) 1141 – Number Transformation

(LighOj) 1307 – Counting Triangles

(LightOj) 1154 – Penguins

(LightOj) 1155 – Power Transmission

(LightOj) 1153 – Internet Bandwidth

(LightOj) 1129 – Consistency Checker

(LightOj) 1334 – Genes in DNA

(UVa) 10069 – Distinct Subsequences

(UVa) 572 – Oil Deposits

(LightOj) 1258 – Making Huge Palindromes