(USACO) Contact

Posted on June 26, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: contact
LANG: C++
*/


#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 8192+2

void printBinary(int num)
{
    int len;
    for(int i=13; i>-1; i--)
    {
        if(num & (1<<i))
        {
            len = i;
            break;
        }
    }
    for(int i=len-1; i>-1; i--)
        if(num & (1<<i))
            pf("1");
        else
            pf("0");
}

int main()
{


    #ifndef henapc
        read("contact.in");
        write("contact.out");
    #endif
    int cnt[MAXX];
    mem(cnt, 0);
    int A, B, N;
    string str;
    string inp;
    take(A, B, N);
    char c;
    cin.ignore();
    while(true)
    {
        c = getchar();
        if(c == EOF) break;
        if(c != '\n')
            str.pb(c);
    }
    //debug("str", str, "str");
    B++;

    FOR(len, A, B)
    {
        int mask = 0;

        loop(i, len)
        {
            mask = mask*2 + (str[i] - '0');
        }
        mask = mask | (1<<len);

        //if(len == 2) dump(mask);


        cnt[mask]++;

        FOR(i, len, SZ(str))
        {
            //dump(i);
            mask = mask & ~(1<<len);
            mask = mask*2 + str[i]-'0';
            mask = mask & ~(1<<len);
            mask = mask | (1<<len);
            //if(len == 2) dump(mask);
            cnt[mask]++;
        }
        //dump(cnt[4][2]);
    }



    map<int, vector<int> >all;

    paii temp;

    loop(i, MAXX)
    {

            if(cnt[i])
            {
                all[cnt[i]].pb(i);
            }

        //debug("came here");
    }


    int counting = 0;
    for(map<int, vector<int> >::iterator it = all.end(); it != all.begin() && counting < N;)
    {
        it--;
        counting++;
        pf("%d\n", it->fr);

        vector<int> &v = it->sc;

        printBinary(v[0]);

        FOR(i, 1, SZ(v))
        {
            if(i%6 == 0) pf("\n");
            else pf(" ");
            printBinary(v[i]);
        }
        pf("\n");
    }





    return 0;
}

(USACO) Score Inflation

Posted on June 24, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: inflate
LANG: C++
*/


#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 10002
ll best[MAXX];

int main()
{
#ifndef henapc
    read("inflate.in");
    write("inflate.out");
#endif // henapc

    int given, cntGroups;
    int points, minitus;
    take(given, cntGroups);
    given++;

    loop(i, cntGroups)
    {
        take(points, minitus);
        FOR(i, minitus, given)
        {
            best[i] = max(best[i], best[i-minitus]+points);
        }
    }
    cout<<best[given-1]<<endl;


    return 0;
}

(SPOJ) 8425. Coloring Trees

Posted on June 19, 2013 by Hasib Al Muhaimin

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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;


#define MAXX 100002
char color[MAXX];
int parent[MAXX];
vector<int>graph[MAXX];


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

int main()
{
    int N;
    int x, a, b;
    sf("%d", &N);
    loop(i, N)
    {
        color[i] = -1;
        parent[i] = i;
    }
    N--;
    loop(i, N)
    {
        sf("%d %d", &a, &b);
        graph[a].pb(b);
        graph[b].pb(a);
    }

    int Q;
    sf("%d", &Q);

    loop(i, Q)
    {
        sf("%d %d %d", &x, &a, &b);
        if(x == 1)
        {
            color[a] = b;
            loop(i, SZ(graph[a]))
            {
                if(color[graph[a][i]] == b)
                {
                    parent[find(a)] = find(graph[a][i]);
                }
            }
        }
        else if(x==2)
        {
            if(find(a) == find(b))
            {
                if(a!=b || color[a] != -1 )
                    pf("YES\n");
                else
                    pf("NO\n");
            }

            else
                pf("NO\n");
        }
    }
    return 0;
}

(SPOJ) 61. Brackets

Posted on June 17, 2013 by Hasib Al Muhaimin

//link: http://www.spoj.com/problems/BRCKTS/
#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

struct DATA
{
    int needed_opening;
    int needed_closing;
    DATA()
    {
        needed_closing = needed_opening = 0;
    }
};

#define MAXX 30002

DATA sum[4*MAXX];
char str[MAXX];


void insert(int idx, int st, int ed)
{
    if(st == ed)
    {

        if(str[st] == '(')
        {
            sum[idx].needed_closing = 1;
            sum[idx].needed_opening = 0;
        }
        else
        {
            sum[idx].needed_opening = 1;
            sum[idx].needed_closing = 0;
        }
    }
    else
    {
        int l = idx*2;
        int r = l +1;
        int mid = (st+ed)/2;

        insert(l, st, mid);
        insert(r, mid+1, ed);

        int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);

        sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;

        sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
    }
}

void update(int idx, int st, int ed, int pos)
{
    if(st == ed)
    {
        if(str[pos] == '(')
        {
            sum[idx].needed_closing--;
            sum[idx].needed_opening++;
            str[pos] = ')';
        }
        else
        {
            sum[idx].needed_closing++;
            sum[idx].needed_opening--;
            str[pos] = '(';
        }
    }
    else
    {
        int l = idx*2;
        int r = l + 1;
        int mid = (st+ed)/2;
        if(pos <= mid)
        {
            update(l, st, mid, pos);
        }
        else
        {
            update(r, mid+1, ed, pos);
        }


        int r_closing_min = min(sum[l].needed_closing, sum[r].needed_opening);

        sum[idx].needed_closing = sum[l].needed_closing - r_closing_min + sum[r].needed_closing;

        sum[idx].needed_opening = sum[r].needed_opening - r_closing_min + sum[l].needed_opening;
    }
}

int main()
{
    int stlen, m, k;

    loop(kaseno, 10)
    {
        pf("Test %d:\n", kaseno+1);
        sf("%d", &stlen);
        stlen--;
        sf("%s", str);
        insert(1, 0, stlen);


        sf("%d", &m);
        loop(i, m)
        {
            sf("%d", &k);
            if(k == 0)
            {
                if(sum[1].needed_closing == 0 && sum[1].needed_opening == 0)
                {
                    pf("YES\n");
                }
                else
                {
                    pf("NO\n");
                }
            }
            else
            {
                update(1, 0, stlen, k-1);
            }
        }
    }



    return 0;
}

(USACO) Cow Tours

Posted on June 12, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: cowtour
LANG: C++
*/



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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here


int n;

#define MAXX 151
#define INF 1e10

double dist[MAXX][MAXX];
char graph[MAXX][MAXX];
paii points[MAXX];
int parent[MAXX];
double maxDistFrom[MAXX];


template<typename T>
T sqr(T a)
{
    return a*a;
}

double calculateDist(paii a, paii b)
{
    return sqrt( sqr(a.fr - b.fr) + sqr(a.sc - b.sc) );
}





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

int main()
{
    #ifndef hasibpc
        read("cowtour.in");
        write("cowtour.out");
    #endif // hasibpc
    take(n);
    int p, q;

    dd minDist = INF;
    //debug(minDist);

    loop(i, n)
    {
        take(points[i].fr, points[i].sc);
        parent[i] = i;
    }

    loop(i, n)
    {
        sf("%s", graph[i] );
        loop(j, n)
        {
            if(graph[i][j] == '1')
            {
                dist[i][j] = calculateDist(points[i], points[j]);
                parent[find(i)] = find(j);
            }
            else
            {
                dist[i][j] = INF;
            }
        }
    }

    loop(k, n)
        loop(i, n)
            loop(j, n)
                if(dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];


    map<int, double>mp;

    loop(i, n)
    {
        FOR(j, i+1, n)
        {
            if(find(i) == find(j))
            {
                maxDistFrom[i] = max(maxDistFrom[i], dist[i][j]);
                maxDistFrom[j] = max(maxDistFrom[j], dist[j][i]);
            }
        }
        double &ret = mp[find(i)];
        ret = max(ret, maxDistFrom[i]);
    }



    loop(i, n)
    {
        FOR(j, i+1, n)
        {
            if(find(i) != find(j))
            {
                minDist = min(minDist, max(max(calculateDist(points[i], points[j]) + maxDistFrom[i] + maxDistFrom[j],mp[find(i)]), mp[find(j)]) );
            }
        }
    }

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


    return 0;
}

(USACO) Fractions to Decimals

Posted on June 10, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: fracdec
LANG: C++
*/



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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here


int countDigit(int n)
{
    if(n == 0) return 1;
    int res = 0;
    while(n > 0)
    {
        n /= 10;
        res++;
    }
    return res;
}



int main()
{
    #ifndef hasibpc
        read("fracdec.in");
        write("fracdec.out");
    #endif // hasibpc
    int up, down;
    take(up, down);
    int rem;
    pf("%d.", up/down);
    int cnt = countDigit(up/down) + 1;
    rem = up % down;

    if(rem == 0) {
        pf("0\n");
    }
    else
    {
        vector<int> v;
        map<int, int>mp;
        int *p;

                                                //debug("\n");
        bool flag;
        while(rem > 0)
        {
            rem *= 10;


            //dump(rem);
            p = &mp[rem];
            if(*p == 0) {
                *p = SZ(v) + 1;
            }
            else
                break;

            v.pb(rem/down);
            rem %= down;
        }



        if(rem > 0)
        {
            (*p)--;
            //dump(*p);
            //dump(rem);
            //debug(*p, rem);
            loop(i, *p)
            {
                if(cnt++ == 76)
                {
                    pf("\n");
                    cnt = 1;
                }
                pf("%d", v[i]);
            }

            if(cnt++ == 76){
                    pf("\n");
                    cnt = 1;
            }
            pf("(");
            FOR(i, *p, SZ(v))
            {
                if(cnt++ == 76)
                {
                    pf("\n");
                    cnt = 1;
                }
                pf("%d", v[i]);
            }
            if(cnt++ == 76)
            {
                pf("\n");
                cnt = 1;
            }
            pf(")\n");
        }
        else
        {
            loop(i, SZ(v))
            {
                if(cnt++ == 76)
                {
                    pf("\n");
                    cnt = 1;
                }
                pf("%d", v[i]);
            }
            pf("\n");
        }
    }




    return 0;
}

Bessie Come Home (USACO)

Posted on June 9, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: comehome
LANG: C++
*/



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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#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 freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define dump(x) cout<<#x<<" = "<<(int)x<<endl
#define INF (1<<29)

using namespace std;

#define MAXX 52

vector<paii> graph[MAXX];


void toInt(char &c)
{
    if('A' <= c && c <= 'Z')
        c = c -'A' + 26;
    else
        c = c - 'a';
}

struct DATA{
    char idx;
    int d;
    bool operator<(const DATA& a) const
    {
        return d > a.d;
    }
};

int dist[MAXX];

void dijkstra()
{
    paii result;
    result.sc = INF;
    priority_queue<DATA>Q;
    loop(i, MAXX) dist[i] = INF;
    dist[51] = 0;
    DATA u,v;
    u.idx = 51;
    u.d = 0;
    Q.push(u);

    while(!Q.empty())
    {
        u = Q.top(); Q.pop();
        //dump(u.idx);
        if(u.d && u.idx > 25 && u.d < result.sc)
        {
            result.fr = u.idx;
            result.sc = u.d;
        }

        if(dist[u.idx] == u.d)
        {
            loop(i, SZ(graph[u.idx]))
            {
                v.idx = graph[u.idx][i].fr;
                //cout<<"\t"; dump(v.idx);
                v.d = u.d + graph[u.idx][i].sc;
                if(dist[v.idx] > v.d )
                {
                    dist[v.idx] = v.d;
                    Q.push(v);
                }
            }
        }
    }

    result.fr = result.fr - 26 + 'A';
    cout<<(char)result.fr<<" "<<result.sc<<endl;


}

int main()
{
    #ifndef hasibpc
        freopen("comehome.in", "r", stdin);
        freopen("comehome.out", "w", stdout);
    #endif // hasipc
    int paths;
    gi(paths);
    char a, b;
    int d;

    loop(i, paths)
    {
        cin.ignore();
        sf("%c %c %d", &a, &b, &d);
        //dump(a); dump(b); dump(d);
        toInt(a);
        toInt(b);
        //dump(a); dump(b);
        graph[a].pb(MP(b,d));
        graph[b].pb(MP(a,d));
    }

    dijkstra();





    return 0;
}

Overfencing (USACO)

Posted on June 8, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: maze1
LANG: C++
*/



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

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

#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d %d", &a, &b)
#define sf scanf
#define pf printf
#define pb push_back
#define fr first
#define sc second
#define MP make_pair
#define PI acos(-1.0)
#define INF 1<<29;
#define ll long long
#define paii pair<int, int>
#define all(v) v.begin(), v.end()
#define SZ(a) int(a.size())
#define dd double
#define mem(a, v) memset(a, v, sizeof(a))
#define dump(x) cout<<#x<<" = "<<(int)x<<endl;


using namespace std;

#define CONDITION -1 < tmp.fr && tmp.fr < rows && -1 < tmp.sc && tmp.sc < columns && graph[tmp.fr][tmp.sc] ==' '

int columns, rows;
char graph[202][78];

paii exits[2];

int bfs(paii u, paii v)
{
    //dump(u.fr); dump(u.sc); dump(v.fr); dump(v.sc);
    char dir[] = {-1, 0, 1, 0};
    int dist[202][78];
    bool visited[202][78];
    int finalDist = 0;
    mem(visited, 0);

    paii tmp;


    loop(i, 4)
    {
        tmp.fr = u.fr + dir[i];
        tmp.sc = u.sc + dir[(i+1)%4];

        if(CONDITION)
        {
             u = tmp;
             break;
        }
    }

    loop(i, 4)
    {
        tmp.fr = v.fr + dir[i];
        tmp.sc = v.sc + dir[(i+1)%4];

        if(CONDITION)
        {
             v = tmp;
             break;
        }
    }



    dist[u.fr][u.sc] = dist[v.fr][v.sc] = 0;
    visited[u.fr][u.sc] = visited[v.fr][v.sc] = 1;
    queue<paii>Q;
    Q.push(u);
    Q.push(v);



    while(!Q.empty())
    {
        u = Q.front(); Q.pop();
        loop(i, 4)
        {
            tmp.fr = u.fr + dir[i];
            tmp.sc = u.sc + dir[(i+1)%4];
            if(CONDITION)
            {
                tmp.fr += dir[i];
                tmp.sc += dir[(i+1)%4];
                if(CONDITION && !visited[tmp.fr][tmp.sc] )
                {
                    //dump(u.fr); dump(u.sc); dump(tmp.fr); dump(tmp.sc); cout<<endl;
                    visited[tmp.fr][tmp.sc] = 1;
                    finalDist = max(dist[tmp.fr][tmp.sc] = dist[u.fr][u.sc] + 1, finalDist);
                    //dump(finalDist);
                    Q.push(tmp);
                }
            }


        }
    }
    return finalDist+1;

}



int main()
{
    #ifndef hasibpc
    freopen("maze1.in", "r", stdin);
    freopen("maze1.out", "w", stdout);
    #endif
    gi2(columns, rows);
    columns = columns*2 + 1;
    rows = rows*2 + 1;

    cin.ignore();
    loop(i, rows)
    {
        gets(graph[i]);
    }

    {
        char x = 0;
        for(int i=1; i<columns; i++)
        {
            //dump(graph[0][i]);
            //dump(i);
            if(graph[0][i] == ' ')
                exits[x++] = MP(0, i);

            if(graph[rows-1][i] == ' ')
                exits[x++] = MP(rows-1, i);
        }

        for(int i=1; i<rows; i++)
        {
            //dump(graph[i][0]);
            //cout<<int(graph[i][0])<<" "<<int(' ')<<endl;

            if(graph[i][0] == ' ')
                exits[x++] = MP(i, 0);
            if(graph[i][columns-1] == ' ')
                exits[x++] = MP(i, columns-1);
        }
        //dump(x);
    }


    cout<<bfs(exits[0], exits[1])<<endl;

    return 0;
}

The Tamworth Two (USACO)

Posted on June 7, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
LANG: C++
TASK: ttwo
*/


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

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

#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 gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d %d", &a, &b)
#define dump(x) cout<<#x<<" = "<<x<<endl;
#define mem(a, v) memset(a, v, sizeof(a))
#define PI acos(-1.0)
#define INF 1<<29
#define pb push_back
#define fr first
#define sc second
#define MP make_pair
#define paii pair<int, int>
#define ll long long
#define pall pair<ll, ll>

using namespace std;

#define MAXX 11

#define VISITED(far, cow,dirF,dirC) visited[far.fr][far.sc][dirF][cow.fr][cow.sc][dirC]

char graph[MAXX][MAXX];
bool visited[MAXX][MAXX][4][MAXX][MAXX][4];
paii farmer, cows;

int dirx[] = {-1, 0, 1, 0};
int diry[] = {0,  1, 0,-1};


int dfs()
{
    mem(visited, 0);

    char dirFarmer = 0, dirCows = 0;
    paii temp;
    int dist = 0;

    while(VISITED(farmer, cows,dirFarmer,dirCows)==0 && farmer != cows)
    {

        //dump(dist);
        VISITED(farmer, cows,dirFarmer, dirCows) = 1;

        temp.fr = farmer.fr + dirx[dirFarmer];
        temp.sc = farmer.sc + diry[dirFarmer];

        if(-1<temp.fr && temp.fr < 10 && -1 < temp.sc && temp.sc < 10 && graph[temp.fr][temp.sc] != '*')
            farmer = temp;
        else
            dirFarmer = (dirFarmer+1)%4;


        temp.fr = cows.fr + dirx[dirCows];
        temp.sc = cows.sc + diry[dirCows];

        if(-1<temp.fr && temp.fr < 10 && -1 < temp.sc && temp.sc < 10 && graph[temp.fr][temp.sc] != '*')
            cows = temp;
        else
            dirCows = (dirCows+1)%4;
        dist++;
        //dump(farmer.fr); dump(farmer.sc); dump(cows.fr); dump(cows.sc);
    }
    if(farmer == cows)
        return dist;
    else
        return 0;

}



int main()
{
    freopen("ttwo.in", "r", stdin);
    freopen("ttwo.out", "w", stdout);

    loop(i, 10)
    {
        sf("%s", graph[i]);
        loop(j, 10)
        {
            if(graph[i][j] == 'F')
                farmer = MP(i, j);
            else if(graph[i][j] == 'C')
                cows = MP(i, j);
        }
    }
    cout<<dfs()<<endl;
}

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Monthly Archives: June 2013

(USACO) Contact

(USACO) Score Inflation

(SPOJ) 8425. Coloring Trees

(SPOJ) 61. Brackets

(USACO) Cow Tours

(USACO) Fractions to Decimals

Bessie Come Home (USACO)

Overfencing (USACO)

The Tamworth Two (USACO)