UVa : 1225 (Digit Counting)

// http://uva.onlinejudge.org/external/12/1225.html
// runtime: 0.012s
// tag: adhoc, frequency


#include <cstdio>
#include <cstring>

using namespace std;

int main ()
{
    int testCase; scanf ("%d", &testCase);

    while ( testCase-- ) {
        int n; scanf ("%d", &n);
        int cnt [10];

        memset (cnt, 0, sizeof cnt);

        for ( int i = 1; i <= n; i++ ) {
            int tmp = i;
            while ( tmp ) {
                cnt [tmp % 10]++;
                tmp /= 10;
            }
        }

        for ( int i = 0; i < 9; i++ ) printf ("%d ", cnt [i]);
        printf ("%d\n", cnt [9]);
    }

    return 0;

}

UVa : 12403 (Save Setu)

// http://uva.onlinejudge.org/external/124/12403.html
// runtime: 0.012s
// tag: adhoc, string


#include <cstdio>
#include <cstring>

using namespace std;

int main ()
{
    int testCase; scanf ("%d", &testCase);
    char input [100];
    int totalAmount = 0;
    int inputAmount;

    while ( testCase-- ) {

        scanf ("%s", input);

        if ( strcmp (input, "donate") == 0 ) {
            scanf ("%d", &inputAmount);
            totalAmount += inputAmount;
        } else {
            printf ("%d\n", totalAmount);
        }
    }

    return 0;

}

UVa: 793 (Network Connections)

// link: http://uva.onlinejudge.org/external/7/793.html
// Runtime: 0.260s
// Tag: Union find 


#include <cstdio>
#include <cstring>
#include <cctype>

#define N 1000000

using namespace std;

int parent [N];

int findParent (int p)
{
    if ( parent [p] == p ) return p;
    return parent [p] = findParent(parent [p]);
}

int main ()
{
    int testCases; scanf ("%d", &testCases);
    bool blank = false;

    while ( testCases-- ) {

        for ( int i = 0; i < N; i++ ) parent [i] = i;

        int numberOfComputers;
        scanf ("%d", &numberOfComputers);
        getchar ();

        char command;
        int computeri, computerj;
        int successfulCnt = 0, unsuccessfulCnt = 0;

        while ( (command = getchar ()) && isalpha (command) ) {

            scanf ("%d %d", &computeri, &computerj); getchar ();

            int p = findParent(computeri);
            int q = findParent(computerj);

            if ( command == 'c' ) {
                parent [p] = q;

            } else {
                if ( p == q ) successfulCnt++;
                else unsuccessfulCnt++;
            }
        }

        if ( blank ) printf ("\n"); blank = true;
        printf ("%d,%d\n", successfulCnt, unsuccessfulCnt);

    }

    return 0;

}

UVa: 615 (Is It A Tree?)

// http://uva.onlinejudge.org/external/6/615.html
// Runtime: 0.016s
// tag: Connected Graph, DFS, inDegree


//============================================================================
// Name        : SampleUVa.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <map>

#define N 1000
using namespace std;

map <int, int> mapping;
vector <int> matrix [N];
map <int, int> inDegree;
bool visited [N];

void dfs (int n)
{
	visited [n] = true;

	for ( size_t i = 0; i < matrix [n].size (); i++ ) {
		if ( visited [matrix [n] [i]] == false ) dfs (matrix [n] [i]);
	}
}

void print ()
{
	for ( map<int,int>::iterator it = inDegree.begin (); it != inDegree.end (); it++) {
		printf ("# %d ==> %d ||", (*it).first, (*it).second);
	}

	printf ("\n");
}

int main ()
{

	int m, n;
	int cases = 0;

	while ( scanf ("%d %d", &m, &n) ) {
		if ( m < 0 && n < 0 ) break;

		mapping.clear ();
		inDegree.clear ();
		for ( int i = 0; i < N; i++ ) matrix [i].clear ();
		memset (visited, false, sizeof visited);
		int mappingNum = 1;

		mapping [m] = mappingNum++;
		mapping [n] = mappingNum++;

		matrix [mapping [m]].push_back (mapping [n]);
		inDegree [mapping [m]] = inDegree [mapping [n]] = 0;
		inDegree [mapping [n]]++;

		//print ();

		if ( m == 0 && n == 0 ) { printf ("Case %d is a tree.\n", ++cases); continue; }

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

			if ( !mapping [m] ) { mapping [m] = mappingNum++; inDegree [mapping [m]] = 0; }
			if ( !mapping [n] ) { mapping [n] = mappingNum++;  inDegree [mapping [n]] = 0; }

			matrix [mapping [m]].push_back (mapping [n]);
			inDegree [mapping [n]]++;
			//print ();
		}

		int root;
		int rootCount = 0;
		bool isOnlyOneInDegree = true;

		for ( map<int,int>::iterator it = inDegree.begin (); it != inDegree.end (); it++) {
			if ( (*it).second == 0 ) { rootCount++;
			//printf ("*** %d\n", (*it).first);
			root = (*it).first; }
			else if ( (*it).second > 1 ) isOnlyOneInDegree = false;
		}

		printf ("Case %d is ", ++cases);

		if ( rootCount > 1 || !isOnlyOneInDegree || rootCount == 0 ) { printf ("not a tree.\n"); continue; }

		dfs (root);

		bool isConnectedGraph = true;

		for ( int i = 1; i < mappingNum; i++ ) {
			if ( visited [i] == false ) isConnectedGraph = false;
		}

		if ( !isConnectedGraph ) printf ("not a tree.\n");
		else printf ("a tree.\n");

	}

	return 0;
}

UVa : 497 (Strategic Defense Initiative )

// http://uva.onlinejudge.org/external/4/497.html
// Runtime: 0.016s
// Tag: LIS, 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>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

const double EPS = 1e-9;
inline bool Equal(double a, double b) { return abs(a-b) < EPS; }
inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;

// @BEGIN_OF_SOURCE_CODE
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// Dp: O(n^2)
void get_lis_length (int *a, int length)
{
	int best [length]; // length of LIS upto using this num
	int prev_element [length]; // previous elements index
	for ( int i = 0; i < length; i++ )
	{
		best [i] = 1;
		prev_element [i] = i;
	}
	// first number always right, i = 1
	for ( int i = 1; i < length; i++ )
	{
		for ( int j = 0; j < i; j++ )
		{
			if ( a [i] > a [j] && best [i] < best [j] + 1 )
			{
				best [i] = best [j] + 1;
				prev_element [i] = j;
			}
		}
	}
	int lis_length = 0;
	int numIndex = -1;
	for ( int i = 0; i < length; i++ ) {
		if ( lis_length < best [i] ) {
			lis_length = best [i];
			numIndex = i;
		}
	}

	printf ("Max hits: %d\n", lis_length);

	vector <int> output;

	while ( prev_element [numIndex] != numIndex ) {
		output.push_back(a [numIndex]);
		numIndex = prev_element [numIndex];
	}

	output.push_back(a [numIndex]);
	reverse(output.begin(), output.end());

	Fs (i, output) printf ("%d\n", output [i]);
}
int main ()
{
	int testCase; scanf ("%d", &testCase);
	getchar ();
	char ch [20]; gets (ch);

	bool blank = false;

	int nums [10000];

	while ( testCase-- ) {
		int ind = 0;

		while ( gets (ch) && strlen (ch) ) {
			nums [ind++] = atoi (ch);
		}

		if ( blank ) printf ("\n");
		blank = true;

		get_lis_length (nums, ind);

	}

	return 0;
}
// @END_OF_SOURCE_CODE

UVa : 913 (Joana and the Odd Numbers)

// http://uva.onlinejudge.org/external/9/913.html
// Runtime: 2.292s
// Tag: math

// @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>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

const double EPS = 1e-9;
inline bool Equal(double a, double b) { return abs(a-b) < EPS; }
inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;

int main ()
{
	int n;

	while ( scanf ("%d", &n) != EOF ) {
		int lineNumber = n / 2;
		LL num = 6;
		LL next = 1;

		for ( int i = 0; i < lineNumber; i++ ) {
			next += num;
			num += 4;
		}

		printf ("%lld\n", next + (next - 2) + (next - 4));

	}

	return 0;
}

UVa : 11451 (Water Restrictions)

// http://uva.onlinejudge.org/external/114/11451.html
// Runtime: 0.124s
// Tag: Recursive, Dp, bitmask


// @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 <ctime>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

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

int l, s, sPos [10 + 2], c, maxFlow [10 + 2];
int bitMaskFilled [10 + 2] [10 + 2];
int maxFilled;

int minimum (int p, int q)
{
	if ( p < q ) return p;
	return q;
}

void recur (int at, int cLeft, int filled)
{
	if ( at == s || !cLeft ) {
		int cnt = 0;
		for ( int i = 0; i <= l; i++ )
			if ( filled & (1 << i) ) cnt++;
		if ( cnt > maxFilled ) maxFilled = cnt;
		return;
	}

	for ( int i = 0; i <= minimum (maxFlow [at], cLeft); i++ ) {
		recur (at + 1, cLeft - i, filled | bitMaskFilled [at] [i]);
	}
}

int main ()
{
	int testCase; scanf ("%d", &testCase);

	while ( testCase-- ) {
		scanf ("%d %d", &l, &s);

		for ( int i = 0; i < s; i++ ) scanf ("%d", &sPos [i]);

		scanf ("%d", &c);

		for ( int i = 0; i < s; i++ ) scanf ("%d", &maxFlow [i]);

		Set (bitMaskFilled, 0);

		int tmp;
		for ( int i = 0; i < s; i++ ) {
			for ( int j = 1; j <= maxFlow [i]; j++ ) {
				tmp = bitMaskFilled [i] [j - 1];
				tmp |= (1 << sPos [i]);
				tmp |= (1 << (sPos [i] + j));
				tmp |= (1 << (sPos [i] - j));
				bitMaskFilled [i] [j] = tmp;
			}
		}

		/*
		for ( int i = 0; i < s; i++ ) {
			for ( int j = 0; j <= maxFlow [i]; j++ ) printf ("%d ", bitMaskFilled [i] [j]);
			printf ("\n");
		}
		*/

		maxFilled = 0;

		recur (0, c, 0);

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

	return 0;
}

UVa : 11452 (Dancing the Cheeky-Cheeky)

// http://uva.onlinejudge.org/external/114/11452.html
// Runtime: 0.020s
// Tag: Adhoc, string 


// @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>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

int main() {
	int testCase;
	scanf("%d", &testCase);

	while (testCase--) {
		char inp[2000 + 10];
		scanf("%s", inp);

		int len = strlen(inp);
		string inpStr = inp;
		string basic;

		for (int i = len / 2; i >= 0; i--) {
			basic = inpStr.substr(0, i);
			string repeat = inpStr.substr(i, i);
			// cout << basic << " " << repeat << endl;
			if (basic == repeat)
				break;
		}

		int ind = basic.size() * 2;
		int basicInd = 0;

		while (ind < inpStr.size()) {
			ind++;
			basicInd++;
		}

		int output = 8;

		while (output) {
			cout << basic [basicInd % basic.size()];
			output--;
			basicInd++;
		}

		cout << "..." << endl;
	}

	return 0;
}

// @END_OF_SOURCE_CODE

UVa : 11420 (Chest of Drawers)

// link: http://uva.onlinejudge.org/external/114/11420.html
// Runtime: 0.364s
// Tag: Recur, dp


//============================================================================
// Name        : Test.cpp
// Author      : Shahab
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

// @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>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 50000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

enum State {UnLocked, Locked, SecureLocked};

LL dp [65 + 3] [3 + 2] [65 + 3];
int n, s;

LL recur (int at, State pre, int cntSecure)
{
	if ( at == n ) return cntSecure == s ? 1 : 0;

	if ( dp [at] [pre] [cntSecure] != -1 ) return dp [at] [pre] [cntSecure];

	LL c = 0;

	if ( pre == UnLocked ) {
		c += recur (at + 1, UnLocked, cntSecure);
		c += recur (at + 1, Locked, cntSecure);
	} else if ( pre == Locked ) {
		c += recur (at + 1, UnLocked, cntSecure);
		c += recur (at + 1, SecureLocked, cntSecure + 1);
	} else {
		c += recur (at + 1, UnLocked, cntSecure);
		c += recur (at + 1, SecureLocked, cntSecure + 1);
	}

	return dp [at] [pre] [cntSecure] = c;
}

int main ()
{
	while ( scanf ("%d %d", &n, &s) ) {
		if ( n < 0 && s < 0 ) break;

		Set (dp, -1);

		printf ("%lld\n", recur (0, Locked, 0));
	}

	return 0;
}

// @END_OF_SOURCE_CODE

UVa : 11418 (Clever Naming Patterns)

// http://uva.onlinejudge.org/external/114/11418.html
// Runtime: 0.012s
// Tag: String


//============================================================================
// Name        : Test.cpp
// Author      : Shahab
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

// @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>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 50000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

string str [26 + 3] [26 + 3];

int main ()
{
	int testCase; scanf ("%d", &testCase);
	int cases = 0;
	string tmp;

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

		bool isRowValid [26 + 3]; Set (isRowValid, true);
		bool isLetter [26 + 3] [26 + 3]; Set (isLetter, false);

		for ( int i = 0; i < n; i++ ) {
			int k; scanf ("%d", &k);
			for ( int j = 0; j < k; j++ ) {
				cin >> tmp;
				str [i] [j] = "";
				for ( size_t p = 0; p < tmp.size(); p++ ) str [i] [j] += tolower (tmp [p]);
				isLetter [i] [str [i] [j].at(0) - 'a'] = true;
			}
		}

		string output [26 + 3];

		for ( int i = 0; i < n; i++ ) {
			for ( int j = 0; j < n; j++ ) {
				int cnt = 0;
				int ind;
				for ( int k = 0; k < n; k++ )
					if ( isRowValid [k] && isLetter [k] [j]  ) { cnt++; ind = k; }

				if ( cnt == 1 ) {
					isRowValid [ind] = false;
					for ( int k = 0; k < n; k++ )
						if ( str [ind] [k].at (0) - 'a' == j ) { output [i] = str [ind] [k]; j = n; break; }
				}
			}
		}

		sort (output, output + n);
		printf ("Case #%d:\n", ++cases);
		for ( int i = 0; i < n; i++ ) {
			printf ("%c", toupper (output [i] [0]));
			for ( size_t j = 1; j < output [i].size(); j++ ) {
				printf ("%c", output [i] [j]);
			}
			printf ("\n");
		}

	}

	return 0;
}

// @END_OF_SOURCE_CODE