A solution for the Minesweeper problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10137.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.08

/* 
 * A solution for "The Trip" problem.
 * UVa ID: 10137
 */
#include <stdio.h>

int main (int argc, const char * argv[]) {
	/* number of students in the trip */
	long numOfStudents;
	
	/* the total sum of money spent */
	double total;
	
	/* the total amount of money to exchange in order to equalize */
	double exchange;
	
	/* the equalized trip amount to be payed by each student */
	double equalizedAmount;
	
	/* difference between the equalized amount and the amount spent */
	double diff;
	
	/* sum of all negative differences */
	double negativeSum;
	
	/* sum of all positive differences */
	double positiveSum;
	
	/* iterator */
	int i;
	
	while(scanf("%ld", &numOfStudents) != EOF) {
				
		/* 0, ends the program */
		if (!numOfStudents) {
			return 0;
		}
		
		/* keeps the amount of money spent by each student */
		double amountSpent[numOfStudents];		
		
		/* clean */
		total = 0;
		negativeSum = 0;
		positiveSum = 0;
				
		for (i = 0; i < numOfStudents; i++) {
			scanf("%lf\n", &amountSpent[i]);
			total += amountSpent[i];
		}
				
		equalizedAmount = total / numOfStudents;
		
		for (i = 0; i < numOfStudents; i++) {
			/* to ensure 0.01 precision */
			diff = (double) (long) ((amountSpent[i] - equalizedAmount) * 100.0) / 100.0;
			
			if (diff < 0) {
				negativeSum += diff;
			} else { 
				positiveSum += diff;
			}
		}

		/* when the total amount is even, these sums do not differ. otherwise, they differ in one cent */
		exchange = (-negativeSum > positiveSum) ? -negativeSum : positiveSum;
						
		/* output result */
		printf("$%.2lf\n", exchange);
	}

    return 0;
}

A solution for the Minesweeper problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10189.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.08

/* 
 * A solution for the Minesweeper problem.
 * UVa ID: 10189
 */
#include <stdio.h>

#define MINE '*'
#define MATRIX_OFFSET 1

int main (int argc, const char * argv[]) {
	/* number of lines of the mine field */
	long n;
	
	/* number of colums of the mine field */
	long m;
	
	/* iterators for retrieving the content of each field line*/
	long i, j;
	
	/* field number identifier */
	long fieldNumber = 0;

	while(scanf("%ld %ld", &n, &m) != EOF) {
			
		/* 0 0, ends the program */
		if (!n && !m) {
			return 0;
		} else {
			if (fieldNumber > 0) {
				/* 
				 * workaround for the extra line on the output, 
				 * which was giving me a Wrong Answer verdict..
				 * so only insert an extra line if there's more
				 * to come :-) 
				 */
				printf("\n");
			}
		}
		
		/* increment field id */
		fieldNumber++;
				
		/* a bidimensional array representing the input mine field */
		char inputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* a bidimensional array to output the mine field */
		int outputField[n + MATRIX_OFFSET + 1][m + MATRIX_OFFSET + 1];
		
		/* temporary variable to retrieve mine field lines */
		char line[m];
		
		/* init, O(n2) */
		for (i = 0; i < n + MATRIX_OFFSET + 1; i++) {
			for (j = 0; j < m + MATRIX_OFFSET + 1; j++) {
				outputField[i][j] = 0;
			}
		}
		
		/* read mine field, O(n2) */
		for (i = 0; i < n; i++) {
			scanf("%s\n",line);
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				inputField[i + MATRIX_OFFSET][j] = line[j - MATRIX_OFFSET];
			}
		}
		
		/* update output, O(n2) */ 
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE) {
				
					/* upper neighbours */
					outputField[i-1][j-1]++;
					outputField[i-1][j]++;
					outputField[i-1][j+1]++;
					
					/* same level neighbours */
					outputField[i][j-1]++;
					outputField[i][j+1]++;
					
					/* lower neighbours */
					outputField[i+1][j-1]++;
					outputField[i+1][j]++;
					outputField[i+1][j+1]++;
				}
			}
		}
		
		/* present output, O(n2) */
		printf("Field #%ld:\n",fieldNumber);
		for (i = MATRIX_OFFSET; i < n + MATRIX_OFFSET; i++) {
			for (j = MATRIX_OFFSET; j < m + MATRIX_OFFSET; j++) {
				if (inputField[i][j] == MINE)
					printf("%c", MINE);
				else	
					printf("%d",outputField[i][j]);
			}
			printf("\n");
		}

	}

    return 0;
}

// i can't get this to work. This seems to be the problem portion of the code.

//import random
# choose from a list
adam = random.choice([1,2])
print adam
input('press enter to continue');
if adam = 1:
    print 'you loose'
raw_input('press enter to exit')
if adam = 2:
    print 'you WIN!!'
raw_input('press enter to exit')

This is a dynamic-programming algorithm implementation for solving the the 0-1 Knapsack Problem in C.

Further explanation is given here.

#include <stdio.h>

#define MAXWEIGHT 100

int n = 3; /* The number of objects */
int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
				YOU PAY to take the object */
int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
				what YOU GET for taking the object */
int W = 10; /* The maximum weight you can take */ 

void fill_sack() {
	int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
				using at most i weight */
	int last_added[MAXWEIGHT]; /* I use this to calculate which object were
					added */
	int i, j;
	int aux;

	for (i = 0; i <= W; ++i) {
		a[i] = 0;
		last_added[i] = -1;
	}

	a[0] = 0;
	for (i = 1; i <= W; ++i)
		for (j = 0; j < n; ++j)
			if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
				a[i] = a[i - c[j]] + v[j];
				last_added[i] = j;
			}

	for (i = 0; i <= W; ++i)
		if (last_added[i] != -1)
			printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
		else
			printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);

	printf("---\n");

	aux = W;
	while ((aux > 0) && (last_added[aux] != -1)) {
		printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
		aux -= c[last_added[aux]];
	}

	printf("Total value added: %d$\n", a[W]);
}

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

	return 0;
}

This is the classic Greedy algorithm implementation for solving the Fractional Knapsack Problem in C.

Further explanations here

#include <stdio.h>

int n = 5; /* The number of objects */
int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
				YOU PAY to take the object */
int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
				what YOU GET for taking the object */
int W = 15; /* The maximum weight you can take */

void simple_fill() {
	int cur_w;
	float tot_v;
	int i, maxi;
	int used[10];

	for (i = 0; i < n; ++i)
		used[i] = 0; /* I have not used the ith object yet */

	cur_w = W;
	while (cur_w > 0) { /* while there's still room*/
		/* Find the best object */
		maxi = -1;
		for (i = 0; i < n; ++i)
			if ((used[i] == 0) &&
				((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
				maxi = i;

		used[maxi] = 1; /* mark the maxi-th object as used */
		cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
		tot_v += v[maxi];
		if (cur_w >= 0)
			printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
		else {
			printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
			tot_v -= v[maxi];
			tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
		}
	}

	printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}

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

	return 0;
}

Prints all valid ways to arrange n qeens on a n x n chessboard so that the qeens don't attack each other.

#include <iostream>
#include <vector>

typedef std::vector< int > Vect;
typedef std::vector< Vect > List;

const int n = 12;

bool checkRow(const Vect &v, int k) {
	for (int i = k - 1; i >= 0; --i)
		if (v[k] == v[i])
			return false;

	return true;
}

bool checkDiag(const Vect &v, int k) {
	for (int i = k - 1; i >= 0; --i)
		if (k - i == abs(v[k] - v[i]))
			return false;
	
	return true;
}

List filter(List l, int k) {
	List r;
	for (List::const_iterator it = l.begin(); it != l.end(); ++it) {
		if (checkRow(*it, k) && checkDiag(*it, k))
			r.push_back(*it);
	}
	
	return r;
}

List qeens(int k) {
	if (0 == k) {
		List l;
		l.push_back(Vect());
		return l;
	}
	
	List l = qeens(k - 1);
	List r;
	for (List::iterator it = l.begin(); it != l.end(); ++it) {
		for (int newRow = 1; newRow <= n; ++newRow) {
			Vect v(*it);
			v.push_back(newRow);
			r.push_back(v);
		}
	}
	
	r = filter(r, k - 1);
	
	return r;
}

void printS(List l) {
	for (List::const_iterator it = l.begin(); it != l.end(); ++it) {
		for (Vect::const_iterator jt = it->begin(); jt != it->end(); ++jt)
			std::cout << *jt << " ";
		std::cout << std::endl;
	}
}

int main(int argc, char *argv[]) {
	List l = qeens(n);
	
	printS(l);
	
	return 0;
}

For n = 8, builds
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 0
1 1 1 1 1 0 1 0
1 1 1 1 0 0 0 0
1 1 1 0 1 1 1 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0

The algorithm, for a n x n matrix is:
1. Split the matrix into 4 matrices of the same size
2. Complete the top-left one with 1
3. Repeat for each of the other 3 matrices.

#include <stdio.h>
#include <stdlib.h>

int n;
int **T;

void printM() {
	int i,
		j;
	printf("\n");
	for (i = 0; i < n; ++i) {
		for (j = 0; j < n; ++j)
			printf("%d ", T[i][j]);
		printf("\n");
	}
}

void fill(int x1, int y1, int x2, int y2) {
	printf("%d %d %d %d\n", x1, y1, x2, y2);
	//getchar();
	
	if (x1 == x2) {
		//T[x1][y1] = 1;
		return;
	}
	
	int i,
		j;
	int xm = (x1 + x2) / 2;
	int ym = (y1 + y2) / 2;
	for (i = y1; i <= ym; ++i)
		for (j = x1; j <= xm; ++j)
			T[i][j] = 1;
	
	fill(x1, ym + 1, xm, y2);
	fill(xm + 1, y1, x2, ym);
	fill(xm + 1, ym + 1, x2, y2);
}

int main(int argc, char *argv[]) {
	n = 8;
	T = (int**)malloc(n * sizeof(int*));
	int i;
	for (i = 0; i < n; ++i)
		T[i] = (int*)malloc(n * sizeof(int));
	
	int j;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			T[i][j] = 0;
	
	fill(0, 0, n - 1, n - 1);
	printM();
	
	return 0;
}