DZone Snippets: uva code

A solution for the "Carmichael Numbers" problem

jmftrindade (Joana M. F. da Trindade) — Thu, 24 Apr 2008 23:16:02 GMT

A solution for the "Carmichael Numbers" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10006.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.24



/* 

 * Solution for "Carmichael Numbers" problem.

 * UVa ID: 10006

 */

#include 

#include 



#define MAXPRIME 65001



using namespace std;



/*

 * Modular exponentiation algorithm. Returns b^e mod m.

 */

unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) {

    unsigned long long r = 1;

    while (e > 0) {

        if ((e & 1) == 1) {

	    r = (r * b) % m;

        }

        e >>= 1;

        b = (b * b) % m;

    }

    return r;

}



/* 

 * Generates all prime numbers up to MAXPRIME. Based on

 * the Sieve of Eratosthenes.

 */

void gen_primes(bool p[]) {

    p[0] = p[1] = false;

	

    /* 

     * starting at number 2 and going to the upper limit, mark 

     * all numbers as potential primes 

     */  

    for (int i=2; i        p[i] = true;

    }

	

    int m = floor(sqrt(MAXPRIME));

    int n;

    /* 

     * mark all multiples of a prime as non-primes. this has to be done for primes 

     * only up to the square root, since every number in the array has at least 

     * one factor smaller than the square root of the limit. 

     */

    for (int i=2; i        if (p[i]) {

       	    n = MAXPRIME / i;

	    for (int j=2; j<=n; j++) {

	        p[i * j] = false;

	    }

	}

    }

}



/* generates all carmichael numbers up to the given limit by performing the fermat test */

void gen_carmi(bool c[], bool p[]) {



    /* initialize carmichael numbers array with false */

    memset(c, 0, MAXPRIME * sizeof(bool));

	

    /* 

     * starting from the first non-prime, mark all 

     * odd numbers as potential carmichael numbers 

     */

    for (int i=9; i	c[i] = true;

    }

	

    /* 

     * again, for all odd numbers, we exclude the primes and perform

     * the fermat test for 2 <= a <= n-1.

     */

    for (int n=9; n	/* VERY IMPORTANT! check first if this number is prime, otherwise we get TLE */

	if (p[n]) {

	    c[n] = false;

	    continue;

	}

	for (int a=2; a<=n-1; a++) {

	    if (fast_mod_pow(a,n,n) != a) {

	        c[n] = false;

		break;

	    } 

	}	

    }

}



/* main */

int main() {

    unsigned long long n; /* number */

    unsigned long long a; /* a of the fermat test */

    bool prime[MAXPRIME]; /* prime numbers array */

    bool carmi[MAXPRIME]; /* carmichael numbers array */

	

    gen_primes(prime);

    gen_carmi(carmi, prime);

	

    while (cin >> n && (n != 0)) {	

        if (carmi[n]) {

            cout << "The number " << n << " is a Carmichael number." << endl;

        } else {

            cout << n << " is normal." << endl;

        }

    }

    return 0;

}

A solution for the "Binomial Showdown" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:43:03 GMT

A solution for the "Binomial Showdown" problem.

Problem description:
http://acm.uva.es/p/v5/530.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.11



/*

 * Solution for the "Binomial Showdown" problem.

 * UVa ID: 530

 */



#include 



using namespace std;



/* main */

int main() {

    int n, k;

    unsigned long long r; /* result */



    while(cin >> n >> k && ((n != 0) || (k != 0))) {

        /* init result */

        r = 1;



        /* if k is more than half of n, then use the complement */

        if(k > (n / 2)) {

            k = n - k;

        }



        /*         

         * C(n,k) = n! / (k!(n-k)!) =

         * (n)(n-1)(...)(n-k+1) / 2*3*4*(...)*k

         */ 

        for (int i=0; i            r = r * (n - i);   /* (n)(n-1)(...)(n-k+1) */

            r = r / (1 + i);   /* 2*3*4*(...)*k */

        }

        cout << r << endl;

    }

}

A solution for the "Reverse and Add" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:38:45 GMT

A solution for the "Reverse and Add" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10018.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.14



/*

 * Solution for the "Reverse and Add" problem.

 * UVa ID: 10018

 */

#include 



#define NDIGITS 100



using namespace std;



/* returns the reversed number */

unsigned long long reverse(unsigned long long number) {

	unsigned long long m = 0; /* reversed number */

	int digits[NDIGITS]; /* digits array */

	int pos = 0, power = 1;

	

	/* init */

	for (int i=0; i		digits[i] = 0;

	}

	

	/* retrieve all digits */

	while (number > 0) {

		digits[pos++] = number % 10;

		number = number / 10;

	}



	/* multiply the reversed digits by the powers of ten */

	for (int i=pos-1; i>=0; i--) {

		m += power * digits[i];

		power *= 10;

	}

	

	return m;

}



/* main */

int main() {

	int nc; /* number of cases */

	int m; /* minimum number of iterations */

	unsigned long long n; /* number */

	

	cin >> nc;

	

	/* reverse and add.. */

	for (int i=0; i		cin >> n;

		m = 0;

		while (true) {

			if (reverse(n) == n) {

				break;

			} else {

				n += reverse(n);

				m++;

			}

		}

		cout << m << " " << n << endl;

	}

	

	return 0;

}

A solution for the "Primary Arithmetic" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:21:01 GMT

A solution for the "Primary Arithmetic" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10035.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.04



/**

 * Solution for the "Primary Arithmetic" problem.

 * UVa ID: 10035

 */ 

#include  

#include  



using namespace std; 



int main() {

    unsigned long long n1; /* 1st number */ 

    unsigned long long n2; /* 2nd number */ 

    int carry = 0; /* carry */ 

    int sum = 0; /* temporary sum */ 

    int count = 0; /* carry counter */ 



    while(cin >> n1 >> n2 && ((n1 > 0) || (n2 > 0))) { 

        carry = 0; 

	count = 0; 

	sum = 0; 



	/* while there's still something.. */ 

	while ((n1 > 0) || (n2 > 0)) { 

	    /* sum the two right-most digits */ 

	    sum = carry + (n1 % 10) + (n2 % 10); 



	    if (sum >= 10) { 

		count++; 

	    } 

			

	    /* get the carry by dividing the sum of the two digits */ 

	    carry = sum / 10; 



	    /* 'reduce' the numbers by ten, to update the right-most digits */ 

	    n1 /= 10; 

            n2 /= 10; 

	} 

		

	if (count == 0) { 

            cout << "No carry operation." << endl; 

	} else if (count == 1) { 

	    cout << "1 carry operation." << endl; 

	} else { 

            cout << count << " carry operations." << endl; 

        } 

    } 



    return 0;

}

A solution for the "Shoemaker" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 01:02:22 GMT

A solution for the "Shoemaker" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10026.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.06



/* 

 * Solution for "Shoemaker" problem.

 * UVa ID: 10026

 */

#include 



#define NJOBS 1000



using namespace std;



int jobs[NJOBS]; /* jobs */

double p[NJOBS]; /* priority */



/* main */

int main() {

    int nc;	/* number of cases */

	int nj; /* number of jobs */

	int ct;	/* completion time */

	int dp; /* daily penalty */

	

    cin >> nc;

	

	/* for each test case.. */

    for (int i=0; i		cin >> nj;

		

		/* init input */

		for (int i=0; i			cin >> ct >> dp;

			jobs[i] = i;

			/* priority is daily penalty divided by completion time (minimal fine) */

			p[i] = double(dp) / ct;

		}

		

		int j, k, tmp;

		

		/* sort jobs by priority */

		for (int i=0; i			for (j=i+1, k=i; j				if( (p[jobs[j]] > p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] < jobs[k])) ) {

					k=j;

				}

			}

			tmp = jobs[i]; 

			jobs[i] = jobs[k]; 

			jobs[k] = tmp;

		}

		

		/* output */

		for (int i=0; i			if(i > 0) { 

				cout << " ";

			}

			cout << jobs[i] + 1;

		}

		cout << endl;

		if (i < nc-1) {

			cout << endl;

		}

    }

	

    return 0;

}

A solution for the "Stack 'em Up" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 00:29:21 GMT

A solution for the "Stack 'em Up" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/102/10205.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.05



/* 

 * Solution for "Stack 'em Up" problem.

 * UVa ID: 10205

 */

#include 



#define NVALUES 13

#define NSUITS 4

#define NCARDS 52

#define NSHUFFLES 100

#define WSIZE 9



using namespace std;



char values[NVALUES][WSIZE] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};

char suits[NSUITS][WSIZE] = {"Clubs", "Diamonds", "Hearts", "Spades"};

int shuffles[NSHUFFLES][NCARDS];

int deck[NCARDS];



/* read all dealer shuffles */

void read_shuffles(int n_shuff) {

	for(int i=0; i		for (int j=0; j			cin >> shuffles[i][j];

		}

	}

}



/* shuffle the deck with one of the known shuffles */

void shuffle_deck(int s_id) {

	int tmpdeck[NCARDS];

	for (int i=0; i		tmpdeck[i] = deck[shuffles[s_id][i] - 1];

	}

	for (int i=0; i		deck[i] = tmpdeck[i];

	}

}



/* main */

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

	int nc; /* number of cases */

	int ns;	/* number of shuffles */

	int s; /* current shuffle */

		

	cin >> nc;

		

	for (int i=0; i		cin >> ns;

			

		/* initialize deck */

		for (int p=0; p			deck[p] = p;

		}

		

		/* read list of known shuffles */

		read_shuffles(ns);

		

		/* shuffle deck */

		for (int j=0; j			cin >> s;

			shuffle_deck(s - 1);

		}



		/* print deck */

		for (int k=0; k			cout << values[deck[k] % NVALUES] << " of " << suits[deck[k] / NVALUES] << endl;

		}

		if (i < (nc - 1)) {

			cout << endl;

		}

	}

	

}

A solution for the "Hartals" problem

jmftrindade (Joana M. F. da Trindade) — Mon, 14 Apr 2008 00:21:58 GMT

A solution for the "Hartals" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10050.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.06



/* 

 * Solution for the "Hartals" problem.

 * UVa ID: 10050

 */

#include 

 

#define NDAYS 3651

 

using namespace std;



/* simulation time (in days) */

int st[NDAYS]; 

 

/* main */

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

	int nc; /* number of cases */

	int nd; /* number of days */

	int np; /* number of political parties */

	int h; /* current hartal number */

	int dl;	/* days lost */

	

	cin >> nc;

	

	/* for each case.. */

	for (int i=0; i		cin >> nd;

		cin >> np;		

		

		/* initialize simulation table */

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

			st[j] = 0;

		}

		dl = 0; /* init days lost counter */

		

		/* update with hartal for each party */

		for (int j=0; j			cin >> h;

			for (int k=1; k*h-1<=nd; k++) {

				st[k*h-1] = 1; /* set lost day flag */

			}

		}

		

		/* calculate number of days lost */

		for (int j=0; j			/* if it's not a friday or a saturday */

			if ((j%7 != 5) && (j%7 != 6) && (st[j] == 1)) {

				dl++;

			}

		}

		cout << dl << endl;

	}

	

}

A solution for the "Interpreter" problem

jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:26:35 GMT

A solution for the "Interpreter" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10033.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.16



/* 

 * Solution for the "Interpreter" problem.

 * UVa ID: 10033

 */

#include 



#define MAX_REG 10

#define MAX_RAM 1000



int pointer;

int regArray[MAX_REG];

int ram[MAX_RAM];



/* initialize registers and ram */

int init() {

	int i;

	for (i = 0; i < MAX_REG; i++) {

		regArray[i] = 0;

	}

	for (i = 0; i < MAX_RAM; i++) {

		ram[i] = 0;

	}

	

}



/* decode instruction */

int decode() {

	int command, a1, a2;

	command = ram[pointer] / 100;

	a1 = (ram[pointer] % 100) / 10;

	a2 = ram[pointer] % 10;

	

	switch (command) {

		/* halt */

		case 1 :		

			return 0;

			break;

			

		/* set register a1 to a2 */

		case 2 :

			regArray[a1] = a2;

			pointer++;

			break;

			

		/* add a2 to register a1 */

		case 3 :

			regArray[a1] = (regArray[a1] + a2) % 1000;

			pointer++;

			break;

			

		/* multiply register a1 by a2 */

		case 4 :

			regArray[a1] = (regArray[a1] * a2) % 1000;

			pointer++;

			break;

			

		/* set register a1 to the value of register a2 */

		case 5 : 

			regArray[a1] = regArray[a2];

			pointer++;

			break;

			

		/* add the value of register a2 to register a1 */

		case 6 : 

			regArray[a1] = (regArray[a1] + regArray[a2]) % 1000;

			pointer++;

			break;

			

		/* multiply register a1 by the value of register a2 */

		case 7 :

			regArray[a1] = (regArray[a1] * regArray[a2]) % 1000;

			pointer++;

			break;

			

		/* set register a1 to the value in RAM whose address is in register a2 */

		case 8 :

			regArray[a1] = ram[regArray[a2]];

			pointer++;

			break;			

			

		/* set the value in RAM whose address in in register a2 to that of register a1 */

		case 9 :

			ram[regArray[a2]] = regArray[a1];

			pointer++;

			break;			

			

		/* goto */		

		case 0 :

			if (regArray[a2] != 0) {

				pointer = regArray[a1];

			} else {

				pointer++;

			}

			break;			

			

		default: 

			break;

	}

	return 1;	

}



/* main */

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

	int i, j, cases, num_instr;

	char instr[5];



	scanf("%d", &cases);

	fgets(instr, sizeof(instr), stdin);

	fgets(instr, sizeof(instr), stdin);

	num_instr = 0;

	

	/* for the number of test cases specified */

	for (i = 0; i < cases; i++) {

		init();

		

		pointer = 0;

		

		if (i != 0) {

			printf("\n");

		}

		

		/* read input ram */

		while(fgets(instr, sizeof(instr), stdin) != NULL) {

			if (instr[0] == '\n') {

				break;

			}

			ram[pointer] = (instr[0] - '0') * 100 + (instr[1] - '0') * 10 + (instr[2] - '0');

			pointer++;

		}

		

		/* decode and interpret instructions until halt */

		num_instr = 1;

		pointer = 0;

		while (decode()) {

			num_instr++;

		}	

		

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

	}

	

	return 0;

}

A solution for the "Graphical Editor" problem

jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:23:41 GMT

A solution for the "Graphical Editor" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/102/10267.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.12



/* 

 * Solution for the "Graphical Editor" problem.

 * UVa ID: 10267

 */

#include 



#define MAX 250

#define OFFSET 1

#define DOS_NAME 12



/* global image bounds */

int n, m;



/* fills a rectangle with the specified color */

int fillRectangle(int m_ini, int n_ini, int m_end, int n_end, char color, char pTable[][MAX+OFFSET]) {

	int i, j;

	for (i = n_ini; i <= n_end; i++) {

		for (j = m_ini; j <= m_end; j++) {

			pTable[i][j] = color;

		}

	}

	return 0;

}



/* fills a region R with the specified color */

int fillRegion(int x, int y, char oldColor, char newColor, char pTable[][MAX+OFFSET]) {	

	/* (x,y) is in region R */

	pTable[y][x] = newColor;

	

	/* recursively check all 4 directions for neighbours of (x,y) with same color */

	if ((pTable[y][x-1] == oldColor) && (x > OFFSET)) {         

		fillRegion(x-1, y, oldColor, newColor, pTable);

	}

	if ((pTable[y][x+1] == oldColor) && (x < m)) {       

		fillRegion(x+1, y, oldColor, newColor, pTable);

	}

	if ((pTable[y-1][x] == oldColor) && (y > OFFSET)) {        

		fillRegion(x, y-1, oldColor, newColor, pTable);

	}

	if ((pTable[y+1][x] == oldColor) && (y < n)) {        

		fillRegion(x, y+1, oldColor, newColor, pTable);

	}

	return 0;

}



/* outputs the image */

int printImage(int m, int n, char pTable[][MAX+OFFSET]) {

	int i, j;	

	for (i = OFFSET; i < n+OFFSET; i++) {

		for (j = OFFSET; j < m+OFFSET; j++ ) {

			printf("%c", pTable[i][j]);

		}

		printf("\n");

	}

	return 0;

}



/* main */

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

	/* the image */

	char image[MAX+OFFSET][MAX+OFFSET];



	/* editor command */

	char command;

	

	/* coords */

	int x1, x2, y1, y2, tmp;

	

	/* colors */

	char color, oldColor;

	

	/* filename */

	char filename[DOS_NAME+1];

			

	while(scanf("%c", &command) != EOF) {		

		/* X, terminates the session */

		if (command == 'X') {

			return 0;

		}		

		switch (command) {

			/* create image */

			case 'I' :

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

				fillRectangle(1, 1, m, n, 'O', image);

				break;

			

			/* clear image */

			case 'C' :

				fillRectangle(1, 1, m, n, 'O', image);

				break;

			

			/* colors a pixel */

			case 'L' :

				scanf("%d %d %c", &x1, &y1, &color);

				image[y1][x1] = color;

				break;

			

			/* draw vertical segment */

			case 'V' :

				scanf("%d %d %d %c", &x1, &y1, &y2, &color);

				if (y2 >= y1)

					fillRectangle(x1, y1, x1, y2, color, image);

				else

					fillRectangle(x1, y2, x1, y1, color, image);

				break;

			

			/* draw horizontal segment */

			case 'H' : 

				scanf("%d %d %d %c", &x1, &x2, &y1, &color);

				if (x2 >= x1)

					fillRectangle(x1, y1, x2, y1, color, image);

				else

					fillRectangle(x2, y1, x1, y1, color, image);

				break;

			

			/* draw rectangle */

			case 'K' : 

				scanf("%d %d %d %d %c", &x1, &y1, &x2, &y2, &color);

				if (x1 >= x2) {

					tmp = x1;

					x1 = x2;

					x2 = tmp;

				}

				if (y1 >= y2) {

					tmp = y1;

					y1 = y2;

					y2 = tmp;

				}

				fillRectangle(x1, y1, x2, y2, color, image);

				break;

			

			/* fill */

			case 'F' :

				scanf("%d %d %c", &x1, &y1, &color);

				oldColor = image[y1][x1];

				if (oldColor != color) {

					fillRegion(x1, y1, oldColor, color, image);

				}

				break;



			/* fill */

			case 'S' :

				scanf("%s", &filename);

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

				printImage(m, n, image);

				break;			

		

			default: 

				break;

		}		

	}

	

	return 0;

}

A solution for the "LCD Display" problem

jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:16:55 GMT

A solution for the "LCD Display" problem.

Problem description:
http://acm.uva.es/p/v7/706.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.09



/* 

 * Solution for the "LCD Display" problem.

 * UVa ID: 706

 */

#include 

#include 

#include 



#define MAX_SIZE 9



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

	/* number of vertical or horizontal segments in each digit */

	int s;

	

	/* the number to print */

	char digitString[MAX_SIZE];

	

	/* 

	 * LED representation for each number, according to 

	 * the following convention:

	 *

	 *  -0-

	 * |   |

	 * 2   1

	 * |   |

	 *  -3-

	 * |   |

	 * 5   4

	 * |   |

	 *  -6-

	 *

	 */

	

	const char conversionTable[10][7] = {

		      /* 0   1   2   3   4   5   6 */

		/* 0 */ '-','|','|',' ','|','|','-',	  

		/* 1 */ ' ','|',' ',' ','|',' ',' ',

		/* 2 */ '-','|',' ','-',' ','|','-',

		/* 3 */ '-','|',' ','-','|',' ','-',

		/* 4 */ ' ','|','|','-','|',' ',' ',

		/* 5 */ '-',' ','|','-','|',' ','-',

		/* 6 */ '-',' ','|','-','|','|','-',

		/* 7 */ '-','|',' ',' ','|',' ',' ',

		/* 8 */ '-','|','|','-','|','|','-',

		/* 9 */ '-','|','|','-','|',' ','-',



	};

	

	/* iterators */

	int i, j, k;

	

	while(scanf("%d %s", &s, &digitString) != EOF) {

		

		/* 0, ends the program */

		if (!s) {

			return 0;

		}

		

		int n = strlen(digitString);

		int digit;

		

		for (i = 0; i < 2*s+3; i++) {					

			for (j = 0; j < n; j ++) { 

						

				digit = digitString[j] - '0';



				/* upper, middle and lower parts */

				if ((i % (s + 1)) == 0) {

					printf(" ");

					for (k = 0; k < s; k++) {

						printf("%c", conversionTable[digit][(i / (s + 1)) * 3]);

					}

					printf(" ");

				}

				

				/* between upper and middle parts */

				if (i > 0 && i < (s + 1)) {

					printf("%c", conversionTable[digit][2]);

					for (k = 0; k < s; k++) {

						printf(" ");

					}

					printf("%c", conversionTable[digit][1]);

				}



				

				/* between middle and lower parts */

				if (i > (s + 1) && i < (2*s + 2)) {

					printf("%c", conversionTable[digit][5]);

					for (k = 0; k < s; k++) {

						printf(" ");

					}

					printf("%c", conversionTable[digit][4]);

				}

				

				/* if not the last number */

				if (j != n-1)

					printf(" ");

	

			}			

			printf("\n");

			

		}

		printf("\n");

		

	}

	

	return 0;

}