(UVa) 10226 – Hardwood Species

Posted on April 27, 2013 by Hasib Al Muhaimin

/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1167
*/

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

using namespace std;


#define ALPHA_LIST 128

struct node{
    int cnt_trees;
    node *child[ALPHA_LIST];

    node()
    {
        cnt_trees = 0;
        loop(i, ALPHA_LIST)
        {
            child[i] = NULL;
        }
    }
}*head;

int total;


/*
void clearTree(node *p)
{
    loop(i, ALPHA_LIST)
    {
        if(p->child[i] != NULL)
        {
            clearTree(p->child[i]);
        }
    }
    delete p;
}

void init()
{
    head = new node();
}


int toint(char c)
{
    if(c== ' ')
        return 26;
    if('a' <= c && c <= 'z')
        return c - 'a';
    else
        return c - 'A';
}
*/

void insert(char *word)
{
    //cout<<"inserting " << word<<endl;
    node *current = head;

    int ch;

    while(*word != '\0')
    {
        ch = *word;

        if(current->child[ch] == NULL)
            current->child[ch] = new node();
        current = current->child[ch];
        word++;
    }
    current->cnt_trees++;
}

vector<char> name_list;

void printTree(node *current)
{
    if(current->cnt_trees)
    {
        FOR(i, 0, SZ(name_list))
        {
            pf("%c", name_list[i]);
        }
        pf(" %.4lf\n", (100.0*current->cnt_trees)/(double)total);
        //current->cnt_trees = 0;
    }

    loop(i, ALPHA_LIST)
    {
        if(current->child[i] != NULL)
        {
            name_list.pb(i);
            printTree(current->child[i]);
            name_list.pop_back();
        }
    }

    delete current;
    //current = NULL;
}


int main()
{
    int kases;
    char names[35];
    bool blank = 0;

    gi(kases);
    cin.ignore();
    cin.ignore();

    while(kases--)
    {
        if(blank) pf("\n");
        blank = 1;

        head = new node();

        //init();

        //cout<<head<<endl;

        total = 0;
        while(gets(names))
        {
            if(strlen(names) == 0) break;
            insert(names);
            total++;
        }

        printTree(head);

        //head = NULL;
        //cout<<head<<endl<<endl<<endl;

        //clearTree(head);
    }


    return 0;
}

(USACO) Healthy Holsteins

Posted on April 23, 2013 by Hasib Al Muhaimin

/*
ID: himuhas1
TASK: holstein
LANG: C++
link: http://cerberus.delos.com:790/usacoprob2?S=holstein&a=9j5vF1aY3NU
*/


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

using namespace std;

#define MAXX 32772 //1<<15 + 1
#define debug

struct DATA{
    int amount[26];
} scoops[MAXX], rqr, inp[16];

int countBit(int n)
{
    if(n==0)
    {
        return 0;
    }
    return 1 + countBit(n>>1);
}


int main()
{
    #ifndef hasibpc
        freopen("holstein.in", "r", stdin);
        freopen("holstein.out", "w", stdout);
    #endif // hasibpc


    int number_of_vitamins, G;


    gi(number_of_vitamins);
    loop(i, number_of_vitamins)
    {
        gi(rqr.amount[i]);
    }

    gi(G);

    loop(i, G)
    {
        loop(j, number_of_vitamins)
        {
            gi(inp[i].amount[j]);
        }
    }

    int till = (1<<(G));

    mem(scoops[0].amount, 0);
    /*
    loop(i, G)
    {
        cout<<scoops[0].amount[i]<<"   ";
    }
    */

    int pre, best = ~(1<<29);

    bool valid;


    FOR(i, 1, till)
    {
        pre = i & ~(1<<(countBit(i)-1));
        //pf("i=%d, pre=%d\n", i, pre);
        valid = 1;
        loop(j, number_of_vitamins)
        {
            scoops[i].amount[j] = scoops[pre].amount[j] + inp[countBit(i)-1].amount[j];
            if(scoops[i].amount[j] < rqr.amount[j])
                valid = 0;
        }
        if(valid)
        {
            if(__builtin_popcount(best) > __builtin_popcount(i))
            {
                best = i;
                //cout<<"best updated"<<endl;
            }
        }
        #if 0
        else
        {
            cout<<i<<" is not valid"<<endl;
            loop(k, number_of_vitamins)
            {
                cout<<scoops[i].amount[k]<< " ";
            }
            cout<<endl;
        }
        #endif

    }


    //cout<<"came here"<<endl;
    pf("%d", __builtin_popcount(best));
    //return 00;
    //cout<< "best = " << best <<endl;

    for(int i=0; (1<<i) <= best; i++)
    {
        if(best & (1<<i))
        {
            pf(" %d", i+1);
        }
    }
    puts("");


    return 0;
}

(USACO) Sorting a Three-Valued Sequence (IOI’96 Day-2)

Posted on April 21, 2013 by Hasib Al Muhaimin


/*
ID: himuhas1
TASK: sort3
LANG: C++
link: http://cerberus.delos.com:790/usacoprob2?a=gOkLC92Plmn&S=sort3
*/


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

using namespace std;

#define MAXX 1002
int cnt;
vector<int>numbers;
int cntOnes, cntTows, cntThrees;
bool used[MAXX];

int main()
{
    #ifndef hasibpc
        freopen("sort3.in", "r", stdin);
        freopen("sort3.out", "w", stdout);
    #endif // hasibpc

    cntOnes = cntTows = cntThrees = 0;

    gi(cnt);
    numbers.resize(cnt);
    loop(i, cnt)
    {
        gi(numbers[i]);
        if(numbers[i] == 1)
        {
            cntOnes++;
        }
        else if(numbers[i] == 2)
        {
            cntTows++;
        }
        else
        {
            cntThrees++;
        }
    }


    int spcnt[3][3];
    mem(spcnt, 0);
    int moveNeeded = 0;



    int till = cntOnes;
    loop(i, cntOnes)
    {
        spcnt[0][ numbers[i] - 1 ]++;
    }

    till += cntTows;
    FOR(i, cntOnes, till)
    {
        spcnt[1][numbers[i]-1 ]++;
    }

    FOR(i, till, cnt)
    {
        spcnt[2][numbers[i]-1]++;
    }



    moveNeeded +=   min(spcnt[0][1], spcnt[1][0]);
    moveNeeded +=   min(spcnt[0][2], spcnt[2][0]);
    moveNeeded +=   min(spcnt[1][2], spcnt[2][1]);



    moveNeeded = moveNeeded + ((cnt - moveNeeded*2 - spcnt[0][0] - spcnt[1][1] - spcnt[2][2])*2)/3;

    cout<<moveNeeded<<endl;


    return 0;
}

(USACO) Ordered Fractions

Posted on April 21, 2013 by Hasib Al Muhaimin


/*
ID: himuhas1
TASK: frac1
LANG: C++
link: http://cerberus.delos.com:790/usacoprob2?a=0Hi6SPQOgMg&S=frac1
*/


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

using namespace std;


vector<paii>fractions;


bool comp(paii a, paii b)
{
    return a.fr*b.sc < a.sc * b.fr;
}

int gcd(int a, int b)
{
    if(a%b == 0) return b;

    return gcd(b, a%b);
}


int main()
{
    freopen("frac1.in", "r", stdin);
    freopen("frac1.out", "w", stdout);
    int n;
    paii frac;

    gi(n);

    fractions.pb(MP(0,1));

    for(int i=1; i<=n; i++)
    {
        for(int j=i; j<=n; j++)
        {
            if(gcd(i, j) > 1 ) continue;
            frac.fr = i;
            frac.sc = j;
            fractions.pb(frac);
        }
    }

    sort(all(fractions), comp);

    loop(i, SZ(fractions))
    {
        pf("%d/%d\n", fractions[i].fr, fractions[i].sc);
    }


    return 0;
}

(USACO) The Castle

Posted on April 21, 2013 by Hasib Al Muhaimin

/*
user: himuhas1
link: http://cerberus.delos.com:790/usacoprob2?a=0Hi6SPQOgMg&S=castle
*/

/*
ID: himuhas1
TASK: castle
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 INF 1<<29
using namespace std;

#define MAXX 52

int graph[MAXX][MAXX];
int component[MAXX][MAXX];
int column, row;
vector<int>cntElements;
bool visited[MAXX][MAXX];
char dirx[] = {-1, 0, 1, 0};
char diry[] = {0 , -1, 0, 1};

void bfs(int i, int j)
{
    paii u, v;
    u.fr = i;
    u.sc = j;
    visited[i][j] = 1;

    queue<paii>Q;
    Q.push(u);

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


        component[u.fr][u.sc] = SZ(cntElements) - 1;
        cntElements[ component[u.fr][u.sc] ]++;

        loop(i, 4)
        {
            if( ((graph[u.fr][u.sc] & (1<<i)) == 0 ))
            {
                //pf("%d & %d = %d\n", graph[u.fr][u.sc], (1<<i), 0);
                v.fr = u.fr + diry[i];
                v.sc = u.sc + dirx[i];

                if(!visited[v.fr][v.sc])
                {
                    //pf("(%d, %d) -> (%d, %d)\n", u.fr, u.sc, v.fr, v.sc);
                    visited[v.fr][v.sc] = 1;
                    Q.push(v);
                }
            }
        }
        //break;
    }

}



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

    loop(i, row)
    {
        loop(j, column)
        {
            if(!visited[i][j])
            {
                cntElements.pb(0);
                bfs(i, j);
            }
        }
    }


}


int main()
{
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
    int longestRoom;
    gi2(column, row);

    loop(i, row)
    {
        loop(j, column)
        {
            gi(graph[i][j]);
        }
    }




    setComponent();

    pf("%d\n", SZ(cntElements));

    longestRoom = -INF;
    loop(i, SZ(cntElements))
    {
        longestRoom = max(longestRoom, cntElements[i]);
    }
    pf("%d\n", longestRoom);

    longestRoom = -1;
    paii pos, v;
    char ch;
    for(int j=column-1; -1 < j; j--)
    {
        for(int i=0; i<row; i++)
        {
            for(int c=2; 0 < c; c--)
            {
                if( (graph[i][j] & (1<<c)) != 0 )
                {
                    v.fr = i + diry[c];
                    v.sc = j + dirx[c];
                    if(v.fr < 0 || v.sc >= column) continue;

                    if(component[i][j] != component[ v.fr ][ v.sc ] && longestRoom <= cntElements[ component[i][j] ] + cntElements[component[ v.fr ][ v.sc ]] )
                    {
                        longestRoom = cntElements[ component[i][j] ] + cntElements[component[ v.fr ][ v.sc ]];
                        pos.fr = i;
                        pos.sc = j;
                        ch = (c==1?'N':'E');
                    }
                }

            }
        }
    }
    cout<<longestRoom<<endl;
    cout<<pos.fr+1<<" "<<pos.sc+1<<" "<<ch<<endl;


    return 0;
}

(USACO) Checker Challenge

Posted on April 20, 2013 by Hasib Al Muhaimin

/*
user: php
link: http://cerberus.delos.com:790/usacoprob2?a=T7bTTAFb5qU&S=checker
*/

/*
ID: himuhas1
TASK: checker
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)

using namespace std;
#define MAXX 14

int N;
int cnt = 0;
int mask[MAXX][MAXX];
bool used[MAXX][MAXX];

/*
void getState()
{
    loop(i, N)
    {
        loop(j, N)
        {
            if((mask[i] & (1<<j)) != 0)
            {
                pf("1 ");
            }
            else
            {
                pf("0 ");
            }
        }
        pf("\n");
    }
}
*/


void rec(int row)
{
    if(row == N)
    {
        if(cnt < 3)
        {
            loop(i, N)
            {
                if(i) pf(" ");
                loop(j, N)
                {
                    if(used[i][j])
                    {
                        pf("%d", j+1);
                        break;
                    }
                }
            }
            pf("\n");
        }
        cnt++;
        return;
    }
    else
    {
        loop(i, N)
        {
            if( mask[row][i] == 0 )
            {

                for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
                {
                    mask[r][p]++;
                }

                for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
                {
                    mask[r][q]++;
                }

                for(int r=row+1; r<N; r++)
                {
                    mask[r][i]++;
                }

                used[row][i] = 1;


                //getState();
                //cout<<endl<<endl;

                rec(row+1);


                for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
                {
                    mask[r][p]--;
                }

                for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
                {
                    mask[r][q]--;
                }

                for(int r=row+1; r<N; r++)
                {
                    mask[r][i]--;
                }

                used[row][i] = 0;
            }
        }
    }





}

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

    mem(mask, 0);
    mem(used, 0);

    int row = 0;

    cin>>N;



    loop(i, N)
    {
            for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
            {
                mask[r][p]++;
            }

            for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
            {
                mask[r][q]++;
            }

            for(int r=row+1; r<N; r++)
            {
                mask[r][i]++;
            }

            used[row][i] = 1;


            //getState();
            //cout<<endl<<endl;

            rec(row+1);


            for(int r=row+1,p=i-1; r<N && p>-1; r++, p--)
            {
                mask[r][p]--;
            }

            for(int r=row+1, q=i+1; r<N && q<N; r++, q++)
            {
                mask[r][q]--;
            }

            for(int r=row+1; r<N; r++)
            {
                mask[r][i]--;
            }

            used[row][i] = 0;
    }



    cout<<cnt<<endl;

    //getState();



    return 0;
}

(UVa) 571 – Jugs

Posted on April 20, 2013 by Hasib Al Muhaimin

/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=512
*/

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

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



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second

using namespace std;

#define MAXX 1002

pair<int, paii>state[MAXX][MAXX];
bool visited[MAXX][MAXX];
int target;
int cA, cB;
vector<int>result;
string command[] = {"fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A"};

void bfs()
{
    mem(visited, 0);
    paii u, v;
    u.fr = u.sc = 0;
    visited[0][0] = 1;
    queue<paii>Q;
    Q.push(u);
    int quan;

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



        //change 1
        v = u;
        v.fr = cA;

        if(!visited[v.fr][v.sc])
        {
            state[v.fr][v.sc].fr = 0;
            state[v.fr][v.sc].sc = u;
            visited[v.fr][v.sc] = 1;



            if(v.sc == target) break;
            Q.push(v);
        }

        //change 2
        v = u;
        v.sc = cB;

        if(!visited[v.fr][v.sc])
        {
            state[v.fr][v.sc].fr = 1;
            state[v.fr][v.sc].sc = u;
            visited[v.fr][v.sc] = 1;
            if(v.sc == target) break;
            Q.push(v);
        }

        //change 3
        v = u;
        v.fr = 0;

        if(!visited[v.fr][v.sc])
        {
            state[v.fr][v.sc].fr = 2;
            state[v.fr][v.sc].sc = u;
            visited[v.fr][v.sc] = 1;
            if(v.sc == target) break;
            Q.push(v);
        }

        //change 4
        v = u;
        v.sc = 0;
        if(!visited[v.fr][v.sc])
        {
            state[v.fr][v.sc].fr = 3;
            state[v.fr][v.sc].sc = u;
            visited[v.fr][v.sc] = 1;
            if(v.sc == target) break;
            Q.push(v);
        }

        //change 5
        v = u;
        quan = min(v.fr, cB - v.sc);
        v.fr -= quan;
        v.sc += quan;
        if(!visited[v.fr][v.sc])
        {
            state[v.fr][v.sc].fr = 4;
            state[v.fr][v.sc].sc = u;
            visited[v.fr][v.sc] = 1;
            if(v.sc == target) break;
            Q.push(v);
        }


        //change 6
        v = u;
        quan = min(v.sc, cA - v.fr);

        v.sc -= quan;
        v.fr += quan;

        if(!visited[v.fr][v.sc])
        {
            state[v.fr][v.sc].fr = 5;
            state[v.fr][v.sc].sc = u;
            visited[v.fr][v.sc] = 1;
            if(v.sc == target) break;
            Q.push(v);
        }
    }



    result.clear();

    while(v.fr + v.sc != 0)
    {
        result.pb( state[v.fr][v.sc].fr );
        v = state[v.fr][v.sc].sc;
    }
    reverse(all(result));
    loop(i, SZ(result))
    {
        cout<<command[ result[i] ]<<endl;
    }
    cout<<"success"<<endl;
}





int main()
{
    while(sf("%d %d %d", &cA, &cB, &target) == 3)
    {
        bfs();
    }
    return 0;
}

(UVa) 10246 – Asterix and Obelix

Posted on April 20, 2013 by Hasib Al Muhaimin

/*
user: php
link: uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1187
*/

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

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

#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 getint(a) sf("%d", &a)
#define get2int(a, b) getint(a), getint(b)
#define get3int(a, b, c) getint(a), get2int(b, c)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define pi acos(-1.0)
#define INF 1<<29
#define ll long long
#define dd double
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define MP make_pair
#define pb push_back
#define fr first
#define sc second
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define all(v) v.begin(), v.end()
#define mod abs

using namespace std;

#define MAXX 82

int C, R, Q;

int dist[MAXX][MAXX];
int festcost[MAXX][MAXX];

int main()
{
    //read;
    int kaseno = 0;
    int p, q, d;
    while(1)
    {
        get3int(C, R, Q);
        if(C+R+Q == 0) break;

        loop(i, C)
        {
            loop(j, C)
            {
                if(i == j) dist[i][j] = 0;
                else dist[i][j] = festcost[i][j] = INF;
            }
        }


        loop(i, C)
        {
            getint(d);
            festcost[i][i] = d;
        }


        loop(i, R)
        {
            get3int(p, q, d);
            p--; q--;
            dist[p][q] = dist[q][p] = d;
            festcost[p][q] = festcost[q][p] = max(festcost[p][p], festcost[q][q]);
        }

        loop(k, C)
        {
            loop(i, C)
            {
                loop(j, C)
                {
                    if(dist[i][j] + festcost[i][j] > dist[i][k] + dist[k][j] + max(festcost[i][k], festcost[k][j]))
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        festcost[i][j] = max(festcost[i][k], festcost[k][j]);
                    }
                }
            }
        }


        ///////test
        loop(k, C)
        {
            loop(i, C)
            {
                loop(j, C)
                {
                    if(dist[i][j] + festcost[i][j] > dist[i][k] + dist[k][j] + max(festcost[i][k], festcost[k][j]))
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        festcost[i][j] = max(festcost[i][k], festcost[k][j]);
                    }
                }
            }
        }
        ///////


        if(kaseno) pf("\n");
        pf("Case #%d\n", ++kaseno);

        loop(i, Q)
        {
            get2int(p, q);
            p--; q--;
            if(dist[p][q] + festcost[p][q] >= INF)
                puts("-1");
            else pf("%d\n", dist[p][q] + festcost[p][q]);
        }

    }
    return 0;

}

(UVa) 11463 – Commandos

Posted on April 19, 2013 by Hasib Al Muhaimin

/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2458
*/

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

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


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define getint(n) sf("%d", &n)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define SZ(a) int(a.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define dd double
#define paii pair<int, int>
#define pall pair<ll, ll>
#define MP make_pair
#define fr first
#define sc second
#define mod abs
#define pf printf
#define sf scanf
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
#define INF 100000

using namespace std;

#define MAXX 101

int dist[MAXX][MAXX];



int cntBuildings, cntRoads;




int main()
{
    int kases, kaseno = 0;
    getint(kases);
    int p, q;
    int result;
    while(kases--)
    {
        getint(cntBuildings); getint(cntRoads);

        loop(i, cntBuildings)
        {
            loop(j, cntBuildings)
            {
                if(i == j) dist[i][j] = 0;
                else dist[i][j] = INF;
            }
        }

        while(cntRoads--)
        {
            getint(p); getint(q);
            dist[p][q] = dist[q][p] = 1;
        }

        getint(p); getint(q);

        loop(k, cntBuildings) loop(i, cntBuildings) loop(j, cntBuildings) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j] );

        result = -1;

        loop(i, cntBuildings)
        {
            result = max(result, dist[p][i] + dist[i][q] );
        }

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

}

(USACO) Superprime Rib

Posted on April 18, 2013 by Hasib Al Muhaimin

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



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

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



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second

using namespace std;

#define MAXX 31625

bool isPrime[MAXX];
vector<int>primeList;
int n;

int ara[] = {1, 3, 7, 9};

void generateprime()
{
    mem(isPrime, 1);
    int root = sqrt(MAXX)+1;

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


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


void printprime(int num, int len)
{
    //pf("\tcalling with (%d, %d)\n", num, len);
    if(len == n)
    {
        if(num < MAXX)
        {
            if(isPrime[num])
                pf("%d\n", num);
            return;
        }

        int root = sqrt(num) + 1;
        for(int i=0; primeList[i]<root; i++)
        {
            if(num%primeList[i] == 0)
                return;
        }
        pf("%d\n", num);
        return;
    }

    int newnum;
    num *= 10;
    loop(i, 4)
    {
        newnum = num + ara[i];

        if(newnum < MAXX)
        {
            if(isPrime[newnum])
                printprime(newnum, len+1);
            continue;
        }

        bool prm = 1;
        int root = sqrt(newnum) + 1;
        for(int j=0; primeList[j] < root; j++)
        {
            if(newnum%primeList[j] == 0)
            {
                prm = 0;
                break;
            }
        }
        if(prm)
        {
            printprime(newnum, len+1);
        }
    }

}



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

    generateprime();


    cin>>n;

    printprime(2, 1);
    printprime(3, 1);
    printprime(5, 1);
    printprime(7, 1);

    return 0;
}

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Monthly Archives: April 2013

(UVa) 10226 – Hardwood Species

(USACO) Healthy Holsteins

(USACO) Sorting a Three-Valued Sequence (IOI’96 Day-2)

(USACO) Ordered Fractions

(USACO) The Castle

(USACO) Checker Challenge

(UVa) 571 – Jugs

(UVa) 10246 – Asterix and Obelix

(UVa) 11463 – Commandos

(USACO) Superprime Rib