Monthly Archives: May 2013

(USACO) Controlling Companies

0
Posted on by 

/*
ID: himuhas1
TASK: concom
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 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 101

vector<paii>graph[MAXX];
set<int>allNodes;
vector<int> result;
bool visited[MAXX];
int rank[MAXX];

void dfs(int source)
{
    visited = 1;
    loop(i, SZ(graph))
    {
        if(!visited[graph[i].fr])
        {
            rank[ graph[i].fr ] +=  graph[i].sc;
            if(rank[graph[i].fr] > 50)
            {
                result.pb(graph[i].fr);
                dfs(graph[i].fr);
            }
        }
    }
}

int main()
{
    #ifndef hasibpc
        freopen("concom.in", "r", stdin);
        freopen("concom.out", "w", stdout);
    #endif // hasibpc
    int connection;
    int p, q, r;
    gi(connection);

    loop(i, connection)
    {
        gi3(p, q, r);
        allNodes.insert(p);
        allNodes.insert(q);

        graph[p].pb(MP(q, r));
    }

    for(set<int>::iterator it=allNodes.begin(); it != allNodes.end(); it++)
    {
        result.clear();
        mem(visited, 0);
        mem(rank, 0);
        dfs(*it);
        sort(all(result));
        loop(i, SZ(result))
        {
            pf("%d %d\n", *it, result[i]);
        }
    }





    return 0;
}

(USACO) Money Systems

0
Posted on by 
/*
ID: himuhas1
TASK: money
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 10002

ll dp[MAXX];

int main()
{
    #ifndef hasibpc
        freopen("money.in", "r", stdin);
        freopen("money.out", "w", stdout);
    #endif
    int V, N;
    int coin;
    mem(dp, 0);
    dp[0] = 1;
    cin>>V>>N;
    loop(i, V)
    {
        cin>>coin;
        loop(i, N)
        {
            if(i + coin > N)
                break;
            dp[i+coin] += dp[i];
            //cout<<(i+coin)<<endl;
        }

    }

    cout<<dp[N]<<endl;


    return 0;
}

(USACO) Zero Sum

0
Posted on by

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

#include
#include
#include
#include
#include

#include
#include
#include
#include
#include<map>
#include

#define FOR(i, s, e) for(int i=s; i&lt;e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf(&quot;%d&quot;, &amp;a)
#define gi2(a, b) sf(&quot;%d%d&quot;, &amp;a, &amp;b)
#define gi3(a, b, c) sf(&quot;%d%d%d&quot;, &amp;a, &amp;b, &amp;c)
#define gi4(a, b, c, d) sf(&quot;%d%d%d%d&quot;, &amp;a, &amp;b, &amp;c, &amp;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
#define pall pair
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)

using namespace std;

int n;
vectorv;

void rec(int nxt)
{
if(nxt == n+1)
{
#if 0
loop(j, SZ(v))
{
if(v[j] &gt; 9)
cout&lt;&lt;(char)v[j];
else
cout&lt;&lt;v[j];
}
cout&lt;&lt;endl;
#endif
int lastSum = 0, tmp = 0;
char sign = '+';
int i = 0;

while(i 9)
{
break;
}
lastSum = lastSum*10 + v[i];

i++;
}

while(i &lt; SZ(v))
{
if(v[i] &lt; 10)
{//a number
tmp = tmp*10 + v[i];
}
else
{
if(sign == '+')
{
lastSum += tmp;
}
else
{
lastSum -= tmp;
}
tmp = 0;
sign = v[i];
}
i++;
}

if(sign == '+')
{
lastSum += tmp;
}
else
{
lastSum -= tmp;
}

if(lastSum == 0)
{
cout&lt; 9)
{
pf("%c", v[i]);
}
else
{
if(v[i-1] &lt; 10)
{
pf(&quot; &quot;);
}
pf(&quot;%d&quot;, v[i]);
}
}
cout&lt;&lt;endl;
}
//cout&lt;&lt;lastSum&lt;&gt;n;
v.pb(1);

rec(2);

return 0;
}

(USACO) Longest Prefix

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?a=QX6ufTaKJ4D&S=prefix

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<stdio.h>

#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#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 all(v) v.begin(), v.end()
#define pb push_back
#define sf scanf
#define pf printf
#define mem(a, v) memset(a, v, sizeof(a))
#define dd double
#define ll long long
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())

using namespace std;


#define NO_CHILD -2
#define NO_MAP -1

#define MAXX 200002

struct Trie{
    map<int, map<int, int> > childNode;
    vector<bool>allNodes;
    int id;
    int *p;
    int zero;


    Trie()
    {
        allNodes.pb(0);
        zero = 0;
    }


    void add(const string &val)
    {
        p = &zero;
        int ch;
        loop(i, SZ(val))
        {
            ch = val[i];
            p = &childNode[*p][ch];
            if(*p == 0)
            {
                *p = SZ(allNodes);
                allNodes.pb(0);
            }
        }

        allNodes[*p] = 1;
    }

    void iniCharByCharSearch()
    {
        id = 0;
    }

    int charByCharSearch(char ch)
    {
        if(childNode[id].find(ch) == childNode[id].end())
        {
            return NO_CHILD;
        }
        else
        {
            id = childNode[id][ch];
            return allNodes[id];
        }
    }
};






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

    Trie tr;

    string name;
    string str;
    while(1)
    {
        cin>>name;
        if(name[0] == '.') break;

        tr.add(name);
    }

    while(cin>>name)
    {
        str += name;
    }

    bool dp[MAXX];
    mem(dp, 0);
    int ret;
    int result = 0;
    //dp[0] = 1;
    for(int i=-1; i<SZ(str); i++)
    {
        if(i==-1 || dp[i])
        {
            result = max(result, i+1);
            tr.iniCharByCharSearch();
            FOR(j, i+1, SZ(str))
            {
                ret = tr.charByCharSearch(str[j]);

                //pf("%d %d ==> %d\n", i, j, ret);

                if(ret == 1)
                {
                    //cout<<"j = "<< j<<endl;

                    dp[j] = 1;
                    //result = max(result, j+1);
                }


                if(ret == NO_CHILD)
                    break;

            }
        }
    }

    cout<<result<<endl;




    return 0;
}

(USACO) Runaround Numbers

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?a=bcquvHYkCVC&S=runround

/*
ID: himuhas1
TASK: runround
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;

typedef unsigned long type;

int ara[10];


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

    type num, temp;
    int k;
    int mask;
    int cntDigit;
    int pos;

    cin>>num;

    bool isRunAround;


    while(1)
    {
        num++;
        isRunAround = 1;
        mask = 0;
        temp = num;
        cntDigit = 0;
        while(temp)
        {
            k = temp % 10;
            ara[cntDigit] = k;
            if(mask & (1<<k))
            {
                isRunAround = 0;
                break;
            }
            mask = mask | (1<<k);
            temp /= 10;
            cntDigit++;
        }


        if(isRunAround)
        {
            reverse(ara, ara+cntDigit);
            mask = 0;

            pos = 0;

            while(1)
            {
                //cout<<"pos " << pos<<endl;
                mask = mask | (1<<pos);

                pos = (pos + ara[pos]) % cntDigit;

                if(mask & (1<<pos))
                {
                    if(pos != 0 || (1<<cntDigit)-1 != mask)
                    {
                        isRunAround = 0;
                    }
                    break;
                }

            }
        }
        //cout<<num<<endl;
        if(isRunAround) break;
    }

    cout<<num<<endl;


    return 0;
}

(USACO) Subset Sums

0
Posted on by 
// link: http://cerberus.delos.com:790/usacoprob2?S=subset&a=bcquvHYkCVC
/*
ID: himuhas1
TASK: subset
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 392

int main()
{
    //int p = 1512776590;
    //cout<<p<<endl;
    #ifndef hasibpc
        freopen("subset.in", "r", stdin);
        freopen("subset.out", "w", stdout);
    #endif
    int n;
    cin>>n;
    ll int dp[MAXX];
    mem(dp, 0);

    dp[0] = 1;


    int maxn = 0;
    int mid = (n*(n+1))>>1;
    if(mid%2 == 1)
    {
        cout<<0<<endl;
    }
    else
    {
        mid = mid>>1;
        for(int i=1; i<=n; i++)
        {
            for(int j=min(maxn, mid-i); j>-1; j--)
            {
                if(i+j < MAXX)
                dp[i+j] += dp[j];
            }
            maxn += i;
        }

        cout<<(dp[ mid ]>>1)<<endl;
        }



    return 0;
}

(USACO) Hamming Codes

0
Posted on by 

/*
ID: himuhas1
TASK: hamming
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 256

int N, B, D;

bool isHammingDist[MAXX+2][MAXX+2];

vector<int>output;

void hammindDistCalc()
{
    int cnt;

    FOR(i, 0, MAXX)
    {
        FOR(j, i+1, MAXX)
        {
            cnt = 0;
            FOR(k, 0, B)
            {
                if( (i & (1<<k)) ^ ( j & (1<<k)) )
                    cnt++;
            }
            if(cnt >= D)
                isHammingDist[i][j] = 1;
            else
                isHammingDist[i][j] = 0;

        }
    }
}


bool check(int p)
{
    loop(i, SZ(output))
    {
        if(!isHammingDist[output[i]][p])
            return 0;
    }
    return 1;
}



int main()
{
    #ifndef hasibpc
        freopen("hamming.in", "r", stdin);
        freopen("hamming.out", "w", stdout);
    #endif // hasibpc
    gi3(N, B, D);\

    hammindDistCalc();


    output.pb(0);

    int num = 1;

    while(SZ(output) < N)
    {
        while(!check(num)) num++;
        output.pb(num);
    }


    pf("0");
    FOR(i, 1, SZ(output))
    {
        if(i%10 == 0) pf("\n");
        else pf(" ");
        pf("%d", output[i]);
    }
    pf("\n");



    return 0;
}