(USACO) Sweet Butter

Posted on September 6, 2013 by Hasib Al Muhaimin

// link: http://cerberus.delos.com:790/usacoprob2?a=wgELNYzwxkD&amp;S=butter

/*
ID: himuhas1
TASK: butter
LANG: C++
*/
/*
ID: himuhas1
TASK: butter
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, P, C;

#define MAXP 802

int cntCows[MAXP];
ll dist[MAXP];
vector<paii>paths[MAXP];
bool visited[MAXP];

struct comp{
    bool operator()(paii a, paii b)
    {
        return a.fr > b.fr;
    }
};

void bfs(paii u)
{
    int _cost[MAXP];
    mem(_cost, 127);
    mem(visited, 0);

    paii v;

    priority_queue<paii, vector<paii>, comp>Q;
    Q.push(u);
    _cost[u.sc] = 0;
    int mul = cntCows[u.sc];
    //visited[u.sc] = 1;

    while(!Q.empty())
    {
        u = Q.top();

        Q.pop();
        if(!visited[u.sc])
        {
            visited[u.sc] = 1;
            dist[u.sc] += (_cost[u.sc]*mul);  //here to modify
            loop(i, SZ(paths[u.sc]))
            {
                v.sc = paths[u.sc][i].fr;
                if(!visited[v.sc] && _cost[u.sc]+paths[u.sc][i].sc < _cost[v.sc])
                {
                    //dump(i);
                    _cost[v.sc] = _cost[u.sc]+paths[u.sc][i].sc;
                    v.fr = _cost[v.sc];
                    //dump(v.sc);
                    //dump(v.fr);


                    Q.push(v);
                }
            }
        }
    }
}


int main()
{
    #ifndef hasibpc
        read("butter.in");
        write("butter.out");
    #endif

    take(N, P, C);
    int a,b,cost;

    loop(i, N)
    {
        take(a);
        cntCows[a]++;
    }

    loop(i, C)
    {
        take(a, b, cost);
        paths[a].pb(MP(b, cost));
        paths[b].pb(MP(a, cost));
    }

    for(int i=1; i<=P; i++)
    {
        if(cntCows[i])
        {
            bfs(MP(0, i));
        }
    }

    ll result = 1<<29;

    for(int i=1; i<=P; i++)
    {
        //dump(dist[i]);
        result = min(result, dist[i]);
    }

    cout<<result<<endl;







    return 0;
}

(USACO) Magic Squares

Posted on September 5, 2013 by Hasib Al Muhaimin

//link: http://cerberus.delos.com:790/usacoprob2?a=gfh3ra4EtuK&amp;S=msquare
/*
ID: himuhas1
TASK: msquare
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
map<string, string>nodes;


void transformA(string &s)
{
    loop(i, 4)
    {
        swap(s[i], s[7-i]);
    }
}

void transformB(string &s)
{
    loop(i, 3)
    {
        swap(s[i], s[3]);
        swap(s[7-i], s[4]);
    }
}

void transformC(string &s)
{
    swap(s[1], s[6]);
    swap(s[5], s[6]);
    swap(s[2], s[5]);
}


int main()
{
    #ifndef hasibpc
        read("msquare.in");
        write("msquare.out");
    #endif

    string target;

    {
        char c;
        loop(i, 8)
        {
            scanf("%c", &c);
            cin.ignore();
            target.push_back(c);
        }
    }

    //dump(target);

    queue<string>Q;
    string current = "12345678";
    nodes[current] = "-";

    Q.push(current);
    string ss;
    string *ptr;


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

        //dump(current);

        ss = current;
        transformA(ss);
        //dump(ss);
        ptr = &nodes[ss];
        if((*ptr).size() == 0)
        {
            *ptr = current;
            if(*ptr == target) break;
            Q.push(ss);
        }




        ss = current;
        transformB(ss);
        //dump(ss);
        ptr = &nodes[ss];
        if((*ptr).size() == 0)
        {
            *ptr = current;
            if(*ptr == target) break;
            Q.push(ss);
        }



        ss = current;
        transformC(ss);
        //dump(ss);
        ptr = &nodes[ss];
        if((*ptr).size() == 0)
        {
            *ptr = current;
            if(*ptr == target) break;
            Q.push(ss);
        }
    }



    string result;
    //dump(*ptr);

    while(target != "12345678")
    {
        ptr = &nodes[target];

        if((*ptr)[0] == target[7])
        {
            result.pb('A');
        }
        else if((*ptr)[0] == target[0])
        {
            result.pb('C');
        }
        else
        {
            result.pb('B');
        }

        target = *ptr;
    }

    reverse(all(result));
    pf("%d\n", SZ(result));
    cout<<result<<endl;




    return 0;
}

(USACO) Feed Ratios

Posted on August 27, 2013 by Hasib Al Muhaimin

//link: http://cerberus.delos.com:790/usacoprob2?S=ratios&a=0ISnRurrP3v
/*
ID: himuhas1
TASK: ratios
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 target[3], inp[3][3];
int temp[3];
int minSolution[5];


int main()
{
    #ifndef hasibpc
        read("ratios.in");
        write("ratios.out");
    #endif
    mem(minSolution, 0);
    minSolution[3] = (1<<29);
    loop(i, 3) take(target[i]);
    loop(i, 3) loop(j, 3) take(inp[i][j]);
    bool possible;
    loop(i, 100)
    {
        loop(j, 100)
        {
            loop(k, 100)
            {
                loop(l, 3)
                {
                    temp[l] = i*inp[0][l] + j*inp[1][l] + k*inp[2][l];
                }

                if(temp[0] % target[0] == 0)
                {
                    int mul = temp[0] / target[0];
                    if(target[1]*mul == temp[1] && target[2]*mul == temp[2] && i+j+k < minSolution[3] && i+j+k != 0)
                    {
                        minSolution[3] = i + j + k;
                        minSolution[0] = i;
                        minSolution[1] = j;
                        minSolution[2] = k;
                        minSolution[4] = mul;
                    }
                }
            }
        }
    }
    if(minSolution[0] == 0 && minSolution[1] == 0 && minSolution[2] == 0)
    {
        pf("NONE\n");
    }
    else
    {
        pf("%d %d %d %d\n", minSolution[0], minSolution[1], minSolution[2], minSolution[4]);
    }





    return 0;
}

(USACO) Humble Numbers

Posted on August 23, 2013 by Hasib Al Muhaimin

// link: http://cerberus.delos.com:790/usacoprob2?a=VKy6gbSa7gv&S=humble
/*
ID: himuhas1
TASK: humble
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 MAX_PRIMES 102
#define MAX_N 100002
#define INF 4611686018427387904

int primes[MAX_PRIMES];
int hprime[MAX_PRIMES];
long long humble[MAX_N];


int main()
{
    #ifndef hasibpc
        read("humble.in");
        write("humble.out");
    #endif
    int cntPrime, N;
    take(cntPrime, N);
    long long temp;
    loop(i, cntPrime)
    {
        take(primes[i]);
    }
    mem(hprime, 0);

    humble[0] = 1;

    loop(i, N)
    {
        long long next = INF;

        loop(p, cntPrime)
        {
            while(primes[p]*humble[ hprime[p] ] <= humble[i])
            {
                hprime[p]++;
            }
            temp = primes[p]*humble[ hprime[p] ];
            if(temp < next)
            {
                next = temp;
            }
        }
        humble[i+1] = next;
    }

    cout<<humble[N]<<endl;


    return 0;
}

(USACO) Stamps

Posted on July 28, 2013 by Hasib Al Muhaimin


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


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

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


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define ll long long
#define pb push_back
#define MP make_pair
#define mem(a, v) memset(a,  v, sizeof(a))
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define SZ(a) (int(a.size()))
#define INF (1<<29)
#define paii pair<int, int>
#define sf scanf
#define pf printf


using namespace std;


#define MAXX 2000002

#define dump(x) cout<<#x<<" = "<<x<<endl

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


    int n, k, values[52];

    sf("%d %d", &k, &n);

    loop(i, n)
    {
        sf("%d", &values[i]);
    }

    int dp[MAXX];
    mem(dp, 1);
    dp[0] = 0;
    int mxSum = 0;
    int tmp;

    loop(i, n)
    {
        for(int j=0; j<=mxSum; j++)
        {
            if(dp[j] != 16843009 && dp[j]+1 <=k)
            {
                tmp = j + values[i];
                dp[tmp] = min(dp[tmp], dp[j] + 1);
                mxSum = max(mxSum, tmp);
            }
        }
    }

    int res;
    for(res=0; res<=mxSum; res++)
    {
        if(dp[res] == 16843009 )
        {
            break;
        }
    }
    res--;

    cout<<res<<endl;




}

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

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

UnLucky Codes

Focus Not On Your Past, But On Your Present!

Category Archives: USACO

(USACO) Sweet Butter

(USACO) Magic Squares

(USACO) Feed Ratios

(USACO) Humble Numbers

(USACO) Stamps

(USACO) Contact

(USACO) Score Inflation

(USACO) Cow Tours

(USACO) Fractions to Decimals

Bessie Come Home (USACO)