Online Judges

February 11, 2009 2 Comments

 

UVa Online Judge :

[ UVa Toolkit ]

Problem set : [ Official site ]

External Problem set:
 
 …/external/[volume number]/[problem number].html
 
 Problem number 100 :[ http://uva.onlinejudge.org/external/1/100.html ]

Volume wise Problem set:
 
 …vol=[volume number]
 
 For volume 1 :[ http://online-judge.uva.es/problemset/volume.php?vol=1 ]

Another site ( when UVa server down ) : [ http://isaac.lsu.edu/udv/ ]

Hints : [ Algorithmist ] & [ Steven Halim ]

[ Tools ]

[ Hunting Problems ]

[ Problem Rank list ]

[ Another Rank list ]

Total Solved: 176
 
 Ranking: 1917 [not updated] [ Page ]
 
 UVa online judge user id: 31371

 

Usaco :

[ Training ]
 
 [ Contest ]
 
 [ Forum ]

 

CodeChef :

[ Official site ]

 

TJU Online Judge :

[ Official site ]

Total Solved : 92
 
 Rank : 614 [not updated] [ Page ]

 

TopCoder :

[ Official site ]

 

IARCS :

Indian National Olympiad in Informatics

[ Problems ]

Test Data Given. Some solution can be found of particular problem.

 

Project Euler :

series of challenging mathematical/computer programming problems. After solving a problem, a discussion forum of respective problem will be opened.

[ Official site ]

Statistics : [ Bangladesh ]

Total Solved : 73

 

Sphere Online Judge :

[ Official site ]

 

Code Jam :

[ Official site ]

[ Source code ]

 

Saratov Online Judge :

[ Official site ]

 

Croatian Open Competition in Informatics :

[ Officail site ]

High School Programming Contest.
 
 Test data + Sample solutions + Editorials are available of previous contests.

 

Favorite Site/Blog :

[ One problem a day ]

[ Smilitude ]

[ Shafaet Planet ]

[ Young Programmer ]

[ Come on Code on ]

[ Ruet Programmer ]

[ Harsh ]

[ Puzzle ]

[ Quote ]

[ Php Tutorial ]

[ C/C++/Java/Bash/Asm Arena ]

Java Script Tutorial : [ Echo ] [ learn js ]

[ Cut the Knot ]

[ Combinatorial Game Theory ]

[ http://acmph.blogspot.com/ ]

[ http://opc.shaastra.org/ ]

[ http://dwite.ca/ ]

[ http://sp2hari.com/ ]

[ http://www.questtosolve.com/ ]

[ http://algoshare.blogspot.com/ ]                                                     

[ http://uvafcfm.wordpress.com/  ]        

 

Android:

Android for Beginners: [http://androidforbeginners.blogspot.com/ ]

Android Forum: [http://www.anddev.org/ ]

 

 Download Links of Some Essential Books:
 
 !!! [ Introduction to Algorithms. ]
 
 !!! [ Programming Challenges. ]
 
 !!! [ Art of Programming Contest. ] [Elementary Level]
 
 !!! [ Some Web-site Links ] by Saidul Islam

 


Filed under Common Tagged with

UVa : 497 (Strategic Defense Initiative )

January 5, 2012 Leave a Comment 


// 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

Filed under ACM (UVa) Algorithm

UVa : 913 (Joana and the Odd Numbers)

January 5, 2012 Leave a Comment 


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

Filed under ACM (UVa) Algorithm

USACO : Hamming Codes

December 29, 2011 1 Comment 

/*
ID: tausiq11
PROG: hamming
LANG: C++
 */

// @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 100000
#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, b) for( int i = 0; i < (b); i++ )
#define Fs(i, x) for( size_t i = 0; i < x.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)
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

int hammingDistance [255 + 3] [255 + 3];
int n, b, d;
vector <int> output;

void preGenerateValue ()
{
	int cnt;

	for ( int i = 0; i < 256; i++ ) {
		for ( int j = i; j < 256; j++ ) {
			cnt = 0;
			for ( int k = 0; k < 8; k++ ) {
				if ( (i & (1 << k)) ^ (j & (1 << k)) ) cnt++;
			}

			hammingDistance [i] [j] = hammingDistance [j] [i] = cnt;
		}
	}
}

bool findNextNumber (int p)
{
	Fs (i, output) {
		if ( hammingDistance [output [i]] [p] < d ) return false;
	}

	return true;
}

int main ()
{
	Rd ("hamming.in");
	Wt ("hamming.out");

	preGenerateValue ();

	scanf ("%d %d %d", &n, &b, &d);

	output.clear();
	output.push_back(0);

	int num = 1;

	while ( output.size() < n ) {
		while ( !findNextNumber (num) ) num++;
		output.push_back(num);
	}

	Fs (i, output) {
		if ( i % 10 != 0 ) printf (" ");
		printf ("%d", output [i]);
		if ( (i + 1) % 10 == 0 ) printf ("\n");
	}

	if ( output.size() % 10 != 0 ) printf ("\n");

	return 0;
}

// @END_OF_SOURCE_CODE

Filed under USACO

USACO : Healthy Holsteins

December 17, 2011 1 Comment 

/*
ID: tausiq11
PROG: holstein
LANG: C++
 */

// @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 100000
#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;

struct state {
	int arr [25 + 3];
	int step;
	int bitmask;
} a [32768 + 100];

int len;
int finalBitmask;
int finalBitCnt;

void checkBestSolution (int p)
{
	if ( finalBitCnt < a [p].step ) return;
	if ( finalBitCnt > a [p].step ) {
		finalBitCnt = a [p].step;
		finalBitmask = a [p].bitmask;
		return;
	}

	for ( int i = 0; i < 15; i++ ) {
		if ( (finalBitmask & (1 << i)) && !(a [p].bitmask & (1 << i)) ) return;
		if ( !(finalBitmask & (1 << i)) && (a [p].bitmask & (1 << i)) ) {
			finalBitCnt = a [p].step;
			finalBitmask = a [p].bitmask;
			return;
		}
	}
}

int main ()
{
	Rd ("holstein.in");
	Wt ("holstein.out");

	int v; scanf ("%d", &v);

	for ( int i = 0; i < v; i++ ) scanf ("%d", &a [0].arr [i]);
	a [0].step = 0;
	a [0].bitmask = 0;

	int g; scanf ("%d", &g);
	int temp [25 + 3];

	len = 1;
	finalBitCnt = g;
	finalBitmask = (1 << g) - 1;

	for ( int i = 0; i < g; i++ ) {
		for ( int j = 0; j < v; j++ ) scanf ("%d", &temp [j]);

		for ( int j = 0; j < len; j++ ) {

			bool allSet = true;
			a [len + j].step = a [j].step + 1;
			a [len + j].bitmask = a [j].bitmask | (1 << i);

			for ( int k = 0; k < v; k++ ) {
				a [len + j].arr [k] = a [j].arr [k] - temp [k];

				if ( a [len + j].arr [k] > 0 ) allSet = false;
			}

			if ( allSet ) {
				checkBestSolution (len + j);
			}
		}

		len *= 2;
	}

	printf ("%d", finalBitCnt);

	for ( int i = 0; i < g; i++ ) {
		if ( finalBitmask & (1 << i) ) printf (" %d", i + 1);
	}

	printf ("\n");

	return 0;
}

// @END_OF_SOURCE_CODE

Filed under USACO

USACO : Sorting a Three-Valued Sequence

December 8, 2011 1 Comment 


/*
ID: tausiq11
PROG: sort3
LANG: C++
 */

// @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 100000
#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 ()
{
	Rd ("sort3.in");
	Wt ("sort3.out");

	int n; scanf ("%d", &n);
	int a [1000 + 10];
	int freq [3 + 2]; Set (freq, 0);

	for ( int i = 0; i < n; i++ ) {
		scanf ("%d", &a [i]);
		freq [a [i]]++;
	}

	int groupFreq [3 + 2] [3 + 2]; Set (groupFreq, 0);
	int len = 0;

	for ( int i = 1; i <= 3; i++ ) {
		for ( int j = 0; j < freq [i]; j++ ) {
			groupFreq [i] [a [len]]++;
			len++;
		}
	}

	int cnt = 0;
	int mini;

	// reduce '2' from group 1
	mini = min (groupFreq [1] [2], groupFreq [2] [1]);
	groupFreq [1] [2] -= mini;
	groupFreq [2] [1] -= mini;
	groupFreq [1] [1] += mini;
	groupFreq [2] [2] += mini;
	cnt += mini;

	// reduce '3' from group 1
	mini = min (groupFreq [1] [3], groupFreq [3] [1]);
	groupFreq [1] [3] -= mini;
	groupFreq [3] [1] -= mini;
	groupFreq [1] [1] += mini;
	groupFreq [3] [3] += mini;
	cnt += mini;

	mini = freq [1] - groupFreq [1] [1];
	cnt += mini;
	groupFreq [1] [1] = freq [1];
	groupFreq [2] [1] = groupFreq [3] [1] = 0;
	groupFreq [3] [2] += groupFreq [1] [2];
	groupFreq [2] [3] += groupFreq [1] [3];
	groupFreq [1] [2] = groupFreq [1] [3] = 0;
	cnt += groupFreq [2] [3];

	printf ("%d\n", cnt);


	return 0;
}

// @END_OF_SOURCE_CODE

Filed under USACO

USACO : Ordered Fractions

November 29, 2011 1 Comment 


/*
ID: tausiq11
PROG: frac1
LANG: C++
 */

// @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 100000
#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;

struct node {
	int numerator;
	int demonimator;
	int val;
};

node a [N];
int len;
int n;

int gcd (int p, int q)
{
	if ( q == 0 ) return p;
	return gcd (q, p % q);
}

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

int main ()
{
	Rd ("frac1.in");
	Wt ("frac1.out");

	scanf ("%d", &n);

	a [0].numerator = 0;
	a [0].demonimator = 1;
	a [0].val = 0;

	a [1].numerator = 1;
	a [1].demonimator = 1;
	a [1].val = 100000000;

	len = 2;

	for ( int i = 1; i < n; i++ ) {
		for ( int j = i + 1; j <= n; j++ ) {
			if ( gcd (i, j) == 1 ) {
				a [len].numerator = i;
				a [len].demonimator = j;
				a [len].val = (int) (((double)i / (double)j) * 100000000.0);
				len++;
			}
		}
	}

	sort (a, a + len, cmp);

	for ( int i = 0; i < len; i++ ) {
		printf ("%d/%d\n", a [i].numerator, a [i].demonimator);
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Filed under USACO

USACO : The Castle

November 28, 2011 1 Comment 


/*
ID: tausiq11
PROG: castle
LANG: C++
 */

// @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 50
#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 direction { West = 1, North = 2, East = 4, South = 8 };

int width, height;

int maze [N + 2] [N + 2];
vector <int> matrix [N * N + 5];
bool vis [N * N + 5];
int numberOfComponent;
int component [N * N + 5];
int componentFrequency [N * N + 5];
int dr [] = {-1, 0, 1, 0};
int dc [] = {0, 1, 0, -1};
int maxSizedRoom;
int resW, resH;
char resDir;

void reset ()
{
	int cnt = 1;

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) maze [i] [j] = cnt++;
	}

	Set (vis, false);
	numberOfComponent = 0;
	Set (componentFrequency, 0);
	maxSizedRoom = -1;
}

void checkByRemove (int p, int q)
{
	int freq = -1;

	// printf ("%d\n", maze [p] [q]);

	if ( p != 0 && component [maze [p] [q]] != component [maze [p - 1] [q]] ) {
		freq = componentFrequency [component [maze [p] [q]]] + componentFrequency [component [maze [p - 1] [q]]];
		if ( freq > maxSizedRoom ) {
			maxSizedRoom = freq;
			resW = q; resH = p; resDir = 'N';
		}
	}
	if ( q != width - 1 && component [maze [p] [q]] != component [maze [p] [q + 1]] ) {
		freq = componentFrequency [component [maze [p] [q]]] + componentFrequency [component [maze [p] [q + 1]]];
		if ( freq > maxSizedRoom ) {
			maxSizedRoom = freq;
			resW = q; resH = p; resDir = 'E';
		}
	}
}

void dfs (int node, int c)
{
	if ( vis [node] ) return;
	vis [node] = true;
	component [node] = c;

	for ( size_t i = 0; i < matrix [node].size (); i++ ) {
		dfs (matrix [node] [i], c);
	}
}

void print ()
{
	for ( int i = 1; i <= 28; i++ ) {
		printf ("%d -> ", i);
		for ( size_t j = 0; j < matrix [i].size(); j++ ) {
			printf ("%d ", matrix [i] [j]);
		}
		printf ("\n");
	}
}

void print2 ()
{
	for ( int i = 1; i <= 28; i++ ) {
		printf ("%d -> %d\n", i, component [i]);
	}
}

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

	scanf ("%d %d", &width, &height);
	int inp;

	reset ();

	bool dir [4];

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) {
			scanf ("%d", &inp);
			dir [0] = dir [1] = dir [2] = dir [3] = true;
			for ( int k = 8; k >= 1; k /= 2 ) {
				if ( inp >= k ) {
					switch (k) {
					case 8: dir [0] = false; break;
					case 4: dir [1] = false; break;
					case 2: dir [2] = false; break;
					case 1: dir [3] = false; break;
					}
					inp -= k;
				}
			}

			if ( dir [0] ) matrix [maze [i] [j]].push_back(maze [i + 1] [j]);
			if ( dir [1] ) matrix [maze [i] [j]].push_back(maze [i] [j + 1]);
			if ( dir [2] ) matrix [maze [i] [j]].push_back(maze [i - 1] [j]);
			if ( dir [3] ) matrix [maze [i] [j]].push_back(maze [i] [j - 1]);
		}
	}

	// print ();

	for ( int i = 0; i < height; i++ ) {
		for ( int j = 0; j < width; j++ ) {
			if ( !vis [maze [i] [j]] ) {
				dfs (maze [i] [j], ++numberOfComponent);
			}
		}
	}

	// print2 ();


	printf ("%d\n", numberOfComponent); // number of room

	for ( int i = 0; i < N * N + 2; i++ ) {
		componentFrequency [component [i]]++;
	}

	int largestComponent = -1;

	for ( int i = 1; i <= numberOfComponent; i++ ) {
		largestComponent = max (largestComponent, componentFrequency [i]);
	}

	printf ("%d\n", largestComponent);	// largest room

	for ( int j = 0; j < width; j++ ) {
		for ( int i = height - 1; i >= 0; i-- ) {
			checkByRemove (i, j);
		}
	}

	printf ("%d\n%d %d %c\n", maxSizedRoom, resH + 1, resW + 1, resDir);

	return 0;
}

// @END_OF_SOURCE_CODE

Filed under USACO

UVa : 11451 (Water Restrictions)

November 24, 2011 Leave a Comment 


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

Filed under ACM (UVa) Algorithm

UVa : 11452 (Dancing the Cheeky-Cheeky)

November 20, 2011 Leave a Comment 


// 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

Filed under ACM (UVa) Algorithm

Timus : 1131 (Copying)

November 11, 2011 Leave a Comment 


// http://acm.timus.ru/problem.aspx?space=1&num=1131
// runtime: 0.015s
// tag: math


#include <stdio.h>
#include <math.h>

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

	int hrs = 0;
	int activePc = 1;

	while ( true ) {
		if ( activePc <= k ) activePc *= 2;
		hrs++;

		if ( activePc >= n ) break;

		if ( k < activePc ) {
			hrs += (int) ceil ((n - activePc) / (double) k);
			break;
		}
	}

	printf ("%d\n", hrs);

	return 0;
}

Filed under Timus Online Judge

← Older posts

Follow

Get every new post delivered to your Inbox.

Join 40 other followers