1  
   2  /* 
   3   * Solution for "Carmichael Numbers" problem.
   4   * UVa ID: 10006
   5   */
   6  #include <iostream>
   7  #include <math.h>
   8  
   9  #define MAXPRIME 65001
  10  
  11  using namespace std;
  12  
  13  /*
  14   * Modular exponentiation algorithm. Returns b^e mod m.
  15   */
  16  unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) {
  17      unsigned long long r = 1;
  18      while (e > 0) {
  19          if ((e & 1) == 1) {
  20  	    r = (r * b) % m;
  21          }
  22          e >>= 1;
  23          b = (b * b) % m;
  24      }
  25      return r;
  26  }
  27  
  28  /* 
  29   * Generates all prime numbers up to MAXPRIME. Based on
  30   * the Sieve of Eratosthenes.
  31   */
  32  void gen_primes(bool p[]) {
  33      p[0] = p[1] = false;
  34  	
  35      /* 
  36       * starting at number 2 and going to the upper limit, mark 
  37       * all numbers as potential primes 
  38       */  
  39      for (int i=2; i<MAXPRIME; i++) {
  40          p[i] = true;
  41      }
  42  	
  43      int m = floor(sqrt(MAXPRIME));
  44      int n;
  45      /* 
  46       * mark all multiples of a prime as non-primes. this has to be done for primes 
  47       * only up to the square root, since every number in the array has at least 
  48       * one factor smaller than the square root of the limit. 
  49       */
  50      for (int i=2; i<m; i++) {
  51          if (p[i]) {
  52         	    n = MAXPRIME / i;
  53  	    for (int j=2; j<=n; j++) {
  54  	        p[i * j] = false;
  55  	    }
  56  	}
  57      }
  58  }
  59  
  60  /* generates all carmichael numbers up to the given limit by performing the fermat test */
  61  void gen_carmi(bool c[], bool p[]) {
  62  
  63      /* initialize carmichael numbers array with false */
  64      memset(c, 0, MAXPRIME * sizeof(bool));
  65  	
  66      /* 
  67       * starting from the first non-prime, mark all 
  68       * odd numbers as potential carmichael numbers 
  69       */
  70      for (int i=9; i<MAXPRIME; i+=2) {
  71  	c[i] = true;
  72      }
  73  	
  74      /* 
  75       * again, for all odd numbers, we exclude the primes and perform
  76       * the fermat test for 2 <= a <= n-1.
  77       */
  78      for (int n=9; n<MAXPRIME; n+=2) {
  79  	/* VERY IMPORTANT! check first if this number is prime, otherwise we get TLE */
  80  	if (p[n]) {
  81  	    c[n] = false;
  82  	    continue;
  83  	}
  84  	for (int a=2; a<=n-1; a++) {
  85  	    if (fast_mod_pow(a,n,n) != a) {
  86  	        c[n] = false;
  87  		break;
  88  	    } 
  89  	}	
  90      }
  91  }
  92  
  93  /* main */
  94  int main() {
  95      unsigned long long n; /* number */
  96      unsigned long long a; /* a of the fermat test */
  97      bool prime[MAXPRIME]; /* prime numbers array */
  98      bool carmi[MAXPRIME]; /* carmichael numbers array */
  99  	
 100      gen_primes(prime);
 101      gen_carmi(carmi, prime);
 102  	
 103      while (cin >> n && (n != 0)) {	
 104          if (carmi[n]) {
 105              cout << "The number " << n << " is a Carmichael number." << endl;
 106          } else {
 107              cout << n << " is normal." << endl;
 108          }
 109      }
 110      return 0;
 111  }

   1  
   2  /*
   3   * Solution for the "Binomial Showdown" problem.
   4   * UVa ID: 530
   5   */
   6  
   7  #include <iostream>
   8  
   9  using namespace std;
  10  
  11  /* main */
  12  int main() {
  13      int n, k;
  14      unsigned long long r; /* result */
  15  
  16      while(cin >> n >> k && ((n != 0) || (k != 0))) {
  17          /* init result */
  18          r = 1;
  19  
  20          /* if k is more than half of n, then use the complement */
  21          if(k > (n / 2)) {
  22              k = n - k;
  23          }
  24  
  25          /*         
  26           * C(n,k) = n! / (k!(n-k)!) =
  27           * (n)(n-1)(...)(n-k+1) / 2*3*4*(...)*k
  28           */ 
  29          for (int i=0; i<k; i++) {
  30              r = r * (n - i);   /* (n)(n-1)(...)(n-k+1) */
  31              r = r / (1 + i);   /* 2*3*4*(...)*k */
  32          }
  33          cout << r << endl;
  34      }
  35  }

   1  
   2  /*
   3   * Solution for the "Reverse and Add" problem.
   4   * UVa ID: 10018
   5   */
   6  #include <iostream>
   7  
   8  #define NDIGITS 100
   9  
  10  using namespace std;
  11  
  12  /* returns the reversed number */
  13  unsigned long long reverse(unsigned long long number) {
  14  	unsigned long long m = 0; /* reversed number */
  15  	int digits[NDIGITS]; /* digits array */
  16  	int pos = 0, power = 1;
  17  	
  18  	/* init */
  19  	for (int i=0; i<NDIGITS; i++) {
  20  		digits[i] = 0;
  21  	}
  22  	
  23  	/* retrieve all digits */
  24  	while (number > 0) {
  25  		digits[pos++] = number % 10;
  26  		number = number / 10;
  27  	}
  28  
  29  	/* multiply the reversed digits by the powers of ten */
  30  	for (int i=pos-1; i>=0; i--) {
  31  		m += power * digits[i];
  32  		power *= 10;
  33  	}
  34  	
  35  	return m;
  36  }
  37  
  38  /* main */
  39  int main() {
  40  	int nc; /* number of cases */
  41  	int m; /* minimum number of iterations */
  42  	unsigned long long n; /* number */
  43  	
  44  	cin >> nc;
  45  	
  46  	/* reverse and add.. */
  47  	for (int i=0; i<nc; i++) {
  48  		cin >> n;
  49  		m = 0;
  50  		while (true) {
  51  			if (reverse(n) == n) {
  52  				break;
  53  			} else {
  54  				n += reverse(n);
  55  				m++;
  56  			}
  57  		}
  58  		cout << m << " " << n << endl;
  59  	}
  60  	
  61  	return 0;
  62  } 
  63  

   1  
   2  /**
   3   * Solution for the "Primary Arithmetic" problem.
   4   * UVa ID: 10035
   5   */ 
   6  #include <iostream.h> 
   7  #include <stdlib.h> 
   8  
   9  using namespace std; 
  10  
  11  int main() {
  12      unsigned long long n1; /* 1st number */ 
  13      unsigned long long n2; /* 2nd number */ 
  14      int carry = 0; /* carry */ 
  15      int sum = 0; /* temporary sum */ 
  16      int count = 0; /* carry counter */ 
  17  
  18      while(cin >> n1 >> n2 && ((n1 > 0) || (n2 > 0))) { 
  19          carry = 0; 
  20  	count = 0; 
  21  	sum = 0; 
  22  
  23  	/* while there's still something.. */ 
  24  	while ((n1 > 0) || (n2 > 0)) { 
  25  	    /* sum the two right-most digits */ 
  26  	    sum = carry + (n1 % 10) + (n2 % 10); 
  27  
  28  	    if (sum >= 10) { 
  29  		count++; 
  30  	    } 
  31  			
  32  	    /* get the carry by dividing the sum of the two digits */ 
  33  	    carry = sum / 10; 
  34  
  35  	    /* 'reduce' the numbers by ten, to update the right-most digits */ 
  36  	    n1 /= 10; 
  37              n2 /= 10; 
  38  	} 
  39  		
  40  	if (count == 0) { 
  41              cout << "No carry operation." << endl; 
  42  	} else if (count == 1) { 
  43  	    cout << "1 carry operation." << endl; 
  44  	} else { 
  45              cout << count << " carry operations." << endl; 
  46          } 
  47      } 
  48  
  49      return 0;
  50  } 

   1  
   2  /* 
   3   * Solution for "Shoemaker" problem.
   4   * UVa ID: 10026
   5   */
   6  #include <iostream>
   7  
   8  #define NJOBS 1000
   9  
  10  using namespace std;
  11  
  12  int jobs[NJOBS]; /* jobs */
  13  double p[NJOBS]; /* priority */
  14  
  15  /* main */
  16  int main() {
  17      int nc;	/* number of cases */
  18  	int nj; /* number of jobs */
  19  	int ct;	/* completion time */
  20  	int dp; /* daily penalty */
  21  	
  22      cin >> nc;
  23  	
  24  	/* for each test case.. */
  25      for (int i=0; i<nc; i++) {
  26  		cin >> nj;
  27  		
  28  		/* init input */
  29  		for (int i=0; i<nj; i++) {
  30  			cin >> ct >> dp;
  31  			jobs[i] = i;
  32  			/* priority is daily penalty divided by completion time (minimal fine) */
  33  			p[i] = double(dp) / ct;
  34  		}
  35  		
  36  		int j, k, tmp;
  37  		
  38  		/* sort jobs by priority */
  39  		for (int i=0; i<nj-1; i++) {
  40  			for (j=i+1, k=i; j<nj; j++) {
  41  				if( (p[jobs[j]] > p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] < jobs[k])) ) {
  42  					k=j;
  43  				}
  44  			}
  45  			tmp = jobs[i]; 
  46  			jobs[i] = jobs[k]; 
  47  			jobs[k] = tmp;
  48  		}
  49  		
  50  		/* output */
  51  		for (int i=0; i<nj; i++) {
  52  			if(i > 0) { 
  53  				cout << " ";
  54  			}
  55  			cout << jobs[i] + 1;
  56  		}
  57  		cout << endl;
  58  		if (i < nc-1) {
  59  			cout << endl;
  60  		}
  61      }
  62  	
  63      return 0;
  64  }
  65  

   1  
   2  /* 
   3   * Solution for "Stack 'em Up" problem.
   4   * UVa ID: 10205
   5   */
   6  #include <iostream>
   7  
   8  #define NVALUES 13
   9  #define NSUITS 4
  10  #define NCARDS 52
  11  #define NSHUFFLES 100
  12  #define WSIZE 9
  13  
  14  using namespace std;
  15  
  16  char values[NVALUES][WSIZE] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
  17  char suits[NSUITS][WSIZE] = {"Clubs", "Diamonds", "Hearts", "Spades"};
  18  int shuffles[NSHUFFLES][NCARDS];
  19  int deck[NCARDS];
  20  
  21  /* read all dealer shuffles */
  22  void read_shuffles(int n_shuff) {
  23  	for(int i=0; i<n_shuff; i++) {
  24  		for (int j=0; j<NCARDS; j++) {
  25  			cin >> shuffles[i][j];
  26  		}
  27  	}
  28  }
  29  
  30  /* shuffle the deck with one of the known shuffles */
  31  void shuffle_deck(int s_id) {
  32  	int tmpdeck[NCARDS];
  33  	for (int i=0; i<NCARDS; i++) {
  34  		tmpdeck[i] = deck[shuffles[s_id][i] - 1];
  35  	}
  36  	for (int i=0; i<NCARDS;i++) {
  37  		deck[i] = tmpdeck[i];
  38  	}
  39  }
  40  
  41  /* main */
  42  int main (int argc, const char *argv[]) {
  43  	int nc; /* number of cases */
  44  	int ns;	/* number of shuffles */
  45  	int s; /* current shuffle */
  46  		
  47  	cin >> nc;
  48  		
  49  	for (int i=0; i<nc; i++) {	
  50  		cin >> ns;
  51  			
  52  		/* initialize deck */
  53  		for (int p=0; p<NCARDS; p++) {
  54  			deck[p] = p;
  55  		}
  56  		
  57  		/* read list of known shuffles */
  58  		read_shuffles(ns);
  59  		
  60  		/* shuffle deck */
  61  		for (int j=0; j<ns; j++) {
  62  			cin >> s;
  63  			shuffle_deck(s - 1);
  64  		}
  65  
  66  		/* print deck */
  67  		for (int k=0; k<NCARDS; k++) {
  68  			cout << values[deck[k] % NVALUES] << " of " << suits[deck[k] / NVALUES] << endl;
  69  		}
  70  		if (i < (nc - 1)) {
  71  			cout << endl;
  72  		}
  73  	}
  74  	
  75  }
  76  
  77  

   1  
   2  /* 
   3   * Solution for the "Hartals" problem.
   4   * UVa ID: 10050
   5   */
   6  #include <iostream>
   7   
   8  #define NDAYS 3651
   9   
  10  using namespace std;
  11  
  12  /* simulation time (in days) */
  13  int st[NDAYS]; 
  14   
  15  /* main */
  16  int main (int argc, const char *argv[]) {
  17  	int nc; /* number of cases */
  18  	int nd; /* number of days */
  19  	int np; /* number of political parties */
  20  	int h; /* current hartal number */
  21  	int dl;	/* days lost */
  22  	
  23  	cin >> nc;
  24  	
  25  	/* for each case.. */
  26  	for (int i=0; i<nc; i++) {
  27  		cin >> nd;
  28  		cin >> np;		
  29  		
  30  		/* initialize simulation table */
  31  		for (int j=0; j<=nd; j++) {
  32  			st[j] = 0;
  33  		}
  34  		dl = 0; /* init days lost counter */
  35  		
  36  		/* update with hartal for each party */
  37  		for (int j=0; j<np; j++) {
  38  			cin >> h;
  39  			for (int k=1; k*h-1<=nd; k++) {
  40  				st[k*h-1] = 1; /* set lost day flag */
  41  			}
  42  		}
  43  		
  44  		/* calculate number of days lost */
  45  		for (int j=0; j<nd; j++) {
  46  			/* if it's not a friday or a saturday */
  47  			if ((j%7 != 5) && (j%7 != 6) && (st[j] == 1)) {
  48  				dl++;
  49  			}
  50  		}
  51  		cout << dl << endl;
  52  	}
  53  	
  54  }
  55  
  56  

   1  
   2  /* 
   3   * Solution for the "Interpreter" problem.
   4   * UVa ID: 10033
   5   */
   6  #include <stdio.h>
   7  
   8  #define MAX_REG 10
   9  #define MAX_RAM 1000
  10  
  11  int pointer;
  12  int regArray[MAX_REG];
  13  int ram[MAX_RAM];
  14  
  15  /* initialize registers and ram */
  16  int init() {
  17  	int i;
  18  	for (i = 0; i < MAX_REG; i++) {
  19  		regArray[i] = 0;
  20  	}
  21  	for (i = 0; i < MAX_RAM; i++) {
  22  		ram[i] = 0;
  23  	}
  24  	
  25  }
  26  
  27  /* decode instruction */
  28  int decode() {
  29  	int command, a1, a2;
  30  	command = ram[pointer] / 100;
  31  	a1 = (ram[pointer] % 100) / 10;
  32  	a2 = ram[pointer] % 10;
  33  	
  34  	switch (command) {
  35  		/* halt */
  36  		case 1 :		
  37  			return 0;
  38  			break;
  39  			
  40  		/* set register a1 to a2 */
  41  		case 2 :
  42  			regArray[a1] = a2;
  43  			pointer++;
  44  			break;
  45  			
  46  		/* add a2 to register a1 */
  47  		case 3 :
  48  			regArray[a1] = (regArray[a1] + a2) % 1000;
  49  			pointer++;
  50  			break;
  51  			
  52  		/* multiply register a1 by a2 */
  53  		case 4 :
  54  			regArray[a1] = (regArray[a1] * a2) % 1000;
  55  			pointer++;
  56  			break;
  57  			
  58  		/* set register a1 to the value of register a2 */
  59  		case 5 : 
  60  			regArray[a1] = regArray[a2];
  61  			pointer++;
  62  			break;
  63  			
  64  		/* add the value of register a2 to register a1 */
  65  		case 6 : 
  66  			regArray[a1] = (regArray[a1] + regArray[a2]) % 1000;
  67  			pointer++;
  68  			break;
  69  			
  70  		/* multiply register a1 by the value of register a2 */
  71  		case 7 :
  72  			regArray[a1] = (regArray[a1] * regArray[a2]) % 1000;
  73  			pointer++;
  74  			break;
  75  			
  76  		/* set register a1 to the value in RAM whose address is in register a2 */
  77  		case 8 :
  78  			regArray[a1] = ram[regArray[a2]];
  79  			pointer++;
  80  			break;			
  81  			
  82  		/* set the value in RAM whose address in in register a2 to that of register a1 */
  83  		case 9 :
  84  			ram[regArray[a2]] = regArray[a1];
  85  			pointer++;
  86  			break;			
  87  			
  88  		/* goto */		
  89  		case 0 :
  90  			if (regArray[a2] != 0) {
  91  				pointer = regArray[a1];
  92  			} else {
  93  				pointer++;
  94  			}
  95  			break;			
  96  			
  97  		default: 
  98  			break;
  99  	}
 100  	return 1;	
 101  }
 102  
 103  /* main */
 104  int main (int argc, const char * argv[]) {
 105  	int i, j, cases, num_instr;
 106  	char instr[5];
 107  
 108  	scanf("%d", &cases);
 109  	fgets(instr, sizeof(instr), stdin);
 110  	fgets(instr, sizeof(instr), stdin);
 111  	num_instr = 0;
 112  	
 113  	/* for the number of test cases specified */
 114  	for (i = 0; i < cases; i++) {
 115  		init();
 116  		
 117  		pointer = 0;
 118  		
 119  		if (i != 0) {
 120  			printf("\n");
 121  		}
 122  		
 123  		/* read input ram */
 124  		while(fgets(instr, sizeof(instr), stdin) != NULL) {
 125  			if (instr[0] == '\n') {
 126  				break;
 127  			}
 128  			ram[pointer] = (instr[0] - '0') * 100 + (instr[1] - '0') * 10 + (instr[2] - '0');
 129  			pointer++;
 130  		}
 131  		
 132  		/* decode and interpret instructions until halt */
 133  		num_instr = 1;
 134  		pointer = 0;
 135  		while (decode()) {
 136  			num_instr++;
 137  		}	
 138  		
 139  		printf("%d\n",num_instr);	
 140  	}
 141  	
 142  	return 0;
 143  }

   1  
   2  /* 
   3   * Solution for the "Graphical Editor" problem.
   4   * UVa ID: 10267
   5   */
   6  #include <stdio.h>
   7  
   8  #define MAX 250
   9  #define OFFSET 1
  10  #define DOS_NAME 12
  11  
  12  /* global image bounds */
  13  int n, m;
  14  
  15  /* fills a rectangle with the specified color */
  16  int fillRectangle(int m_ini, int n_ini, int m_end, int n_end, char color, char pTable[][MAX+OFFSET]) {
  17  	int i, j;
  18  	for (i = n_ini; i <= n_end; i++) {
  19  		for (j = m_ini; j <= m_end; j++) {
  20  			pTable[i][j] = color;
  21  		}
  22  	}
  23  	return 0;
  24  }
  25  
  26  /* fills a region R with the specified color */
  27  int fillRegion(int x, int y, char oldColor, char newColor, char pTable[][MAX+OFFSET]) {	
  28  	/* (x,y) is in region R */
  29  	pTable[y][x] = newColor;
  30  	
  31  	/* recursively check all 4 directions for neighbours of (x,y) with same color */
  32  	if ((pTable[y][x-1] == oldColor) && (x > OFFSET)) {         
  33  		fillRegion(x-1, y, oldColor, newColor, pTable);
  34  	}
  35  	if ((pTable[y][x+1] == oldColor) && (x < m)) {       
  36  		fillRegion(x+1, y, oldColor, newColor, pTable);
  37  	}
  38  	if ((pTable[y-1][x] == oldColor) && (y > OFFSET)) {        
  39  		fillRegion(x, y-1, oldColor, newColor, pTable);
  40  	}
  41  	if ((pTable[y+1][x] == oldColor) && (y < n)) {        
  42  		fillRegion(x, y+1, oldColor, newColor, pTable);
  43  	}
  44  	return 0;
  45  }
  46  
  47  /* outputs the image */
  48  int printImage(int m, int n, char pTable[][MAX+OFFSET]) {
  49  	int i, j;	
  50  	for (i = OFFSET; i < n+OFFSET; i++) {
  51  		for (j = OFFSET; j < m+OFFSET; j++ ) {
  52  			printf("%c", pTable[i][j]);
  53  		}
  54  		printf("\n");
  55  	}
  56  	return 0;
  57  }
  58  
  59  /* main */
  60  int main (int argc, const char * argv[]) {
  61  	/* the image */
  62  	char image[MAX+OFFSET][MAX+OFFSET];
  63  
  64  	/* editor command */
  65  	char command;
  66  	
  67  	/* coords */
  68  	int x1, x2, y1, y2, tmp;
  69  	
  70  	/* colors */
  71  	char color, oldColor;
  72  	
  73  	/* filename */
  74  	char filename[DOS_NAME+1];
  75  			
  76  	while(scanf("%c", &command) != EOF) {		
  77  		/* X, terminates the session */
  78  		if (command == 'X') {
  79  			return 0;
  80  		}		
  81  		switch (command) {
  82  			/* create image */
  83  			case 'I' :
  84  				scanf("%d %d", &m, &n);
  85  				fillRectangle(1, 1, m, n, 'O', image);
  86  				break;
  87  			
  88  			/* clear image */
  89  			case 'C' :
  90  				fillRectangle(1, 1, m, n, 'O', image);
  91  				break;
  92  			
  93  			/* colors a pixel */
  94  			case 'L' :
  95  				scanf("%d %d %c", &x1, &y1, &color);
  96  				image[y1][x1] = color;
  97  				break;
  98  			
  99  			/* draw vertical segment */
 100  			case 'V' :
 101  				scanf("%d %d %d %c", &x1, &y1, &y2, &color);
 102  				if (y2 >= y1)
 103  					fillRectangle(x1, y1, x1, y2, color, image);
 104  				else
 105  					fillRectangle(x1, y2, x1, y1, color, image);
 106  				break;
 107  			
 108  			/* draw horizontal segment */
 109  			case 'H' : 
 110  				scanf("%d %d %d %c", &x1, &x2, &y1, &color);
 111  				if (x2 >= x1)
 112  					fillRectangle(x1, y1, x2, y1, color, image);
 113  				else
 114  					fillRectangle(x2, y1, x1, y1, color, image);
 115  				break;
 116  			
 117