<bitfield.h>
// This class is a code snippet, it can be freely used and distributed.
// Author: irfan[dot]hamid[at]gmail[dot]com
//
// Bit fields are a widely used mechanism in computing applications.
// Typical applications include memory allocators and Bloom filters. This class
// provides a generic bit field implementation for an arbitrary number of bits.
//
// Implementation notes:
// The use of C++ allows the clean separation of the data structure from the
// interface. The bit field is implemented as a vector of unsigned int that is
// allocated at object creation.
//
// field: The vector that represents the bit field itself
// bit_count: The total number of bits in the bit field

#ifndef __BITFIELD_H__
#define __BITFIELD_H__
#include <math.h>
#define SZ_UINT sizeof(unsigned int)

class Bitfield
{
protected:
	unsigned int *field;
	unsigned int bit_count;

public:
	Bitfield (int bc);
	~Bitfield ();

	int set (int bit);
	int get (int bit);
	int reset (int bit);
};

#endif
</bitfield.h>

<bitfield.cpp>
#include <stdlib.h>
#include "bitfield.h"

// The constructor takes an int param which gives the number of bits in this
// bit field.
Bitfield::Bitfield (int bc)
{
	bit_count = bc;

	// E.g, ceil(257/32*8) = 65, 64 ints fully used, last one partially used
	field = (unsigned int*) malloc(((int) ceil(bc/SZ_UINT*8)));
}

Bitfield::~Bitfield ()
{
	if (field)
		free(field);
}

// This function sets the corresponding bit in the field equal to 1.
//
// Returns: 0 on success, -1 on error.
int Bitfield::set (int bit)
{
	// Sanity check
	if (bit >= bit_count || !field)
		return -1;

	// The correct index into the vector will be given by bit/SZ_UNIT. The
	// index into the correct vector element is given by bit%SZ_UNIT, to
	// achieve this, simply left shift 0x01 the appropriate number of times.
	field[bit/SZ_UINT] |= (0x00000001 << (bit%(SZ_UINT*8)-1));
	return 0;
}

// This function sets the corresponding bit in the field equal to 0.
//
// Returns: 0 on success, -1 on error.
int Bitfield::reset (int bit)
{
	if (bit >= bit_count || !field)
		return -1;
	field[bit/SZ_UINT] &= ~(0x00000001 << (bit%(SZ_UINT*8)-1));
	return 0;
}

// This function returns the value of the corresponding bit.
//
// Returns: The value of the bit, if the field is initialized and bit index is
// within bounds, -1 otherwise.
int Bitfield::get (int bit)
{
	if (bit >= bit_count || !field)
		return -1;
	return (field[bit/SZ_UINT] & (0x00000001 << (bit%(SZ_UINT*8)-1)) ? 1 : 0);
}
</bitfield.cpp>

/******************************************************************************
 * This function is a code snippet. It can be freely used and distributed.
 * Author: irfan[dot]hamid[at]gmail[at]com
 *
 * This function takes two ASCII strings in C syntax (null-terminated
 * character arrays) and determines whether they are anagrams or not.
 *
 * Implementation notes:
 * The function contains a histogram that stores the frequency of each 
 * character it encounters in the first string. For each character of the 
 * second string, it decrements the corresponding entry in the histogram. If 
 * before every decrement, the value of the histogram bucket reaches zero, 
 * then the two strings are not anagrams, as there is some character that has
 * more occurrences in the second string than in the first string.
 *
 * If either of the two strings contains a non-alphabetic character, the
 * anagram property is considered to be violated.
 *
 * Remarks:
 * It is an efficient implementation because:
 *   o It is in-place, the original strings are not copied, no alloc or copy
 *   o Does not clobber the original strings
 *   o It is a linear time implementation
 *
 * Returns:
 * True if the strings are anagrams, false otherwise.
******************************************************************************/

bool is_anagram (char w1[], char w2[])
{
	unsigned int i, sz;

	/* The histogram */
	int freqtbl[26];

	/* Sanity check */
	if ((sz = strlen(w1)) != strlen(w2))
		return false;

	/* Initialize the histogram */
	bzero(freqtbl, 26*sizeof(int));

	/* Read the first string, incrementing the corresponding histogram entry */
	for (i = 0; i < sz; i++) {
		if (w1[i] >= 'A' && w1[i] <= 'Z')
			freqtbl[w1[i]-'A']++;
		else if (w1[i] >= 'a' && w1[i] <= 'z')
			freqtbl[w1[i]-'a']++;
		else
			return false;
	}

	/* Read the second string, decrementing the corresponding histogram entry */
	for (i = 0; i < sz; i++) {
		if (w2[i] >= 'A' && w2[i] <= 'Z') {
			if (freqtbl[w2[i]-'A'] == 0)
				return false;
			freqtbl[w2[i]-'A']--;
		} else if (w2[i] >= 'a' && w2[i] <= 'z') {
			if (freqtbl[w2[i]-'a'] == 0)
				return false;
			freqtbl[w2[i]-'a']--;
		} else {
			return false;
		}
	}

	return true;
}

void dijkstra2(int s) {
	int queue[GRAPHSIZE];
	char inQueue[GRAPHSIZE];
	int begq = 0,
	    endq = 0;
	int i, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d2[i] = INFINITY;
		visited[i] = 0; /* the i-th element has not yet been visited */
		inQueue[i] = 0;
	}

	d2[s] = 0;
	queue[endq] = s;
	endq = (endq + 1) % GRAPHSIZE;


	while (begq != endq) {
		mini = queue[begq];
		begq = (begq + 1) % GRAPHSIZE;
		inQueue[mini] = 0;

		visited[mini] = 1;

		for (i = 1; i <= n; ++i)
			if (dist[mini][i])
				if (d2[mini] + dist[mini][i] < d2[i]) { 
					d2[i] = d2[mini] + dist[mini][i];
					if (!inQueue[i]) {
						queue[endq] = i;
						endq = (endq + 1) % GRAPHSIZE;
						inQueue[i] = 1;
					}
				}
	}
}

#include <stdio.h>

int n;
float a[10][11];

void forwardSubstitution() {
	int i, j, k, max;
	float t;
	for (i = 0; i < n; ++i) {
		max = i;
		for (j = i + 1; j < n; ++j)
			if (a[j][i] > a[max][i])
				max = j;
		
		for (j = 0; j < n + 1; ++j) {
			t = a[max][j];
			a[max][j] = a[i][j];
			a[i][j] = t;
		}
		
		for (j = n; j >= i; --j)
			for (k = i + 1; k < n; ++k)
				a[k][j] -= a[k][i]/a[i][i] * a[i][j];

/*		for (k = 0; k < n; ++k) {
			for (j = 0; j < n + 1; ++j)
				printf("%.2f\t", a[k][j]);
			printf("\n");
		}*/
	}
}

void reverseElimination() {
	int i, j;
	for (i = n - 1; i >= 0; --i) {
		a[i][n] = a[i][n] / a[i][i];
		a[i][i] = 1;
		for (j = i - 1; j >= 0; --j) {
			a[j][n] -= a[j][i] * a[i][n];
			a[j][i] = 0;
		}
	}
}

void gauss() {
	int i, j;

	forwardSubstitution();
	reverseElimination();
	
	for (i = 0; i < n; ++i) {
		for (j = 0; j < n + 1; ++j)
			printf("%.2f\t", a[i][j]);
		printf("\n");
	}
}

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

	FILE *fin = fopen("gauss.in", "r");
	fscanf(fin, "%d", &n);
	for (i = 0; i < n; ++i)
		for (j = 0; j < n + 1; ++j)
			fscanf(fin, "%f", &a[i][j]);
	fclose(fin);
	
	gauss();
	
	return 0;
}

#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */

void printD() {
	int i;
	for (i = 1; i <= n; ++i)
		printf("%10d", i);
	printf("\n");
	for (i = 1; i <= n; ++i) {
		printf("%10ld", d[i]);
	}
	printf("\n");
}

void dijkstra(int s) {
	int i, k, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d[i] = INFINITY;
		visited[i] = 0; /* the i-th element has not yet been visited */
	}

	d[s] = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
				mini = i;

		visited[mini] = 1;

		for (i = 1; i <= n; ++i)
			if (dist[mini][i])
				if (d[mini] + dist[mini][i] < d[i]) 
					d[i] = d[mini] + dist[mini][i];
	}
}

int main(int argc, char *argv[]) {
	int i, j;
	int u, v, w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &e);
	for (i = 0; i < e; ++i)
		for (j = 0; j < e; ++j)
			dist[i][j] = 0;
	n = -1;
	for (i = 0; i < e; ++i) {
		fscanf(fin, "%d%d%d", &u, &v, &w);
		dist[u][v] = w;
		n = MAX(u, MAX(v, n));
	}
	fclose(fin);

	dijkstra(1);

	printD();

	return 0;
}

#include <stdio.h>

typedef struct {
	int u, v, w;
} Edge;

int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[1024]; /* large enough for n <= 2^5=32 */
int d[32]; /* d[i] is the minimum distance from node s to node i */

#define INFINITY 10000

void printDist() {
	int i;

	printf("Distances:\n");

	for (i = 0; i < n; ++i)
		printf("to %d\t", i + 1);
	printf("\n");

	for (i = 0; i < n; ++i)
		printf("%d\t", d[i]);

	printf("\n\n");
}

void bellman_ford(int s) {
	int i, j;

	for (i = 0; i < n; ++i)
		d[i] = INFINITY;

	d[s] = 0;

	for (i = 0; i < n - 1; ++i)
		for (j = 0; j < e; ++j)
			if (d[edges[j].u] + edges[j].w < d[edges[j].v])
				d[edges[j].v] = d[edges[j].u] + edges[j].w;
}

int main(int argc, char *argv[]) {
	int i, j;
	int w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &n);
	e = 0;

	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j) {
			fscanf(fin, "%d", &w);
			if (w != 0) {
				edges[e].u = i;
				edges[e].v = j;
				edges[e].w = w;
				++e;
			}
		}
	fclose(fin);

	/* printDist(); */

	bellman_ford(0);

	printDist();

	return 0;
}

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

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

#include <stdio.h>

int n; /* Then number of nodes */
int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
			it exists, or 0 if it does not */

void printDist() {
	int i, j;
	printf("    ");
	for (i = 0; i < n; ++i)
		printf("%4c", 'A' + i);
	printf("\n");
	for (i = 0; i < n; ++i) {
		printf("%4c", 'A' + i);
		for (j = 0; j < n; ++j)
			printf("%4d", dist[i][j]);
		printf("\n");
	}
	printf("\n");
}

/*
	floyd_warshall()

	after calling this function dist[i][j] will the the minimum distance
	between i and j if it exists (i.e. if there's a path between i and j)
	or 0, otherwise
*/
void floyd_warshall() {
	int i, j, k;
	for (k = 0; k < n; ++k) {
		printDist();
		for (i = 0; i < n; ++i)
			for (j = 0; j < n; ++j)
				/* If i and j are different nodes and if 
					the paths between i and k and between
					k and j exist, do */
				if ((dist[i][k] * dist[k][j] != 0) && (i != j))
					/* See if you can't get a shorter path
						between i and j by interspacing
						k somewhere along the current
						path */
					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
						(dist[i][j] == 0))
						dist[i][j] = dist[i][k] + dist[k][j];
	}
	printDist();
}

int main(int argc, char *argv[]) {
	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &n);
	int i, j;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			fscanf(fin, "%d", &dist[i][j]);
	fclose(fin);

	floyd_warshall();

	return 0;
}

#include <stdio.h>

/*
	The input file (weight.txt) look something like this
		4
		0 0 0 21
		0 0 8 17
		0 8 0 16
		21 17 16 0

	The first line contains n, the number of nodes.
	Next is an nxn matrix containg the distances between the nodes
	NOTE: The distance between a node and itself should be 0
*/

int n; /* The number of nodes in the graph */

int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
			if there is no path between i and j, weight[i][j] should
			be 0 */

char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
			spanning tree; 0 otherwise*/

int d[100]; /* d[i] is the distance between node i and the minimum spanning
		tree; this is initially infinity (100000); if i is already in
		the tree, then d[i] is undefined;
		this is just a temporary variable. It's not necessary but speeds
		up execution considerably (by a factor of n) */

int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
			linked to in order to get a distance of d[i] */

/* updateDistances(int target)
	should be called immediately after target is added to the tree;
	updates d so that the values are correct (goes through target's
	neighbours making sure that the distances between them and the tree
	are indeed minimum)
*/
void updateDistances(int target) {
	int i;
	for (i = 0; i < n; ++i)
		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
			d[i] = weight[target][i];
			whoTo[i] = target;
		}
}

int main(int argc, char *argv[]) {
	FILE *f = fopen("dist.txt", "