Monthly Archives: September 2013

(USACO) Sweet Butter

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?a=wgELNYzwxkD&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

0
Posted on by 
//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;
}