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


    }






}

(UVa) 164 – String Computer

Posted on March 9, 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 mypair pair<int, char>
#define INF (1<<20)


#define MAXX 50

mypair dp[MAXX][MAXX];

bool visited[MAXX][MAXX];


string from, to;



//#define min something

/*
template<typename T>
T min(T a, T b)
{
    if(a.fr == b.fr)
    {
        T p, q;
        p = a;
        q = b;

        if(p.sc == 'D')
            p.sc = 0;
        else if(p.sc == 'I')
            p.sc = 1;
        else if(p.sc == 'C')
            p.sc = 2;
        else
            p.sc = 3;

        if(q.sc == 'D')
            q.sc = 0;
        else if(p.sc == 'I')
            p.sc = 1;
        else if(p.sc == 'C')
            p.sc = 2;
        else
            p.sc = 3;


        if(p <= q)
            return a;
        else
            return b;
    }

    return (a<=b)?a:b;
}
*/


int rec(int i, int j)
{


    mypair &ret = dp[i][j];

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

    visited[i][j] = true;

    if(i>= SZ(from) && j >= SZ(to))
    {
        ret = MP(0, 'F');
        return ret.fr;
    }
    else if(i >= SZ(from))
    {
        ret = MP(SZ(to) - j, 'F');
        return ret.fr;
    }
    else if(j >= SZ(to))
    {
        ret = MP(SZ(from) - i, 'F');
        return ret.fr;
    }



    ret = MP(INF, '\0');

    ret = min(ret, MP(rec(i+1, j) + 1, 'D'));

    if(from[i] == to[j])
    {
        ret = min(ret, MP( rec(i+1, j+1), 'N' ));
    }
    else
    {
        ret = min(ret, MP(rec(i+1, j+1) + 1, 'C' ));
        ret = min(ret, MP(rec(i, j+1) + 1, 'I') );
    }

    //cerr<<"rec("<<i<<", "<<j<<") = "<<ret<<endl;


    return ret.fr;
}




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

    rec(0, 0);

    int i = 0, j = 0;

    int ch = 0;

    int cnt = 0;

    while(true)
    {
        ch = dp[i][j].sc;

        if(ch == 'F')
        {
            break;
        }
        else
        {
            if(ch == 'D')
            {
                pf("D%c%02d", from[i], i+1+cnt );
                i++;
                cnt--;
            }
            else if(ch == 'C')
            {
                pf("C%c%02d", to[j], i+1 + cnt);
                i++;
                j++;
            }
            else if(ch == 'I')
            {
                pf("I%c%02d", to[j], i + 1 + cnt);
                j++;
                cnt++;
            }
            else if(ch == 'N')
            {
                i++;
                j++;
            }
        }
    }

    while(true)
    {
        if(i>= SZ(from) && j >= SZ(to))
        {
            break;
        }
        else if(i>=SZ(from))
        {
            printf("I%c%02d", to[j], i+1+cnt);
            j++;
            cnt++;
        }
        else if(j>=SZ(to))
        {
            printf("D%c%02d", from[i], i+1+cnt);
            i++;
            cnt--;
        }
    }

    printf("E\n");



}





void init()
{
    #ifdef hasibpc
       // read("input");
       // write("output");
    #endif // hasibpc
}


int main()
{
    init();

    while(true)
    {
        cin>>from;

        if(from[0] == '#') break;

        cin>>to;

        solve();
    }


    return 0;
}

(UVa) 615 – Is It A Tree?

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







set<int>NodeList;

set<int>inputNodes;

map<int,int>parent;


int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}



void init()
{

}


int main()
{
    init();

    int kaseno = 0;
    int p, q;
    int edge;
    bool possible;

    while(true)
    {
        scanf("%d %d", &p, &q);
        if(p < 0 && q < 0)
        {
            break;
        }
        else
        {
            edge = 0;
            NodeList.clear();
            inputNodes.clear();
            parent.clear();
            possible = true;

            while(p != 0 && q != 0)
            {
                edge++;
                NodeList.insert(p);
                NodeList.insert(q);

                if(parent[p] == 0)
                {
                    parent[p] = p;
                }

                if(parent[q] == 0)
                {
                    parent[q] = q;
                }

                int u = find(p);
                int v = find(q);
                if(u == v)
                {
                    possible = false;
                }

                parent[ v ] = u;

                if(inputNodes.find(q) != inputNodes.end())
                {
                    possible = false;
                }
                else
                {
                    inputNodes.insert(q);
                }

                scanf("%d %d", &p, &q);
            }

            if( edge == 0 || (possible && (edge == SZ(NodeList) - 1) && (edge == SZ(inputNodes)) ) )
            {
                pf("Case %d is a tree.\n", ++kaseno);
            }
            else
            {
                pf("Case %d is not a tree.\n", ++kaseno);
            }

        }
    }



    return 0;
}

(UVa) 10990 – Another New Function

Posted on February 17, 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 2000007



int phi[MAXX];

ll depth[MAXX], comu[MAXX];


void generatePhi()
{
    loop(i, MAXX)
    {
        phi[i] = i;
    }

    for(int i=2; i<MAXX; i+=2)
    {
        phi[i] /= 2;
    }

    bool isPrime[MAXX];

    mem(isPrime, 1);

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

void generateDepth()
{
    for(int i=2; i<MAXX; i++)
    {
        depth[i] = depth[ phi[i] ] + 1;
    }
}


void generateComu()
{
    for(int i=1; i<MAXX; i++)
    {
        comu[i] = comu[i-1] + depth[i];
    }
}






void init()
{
    generatePhi();

    generateDepth();

    generateComu();
}


int main()
{
    init();


    int kases, n, m;

    take(kases);

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

        pf("%lld\n", comu[n] - comu[m-1]);
    }



    return 0;
}

(UVa) 11889 – Benefit

Posted on February 17, 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 10007



ll A, C;
vector<ll>primes;



void generatePrimes()
{

    bool isPrime[MAXX];

    mem(isPrime, 1);

    int root = sqrt(MAXX) + 7;

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

    primes.pb(2);



    for(int i=3; i<MAXX; i+=2)
    {
        if(isPrime[i])
        {
            primes.pb(i);
        }
    }

}

void init()
{
    generatePrimes();

}


void solve()
{
    if((C%A) != 0)
    {
        pf("NO SOLUTION\n");
    }
    else
    {
        ll root = sqrt(C);

        ll ret = 1;

        for(int i=0; i<SZ(primes) && primes[i] <= root; i++)
        {
            if((C%primes[i]) == 0)
            {
                ll tmp = 1;

                while( (C%primes[i]) == 0 && (A % primes[i]) == 0 )
                {
                    tmp*=primes[i];
                    C /= primes[i];
                    A /= primes[i];
                }

                if( (C % primes[i]) == 0 )
                {
                    do {
                        tmp *= primes[i];
                        C /= primes[i];
                    }while( (C%primes[i]) == 0 );

                    ret *= tmp;

                }

                root = sqrt(C);
            }
        }

        if(C != 1)
        {
            if(A != C)
            {
                ret *= C;
            }
        }

        pf("%lld\n", ret);
    }
}


int main()
{
    init();

    int kases;

    take(kases);

    while(kases--)
    {
        take(A, C);

        solve();
    }



    return 0;
}

(LightOj) 1331 – Agent J

Posted on February 16, 2015 by Hasib Al Muhaimin


#include<iostream>
#include<cmath>
#include<cstdio>
#define PI acos(-1.0)

double cosInverse(double angle)
{
    return acos(angle) * 180.0 / PI;
}
using namespace std;
int main()
{
    int cases, caseno = 0;
    double a, b, c, angleA, angleB, angleC, fullArea;
    cin>>cases;
    while(cases--)
    {
        cin>>a>>b>>c;
        angleC = (a*(a+b+c) - b*c) / (a*(a+b+c) + b*c);
        angleC = cosInverse(angleC);
        angleB = (b*(a+b+c) - a*c) / (b*(a+b+c) + a*c);
        angleB = cosInverse(angleB);
        angleA = 180.0 - angleB - angleC;


        fullArea = 0.5 * (a+c) * (a+b) * sin(angleC * PI/180.0);
        fullArea -= (PI*a*a)*angleC/360.0;
        fullArea -= (PI*b*b) * angleB / 360.0;
        fullArea -= (PI*c*c) * angleA / 360.0;
        printf("Case %d: %.9lf\n", ++caseno, fullArea);

    }
    return 0;
}

(UVA) 11909 – Soya Milk

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


#define toRadian(x) ((x) * PI / 180.0)

void init()
{

}


int main()
{
    init();

    double l, h, w, theta;

    while(cin>>l>>w>>h>>theta)
    {
        double tmp = atan(h/l);

        double ret = 0;

        if(toRadian(theta)> tmp)
        {
            //dump(true);
            theta = 90.0 - theta;

            swap(h, l);

            ret = w*0.5*l*l*tan(toRadian(theta));
        }
        else
        {
            ret = w * (l*h - 0.5*l*l*tan(toRadian(theta)));
        }


        if(l == 0 || h == 0 || w == 0)
        {
            ret = 0;
        }

        pf("%.3lf mL\n", ret);
    }



    return 0;
}

(UVA) 11579 – Triangle Trouble

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


#define MAXX 10007


void init()
{

}


int main()
{
    init();

    int kases, N;

    double len[MAXX];

    take(kases);

    while(kases--)
    {
        take(N);

        loop(i, N)
        {
            take(len[i]);
        }

        sort(len, len + N);

        reverse(len, len + N);

        double max_area = 0;

        loop(i, N)
        {
            int j = i + 1;
            int k = j + 1;
            if(k>=N)
            {
                break;
            }

            if(len[i] < len[j] + len[k])
            {
                double s = (len[i] + len[j] + len[k]) / 2.0;

                double area = sqrt(s*(s - len[i])*(s - len[j]) * (s - len[k]));

                max_area = max(max_area, area);

                //break;
            }




        }

        pf("%.2lf\n", max_area);
    }



    return 0;
}

(UVA) 10991 – Region

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()
{

}

#define sq(x) (x*x)
#define toDegree(x) ((x) * 180/PI)


int main()
{
    init();

    int kases;
    double r1, r2, r3;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%lf %lf %lf", &r1, &r2, &r3);


        double s = r1 + r2 + r3;

        double area = sqrt(s*r1*r2*r3);

        double a = r2 + r3;
        double b = r1 + r3;
        double c = r1 + r2;

        double A = (sq(b) + sq(c) - sq(a)) / (2*b*c);

        A = acos(A);

        A = toDegree(A);

        double B = ( sq(a) + sq(c) - sq(b) ) / (2*a*c);

        B = acos(B);

        B = toDegree(B);

        double C = (sq(a) + sq(b) - sq(c)) / (2*a*b);

        C = acos(C);

        C = toDegree(C);

        area = area - (PI*r1*r1 * (A/360.0)) - (PI*r2*r2* (B/360.0)) - (PI*r3*r3*(C/360.0));

        pf("%.6lf\n", area);

    }



    return 0;
}

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Category Archives: UVa

(UVa) 10069 – Distinct Subsequences

(UVa) 572 – Oil Deposits

(UVa) 164 – String Computer

(UVa) 615 – Is It A Tree?

(UVa) 10990 – Another New Function

(UVa) 11889 – Benefit

(LightOj) 1331 – Agent J

(UVA) 11909 – Soya Milk

(UVA) 11579 – Triangle Trouble

(UVA) 10991 – Region