HDU : 1301 (Jungle Roads)

// http://acm.hdu.edu.cn/showproblem.php?pid=1301
// Runtime: 0ms
// Tag: MST, Kruskal 

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

using namespace std;

int parent [30];

struct village {
    int s;
    int e;
    int d;
} a [30];

bool cmp (village p, village q)
{
    if ( p.d < q.d ) return true;
    return false;
}

void reset ()
{
    for ( int i = 0; i < 30; i++ ) parent [i] = i;
}

int parentOf (int n)
{
    if ( n == parent [n] ) return n;
    return parent [n] = parentOf (parent [n]);
}

int main ()
{
    // Read ("in.in");
    int vertex;

    while ( scanf ("%d", &vertex ) && vertex ) {

        reset ();
        int ind = 0;

        for ( int i = 1; i < vertex; i++ ) {
            char start [3]; scanf ("%s", start);
            int k; scanf ("%d", &k);
            for ( int j = 0; j < k; j++ ) {
                char end [3]; scanf ("%s", end);
                scanf ("%d", &a [ind].d);
                a [ind].s = start [0] - 'A';
                a [ind].e = end [0] - 'A';
                ind++;
            }
        }

        sort (a, a + ind, cmp);

        int totalCost = 0;
        int selectedEdges = vertex - 1;

        for ( int i = 0; i < ind && selectedEdges; i++ ) {
            int p = parentOf (a [i].s);
            int q = parentOf (a [i].e);

            if ( p != q ) {
                parent [p] = q;
                selectedEdges--;
                totalCost += a [i].d;
            }
        }

        printf ("%d\n", totalCost);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

HDU : 1085 (Holding Bin-Laden Captive!)

// http://acm.hdu.edu.cn/showproblem.php?pid=1085
// Runtime: 15ms
// Tag: Dp

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

using namespace std;

int main ()
{
    int n [3];
    bool a [20000];

    while ( scanf ("%d %d %d", &n [0], &n [1], &n [2]) ) {
        if ( n [0] == 0 && n [1] == 0 && n [2] == 0 ) break;

        Set (a, false);
        a [0] = true;
        int coins [] = {1, 2, 5};

        for ( int i = 0; i < 3; i++ ) {
            for ( int j = 8000; j >= 0; j-- ) {
                if ( a [j] ) {
                    int ind = coins [i];
                    for ( int k = 0; k < n [i]; k++ ) { a [j + ind] = true; ind += coins [i]; }
                }
            }
        }

        int ind = 1;

        while ( a [ind] ) ind++;

        printf ("%d\n", ind);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

HDU : 2711 (Lost Cows)

// http://acm.hdu.edu.cn/showproblem.php?pid=2711
// Runtime: 46ms
// Tag: Adhoc

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 6:51 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

int main(int argc, char** argv) {
    int n;

    while ( scanf ("%d", &n) != EOF ) {
        vector <int> v;

        for ( int i = 1; i <= n; i++ ) v.push_back(i);

        int arr [8000 + 5];

        for ( int i = 0; i < n - 1; i++ ) scanf ("%d", &arr [i]);

        vector <int> ret;

        for ( int i = n - 2; i >= 0; i-- ) {
            ret.push_back(v [arr [i]]);
            v.erase(v.begin() + arr [i]);
        }
        ret.push_back(v [0]);
        reverse (ret.begin(), ret.end());

        Fors (i, ret) printf ("%d\n", ret [i]);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 2714 (ISBN)

// http://acm.hdu.edu.cn/showproblem.php?pid=2714
// Runtime: 0ms
// Tag: Adhoc

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 5:05 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

char a [20];

void findVal (int pos)
{
    a [pos] = '0';
    int sum = 0;

    for ( int i = 0; i < 10; i++ ) {
        if ( a [i] >= '0' && a [i] <= '9' ) sum += (10 - i) * (a [i] - '0');
        else sum += (10 - i) * 10;
    }

    for ( int i = 0; i < 10; i++ ) {
        if ( (sum + (10 - pos) * i) % 11 == 0 ) {
            printf ("%c\n", '0' + i);
            return;
        }
    }

    if ( pos != 9 ) { printf ("-1\n"); return; }
    if ( (sum + 10) % 11 == 0 ) printf ("X\n");
    else printf ("-1\n");
}

int main(int argc, char** argv) {
    
    while ( scanf ("%s", a) == 1 ) {
        for ( int i = 0; i < 10; i++ ) {
            if ( a [i] == '?' ) {
                findVal (i);
                break;
            }
        }
    }
    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 2710 (Max Factor)

// http://acm.hdu.edu.cn/showproblem.php?pid=2710
// Runtime: 15ms
// Tag: prime, sieve, factors

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 4:02 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

bool mark [N];
vector <int> primeList;

void sieve ()
{
    memset (mark, true, sizeof (mark));

    mark [0] = mark [1] = false;

    for ( int i = 4; i < N; i += 2 ) mark [i] = false;

    for ( int i = 3; i * i <= N; i += 2 ) {
        if ( mark [i] ) {
            for ( int j = i * i; j < N; j += 2 * i ) mark [j] = false;
        }
    }

    primeList.clear ();
    primeList.push_back (2);

    for ( int i = 3; i < N; i += 2 ) {
        if ( mark [i] ) primeList.push_back (i);
    }
}

int largestPrimeFactors (int n)
{
    int ind = 0;
    int tmp = n;
    int ret = 0;

    while ( primeList [ind] * primeList [ind] <= n ) {
        while ( tmp % primeList [ind] == 0 ) {
            tmp /= primeList [ind];
            ret = primeList [ind];
        }
        ind++;
    }

    if ( tmp > 1 )
        return max (ret, tmp);
    return ret;
}


int main(int argc, char** argv) {
    sieve ();

    int n;

    while ( scanf ("%d", &n) != EOF ) {
        int maxi = INF_MIN;
        int ret;
        int num;
        while ( n-- ) {
            scanf ("%d", &num);
            int p = largestPrimeFactors(num);
            if ( maxi < p) {
                maxi = p;
                ret = num;
            }
        }
        printf ("%d\n", ret);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 2700 (Parity)

// http://acm.hdu.edu.cn/showproblem.php?pid=2700
// Runtime: 0ms
// Tag: adhoc

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 3:50 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

int main(int argc, char** argv) {
    char a [50];

    while ( scanf ("%s", a) && strcmp (a, "#") ) {
        int len = strlen (a);
        int one = 0;

        for ( int i = 0; i < len; i++ ) {
            if ( a [i] == '1' ) one++;
        }

        if ( one % 2 ) a [len - 1] = a [len - 1] == 'o' ? '0' : '1';
        else a [len - 1] = a [len - 1] == 'e' ? '0' : '1';

        printf ("%s\n", a);

    }

    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 1050 (Moving Tables)

// http://acm.hdu.edu.cn/showproblem.php?pid=1050
// Runtime: 15ms
// Tag: Adhoc

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 2:51 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

struct Block {
    int s;
    int t;
} a [200 + 5];

int main(int argc, char** argv) {
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int n;
        scanf ("%d", &n);

        for ( int i = 0; i < n; i++ ) {
            scanf ("%d %d", &a [i].s, &a [i].t);
            if (a [i].s > a [i].t) swap (a [i].s, a [i].t);
            a [i].s = a [i].s % 2 ? a [i].s : a [i].s - 1;
            a [i].t= a [i].t % 2 ? a [i].t + 1 : a [i].t;
        }

        int blockRooms [400 + 5];
        Set (blockRooms, 0);

        for ( int i = 0; i < n; i++ ) {
            for ( int j = a [i].s; j <= a [i].t; j++ ) blockRooms [j]++;
        }

        int cnt = 0;
        for ( int i = 0; i < 405; i++ ) cnt = max (cnt, blockRooms [i]);

        printf ("%d\n", cnt * 10);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 2391 (Filthy Rich)

// http://acm.hdu.edu.cn/showproblem.php?pid=2391
// Runtime: 1140ms
// Tag: dp

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 12:02 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

int matrix [1000 + 5] [1000 + 5];

int main(int argc, char** argv) {
    int testCase;
    scanf ("%d", &testCase);
    int cases = 0;

    while ( testCase-- ) {
        int r, c;
        scanf ("%d %d", &r, &c);
        
        for (int i = 0; i < 1005; i++ ) matrix [0] [i] = matrix [i] [0] = 0;

        For (i, 1, r + 1) {
            For (j, 1, c + 1) {
                scanf ("%d", &matrix [i] [j]);
                matrix [i] [j] += max (matrix [i - 1] [j], matrix [i] [j - 1]);
            }
        }

        printf ("Scenario #%d:\n", ++cases);
        printf ("%d\n\n", matrix [r] [c]);
    }
    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 1049 (Climbing Worm)

// http://acm.hdu.edu.cn/showproblem.php?pid=1049
// Runtime: 15ms
// Tag: Adhoc

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 10:46 AM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

int main(int argc, char** argv) {
    int n, u, d;

    while ( scanf ("%d %d %d", &n, &u, &d) ) {
        if ( n == 0 ) break;
        int ret = 0;

        while (n) {
            ret++;
            n -= u;
            if ( n <= 0 ) break;
            ret++;
            n += d;
        }

        printf ("%d\n", ret);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

HDU : 1009 (FatMouse’ Trade)

// http://acm.hdu.edu.cn/showproblem.php?pid=1009
// Runtime: 31ms
// Tag: greedy 

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 18, 2011, 10:16 AM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

struct deal {
    int javaBean;
    int catFood;
    double unit;
} a [1000 + 5];

bool cmp (deal A, deal B)
{
    if ( A.unit > B.unit ) return true;
    return false;
}

int main(int argc, char** argv) {
    int m, n;

    while ( scanf ("%d %d", &m, &n) ) {
        if ( m == -1 && n == -1 ) break;

        for ( int i = 0; i < n; i++ ) {
            scanf ("%d %d", &a [i].javaBean, &a [i].catFood);
            if (a [i].catFood != 0 ) a [i].unit = (double)a [i].javaBean / (double)a [i].catFood;
            else a [i].unit = INF_MAX;
        }

        sort (a, a + n, cmp);
        double ret = 0;

        for ( int i = 0; i < n; i++ ) {
            if ( m >= a [i].catFood ) { ret += a [i].javaBean; m -= a [i].catFood; }
            else if ( m > 0 ) { ret += (m * a [i].unit); break; }
        }

        printf ("%.3lf\n", ret);

    }

    return 0;
}

// @END_OF_SOURCE_CODE