10070 - Leap Year or Not Leap Year and …, uva

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define db(a) cout << #a << " = " << a << endl
using namespace std;
string linea;
int n = 0;
bool esbisiesto() {
 bool fin = false;
 int num = 0, t = 1;
 for (int i = 0; i < 4 && !fin; i++) {
  if (i >= n) {
   fin = true;
   continue;
  }
  num = t * (linea[n - i - 1] - 48) + num;
  t *= 10;
 }
 //db(num);
 return (num % 4 == 0 && num % 100 != 0) or (num % 400 == 0);
}
int main() {
 bool por3, por5, por11, bisiesto, first = true;
 while (cin >> linea) {
  if (!first) puts("");
  else first = false;
  n = linea.size();
  bisiesto = esbisiesto();
  int suma11 = 0;
  int suma3 = 0;
  for (int i = 0; i < n; i++) {
   suma3 += linea[i] - 48;
   if (i % 2) suma11 += linea[i] - 48;
   else suma11 -= linea[i] - 48;
  }
  por3 = (suma3 % 3 == 0);
  por5 = (linea[n - 1] - 48) % 5 == 0;
  por11 = suma11 % 11 == 0;
  if (bisiesto) puts("This is leap year.");
  if (por3 && por5) puts("This is huluculu festival year.");
  if (por5 && por11 && bisiesto) puts("This is bulukulu festival year.");
  if (!bisiesto && !(por3 && por5) && !(por5 && por11 && bisiesto))
   puts("This is an ordinary year.");
 }
 return 0;
}

750 - 8 Queens Chess Problem , uva

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int x[9], a, b, cont = 0;
bool place(int queen, int row) {
 for (int prev = 1; prev < queen; prev++)
  if (x[prev] == row or abs(x[prev] - row) == abs(prev - queen))
   return false;
 return true;
}
void Nqueen(int queen) {
 if (queen == 9) {
  if (x[b] == a) {
   printf("%2d      %d",++cont, x[1]);
   for (int i = 2; i <= 8; i++) {
    printf(" %d", x[i]);
   }
   puts("");
  }
 }
 else {
  for (int row = 1; row <= 8; row++) {
   if (place(queen, row)) {
    x[queen] = row;
    Nqueen(queen + 1);
   }
  }
 }
}
int main() {
 int t;
 scanf("%d", &t);
 while (t--) {
  scanf("%d %d", &a, &b);
  memset(x, 0, sizeof x);
  cont = 0;
  printf("SOLN       COLUMN\n");
  printf(" #      1 2 3 4 5 6 7 8\n\n");
  Nqueen(1);
  if (t) puts("");
 }
 return 0;
}

11988 - Broken Keyboard (a.k.a. Beiju Text), uva

#include<iostream>
#include<cstdio>
#include<deque>
#define db(a) cout << #a << " = " << a << endl
using namespace std;
deque<string> deq;
void insert(bool pos, string &s) {
 if (pos) deq.push_back(s);
 else deq.push_front(s);
 s = "";
}
int main() {
 string aux;
 bool end = true;
 char c;
 while (c = getchar()) {
  if (c == EOF) break;
  if (c == '\n') {
   insert(end, aux);
   while (deq.size()) { 
    printf("%s", deq.front().c_str());
    deq.pop_front();
   }
   printf("\n");
   deq.clear();
   aux = "";
   end = true;
  }
  else
   if (c == '[') {
    if (aux != "") {
     insert(end, aux);
    }
    end = false;
   }
   else
    if (c == ']') {
     if (aux != "") insert(end, aux);
     end = true;
    }
    else aux += c;
 }
 return 0;
}

374 - Big Mod , uva

#include<iostream>
#include<ctime>
#include<cstring>
#include<cstdio>
#define mod 131071
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
int m;
int power(int n, int p) {
 if (p == 0) return 1;
 if (p == 1) return n;
 if (p & 1) {
  return ((n % m)  * (power(((n % m) * (n % m)) % m, (p - 1) / 2) % m)) % m;
 }
 else {
  return power(((n % m) * (n % m))% m, p / 2);
 }
}
int main() {
 int b, p;
 while (cin >> b >> p >> m) {
  cout << power(b, p) << endl;
 }
 return 0;
}

Click here for a great explanation

10176 - Ocean Deep - Make it shallow , uva

#include<iostream>
#include<cstring>
#include<cstdio>
#define mod 131071
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
int main() {
	string binario = "", leido;
	while (cin >> leido) {
		int len = leido.size();
		if (leido[len - 1] == '#') {
			int res = 0;
			binario += leido.substr(0, len - 1);
			int total = binario.size();
			int p = 1;
			for (int i = total - 1; i >= 0; i--) {
				res += (binario[i] - '0') * p;
				res %= mod;
				p *= 2;
				p %= mod;
			}
			if (res == 0) puts("YES");
			else puts("NO");
			binario = "";
		}
		else binario += leido;
	}
	return 0;
}

10583 - Ubiquitous Religions, uva

#include<iostream>
#include<cstdio>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl
#define MAX 50001
using namespace std;
int P[MAX], mejor[MAX];
int find(int i) { return P[i] == -1 ? i : P[i] = find(P[i]); }
void join(int i, int j) { if (find(i) != find(j)) P[find(i)] = find(j);}
void init(int n) { fill(P, P + n, -1);}
int main() {
 int n, m, a, b, cont = 1;
 while (scanf("%d %d", &n, &m) != EOF && (n || m)) {
  init(n + 1);
  for (int i = 0; i < m; i++) {
   scanf("%d %d", &a, &b);
   join(a, b);
  }
  int res = 0;
  for (int i = 1; i < n + 1; i++) res += find(i) == i;
  printf("Case %d: %d\n",cont++ , res);
 }
 return 0;
}

10608 - Friends, uva

#include<iostream>
#include<cstdio>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl
#define MAX 30001
using namespace std;
int P[MAX], mejor[MAX];
int find(int i) { return P[i] == -1 ? i : P[i] = find(P[i]); }
void join(int i, int j) { if (find(i) != find(j)) P[find(i)] = find(j);}
void init(int n) { fill(P, P + n, -1);}
int main() {
 int n, m, a, b, t;
 scanf("%d", &t);
 while (t--) {
  scanf("%d %d", &n, &m);
  init(n + 1);
  for (int i = 0; i < m; i++) {
   scanf("%d %d", &a, &b);
   join(a, b);
  }
  fill(mejor, mejor + n + 1, 0);
  for (int i = 1; i < n + 1; i++) mejor[find(i)]++;
  
  
  int res = *max_element(mejor, mejor + n + 1);
  printf("%d\n", res);
 }
 return 0;
}

10360 - Rat Attack, uva

#include<iostream>
#include<cstring>
#include<vector>
#include<utility>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
int killed[1025][1025];
using namespace std;
int main() {
 int s, d, n, x, y, tam;
 cin >> s;
 for (int i = 0; i < s; i++) {
  memset(killed, 0, sizeof killed);
  cin >> d >> n;
  for (int j = 0; j < n; j++) {
   cin >> x >> y >> tam;
   for (int u = x - d; u <= x + d; u++)
    for (int v = y - d; v <= y + d; v++) {
     if (u >= 0 && u <= 1024 && v >= 0 && v <= 1024) killed[u][v] += tam;
    }
  }
  int maxi = 0;
  for (int u = 0; u <= 1024; u++)
    for (int v = 0; v <= 1024; v++) {
     if (maxi < killed[u][v]) {
      maxi = killed[u][v];
      x = u;
      y = v;
     }
    }
  cout << x << " " << y << " " << maxi << endl;
 }
 return 0;
}

10903 - Rock-Paper-Scissors Tournament, uva

#include<iostream>
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<numeric>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
struct player {
 int win, lose;
 player(int win = 0, int lose = 0) : win(win), lose(lose) {}
};
int main() {
 int p1, p2, n, k;
 string m1, m2;
 char linea[100];
 stringstream ss;
 bool first = true;
 while (scanf("%d %d\n",&n , &k) == 2){
  if (n == 0) break;
  if (!first) 
   printf("\n");
  else first = false;
  player jugadores[n];
  int times = k * n * (n - 1) / 2;
  for (; times-- ; ) {
   gets(linea);
   ss.clear();
   ss << linea;
   ss >> p1 >> m1 >> p2 >> m2;
   if ( m1[0] == 'r') {
    if (m2[0] == 's')
     jugadores[p1 - 1].win++, jugadores[p2 - 1].lose++;
    else
     if (m2[0] == 'p') jugadores[p1 - 1].lose++, jugadores[p2 - 1].win++;
    continue;
   }
   if ( m1[0] == 's') {
    if (m2[0] == 'p')
     jugadores[p1 - 1].win++, jugadores[p2 - 1].lose++;
    else
     if (m2[0] == 'r') jugadores[p1 - 1].lose++, jugadores[p2 - 1].win++;
    continue;
   }
   if ( m1[0] == 'p') {
    if (m2[0] == 'r')
     jugadores[p1 - 1].win++, jugadores[p2 - 1].lose++;
    else
     if (m2[0] == 's') jugadores[p1 - 1].lose++, jugadores[p2 - 1].win++;
    continue;
   }
  }
  for (int i = 0;i < n; i++) {
   if (jugadores[i].win + jugadores[i].lose == 0)
    puts("-");
   else
    printf("%.3f\n", (double)jugadores[i].win / (jugadores[i].win + jugadores[i].lose));
  }
 }
 return 0;
}

459 - Graph Connectivity, uva

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " = " << #b << " = " << b << endl
using namespace std;
int vis[26], mapa[26][26], top;
void buscar(int i) {
 if (!vis[i]) {
  vis[i] = 1;
  for (int j = 0; j <= top; j++) {
   if (mapa[i][j]) {
    mapa[i][j] = 0;
    mapa[j][i] = 0;
    buscar(j);
   }
  }
 }
}
int main() {
 int cases, res;
 char linea[3];
 scanf("%d\n\n", &cases);
 for (int k = 0; k < cases; k++) {
  memset(mapa, 0, sizeof mapa);
  memset(vis, 0, sizeof vis);
  res = 0;
  while(gets(linea) && linea[0]) {
   if (!linea[1]) 
    top = linea[0] - 'A';
   else 
    mapa[linea[0] - 'A'][linea[1] - 'A'] = mapa[linea[1] - 'A'][linea[0] - 'A'] = 1;
  }
  for (int i = 0; i <= top; i++)
    if (!vis[i]) buscar(i), res++;
  printf("%d\n", res);
  if (k + 1 != cases) printf("\n");
 }
 
 return 0;
}

10928 - My Dear Neighbours, uva

#include<iostream>
#include<sstream>
#define db(a) cout << #a << " = " << a << endl
using namespace std;
int main() {
 ios_base::sync_with_stdio(false);
 int casos, v[1001];
 int lugares, val;
 stringstream ss;
 string linea;
 cin >> casos;
 int min;
 getline(cin, linea);
 while (casos--) {
  cin >> lugares;
  getline(cin, linea);
  min = 0x7fffffff;
  for (int i = 1; i <= lugares; i++) {
   ss.clear();
   getline(cin, linea);
   ss << linea;
   v[i] = 0;
   while (ss >> val)
    v[i]++;
   if (min > v[i]) min = v[i];
  }
  bool first = true;
  for (int i = 1; i <= lugares; i++) {
   if (min == v[i])
    if (first) {
     cout << i;
     first = false;
    }
    else
     cout << " " << i;
  }
  cout << endl;
 }
 return 0;
}

291 - The House Of Santa Claus, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl
using namespace std;
int matriz[6][6];
int prev12[] = {1, 2, 3, 5};
int prev35[] = {1, 2, 3, 4, 5};
int prev4[]= {3, 5};
void buscar(int res,int deep) {
 if(deep == 8) {
  //printf("%d %d\n",cont++, res);
  printf("%d\n", res);
 }
 else {
  int prev = res % 10;
  if (prev == 1 || prev == 2) {
   for (int i = 0; i < 4; i++) {
    if (!matriz[prev][prev12[i]]) {
     matriz[prev][prev12[i]] = 1;
     matriz[prev12[i]][prev] = 1;
     /*db(prev);
     db2(res * 10 + prev12[i], deep + 1);*/
     buscar(res * 10 + prev12[i], deep + 1);
     matriz[prev][prev12[i]] = 0;
     matriz[prev12[i]][prev] = 0;
    }
   }
  }
  else {
   if (prev == 3 || prev == 5) {
    for (int i = 0; i < 5; i++) {
     if (!matriz[prev][prev35[i]]) {
      matriz[prev][prev35[i]] = 1;
      matriz[prev35[i]][prev] = 1;
      /*db(prev);
      db2(res * 10 + prev35[i], deep + 1);*/
      buscar(res * 10 + prev35[i], deep + 1);
      matriz[prev][prev35[i]] = 0;
      matriz[prev35[i]][prev] = 0;
     }
    }
   }
   else {
    for (int i = 0; i < 2; i++) {
     if (!matriz[prev][prev4[i]]) {
      matriz[prev][prev4[i]] = 1;
      matriz[prev4[i]][prev] = 1;
      /*db(prev);
      db2(res * 10 + prev4[i], deep + 1);*/
      buscar(res * 10 + prev4[i], deep + 1);
      matriz[prev][prev4[i]] = 0;
      matriz[prev4[i]][prev] = 0;
     }
    }
   }
  }
 }
}
int main() {
 memset(matriz, 0, sizeof matriz);
 for (int i = 0; i < 6; i++) matriz[i][i] = 1;
 buscar(1, 0);
 return 0;
}

11136 - Hoax or what, uva

#include<cstdio>
#include<set>
using namespace std;
int main() {
 int n, k, val, i, num;
 long long res;
 multiset::iterator it;
 multiset s;
 while (scanf("%d", &n)) {
  if (n == 0) break;
  s.clear();
  res = 0;
  for (num = 0; num < n; num++) {
   scanf("%d", &k);
   for (i = 0; i < k; i++) {
    scanf("%d", &val);
    s.insert(val);
   }
   it = s.end();
   it--;
   res += *it - *s.begin();
   s.erase(it);
   s.erase(s.begin());
  }
  printf("%lld\n", res);
 }
 return 0;
}

11308 - Bankrupt Baker, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) cout << #a << " = " << a << endl
using namespace std;
int main() {
	int t, m, n, b, price, cant, units;
	char linea[60];
	
	scanf("%d\n", &t);
	for (int i = 0; i < t; i++) {
		map mapa_price;
		pair receta;
		set< pair > lista;
		gets(linea);
		int len = strlen(linea);
		transform(linea, linea + len, linea, ::toupper);
		printf("%s\n", linea);	
		scanf("%d%d%d\n", &m , &n, &b);
		for (int r = 0; r < m; r++) {
			scanf("%s %d\n", linea, &price);
			mapa_price[linea] = price;
		}
		for (int q = 0; q < n; q++) {
			gets(linea);
			receta.second = linea;
			receta.first = 0;
			gets(linea);
			cant = atoi(linea);
			units = 0;
			for (int r = 0; r < cant; r++) {
				scanf("%s %d\n", linea, &units);
				receta.first += mapa_price[linea] * units;
			}
			lista.insert(receta);
		}
		cant = 0;
		foreach(it, lista) {
			if (it->first <= b) {
			printf("%s\n", it->second.c_str());
			cant++;
			}
		}
		if(cant == 0) 
			printf("Too expensive!\n");
		printf("\n");
	}
	return 0;
}

10226 - Hardwood Species, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<cstdlib>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) cout << #a << " = " << a << endl
using namespace std;
int main() {
	char linea[30];
	void *p;
	gets(linea);
	int test = atoi(linea), total;
	gets(linea);
	for (int i = 0; i < test; i++) {
		if (i != 0) printf("\n");
		map mapa;
		while (1) {
			p = gets(linea);
			if(p == NULL || linea[0] == '\0') break;
			if (strcmp(linea, "") == 0) break;
			mapa[linea]++;
		}
		total = 0;
		foreach(it, mapa) {
			total += it->second;
		}
		foreach(it, mapa) {
			printf("%s %.4f\n", it->first.c_str(), ( (double)it->second * 100 )/ total);
		}
	}
	return 0;
}

11034 - Ferry Loading IV, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define db(a) cout << #a << " = " << a << endl;
#define foreach(it,l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main() {
 int c, l, m, val, cap = 0, cont = 0;
 char direccion[20];
 scanf("%d", &c);
 for (int k = 0; k < c; k++) {
  queue left, right;
  scanf("%d %d", &l, &m);
  l *= 100;
  for (int i = 0; i < m; i++) {
   scanf("%d %s", &val, direccion);
   if(strcmp(direccion,"left") == 0) 
    left.push(val);
   else 
    right.push(val);
  }
  cont = cap = 0;
  string ini = "left";
  while (!left.empty() || !right.empty()) {
   if (ini == "left") {
    cap = 0;
    while (!left.empty() && cap + left.front() <= l) {
     //printf("left %d\n", time + t);
     cap += left.front();
     left.pop();
    }
    ini = "right";
    cont++;
   }
   else {
    cap = 0;
    while (!right.empty() && cap + right.front() <= l) {
     //printf("right %d\n", time + t);
     cap += right.front();
     right.pop();
    }
    ini = "left";
    cont++;
   }
  }
  printf("%d\n", cont);
 }
 return 0;
}

725 - Division, uva

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>

/*#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " "<< #b << " = " << b << endl
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)*/

using namespace std;
bool digits[10];
int last;

bool valid(int numerador, int denominador) {
    if (numerador > 99999) return false;
    memset(digits, true, sizeof digits);
    if (numerador / 10000 == 0) digits[0] = false;
    while (numerador > 0) {
        last = numerador % 10;
        if (digits[last]) digits[last] = false;
        else return false;
        numerador /= 10;
    }
    if (denominador / 10000 == 0)
        if (digits[0]) digits[0] = false;
        else return false;
    while (denominador > 0) {
        last = denominador % 10;
        if (digits[last]) digits[last] = false;
        else return false;
        denominador /= 10;
    }
    return true;
}

int main() {
    int N, num;
    bool ok;
    //clock_t now = clock();
    scanf("%d", &N);
    if (N != 0) {
        while (true) {
            ok = false;
            for (int f = 0; f < 10; f++) {
                num = f;
                for (int g = 0; g < 10; g++) {
                    if (g == f) continue;
                    num = num * 10 + g;
                    for (int h = 0; h < 10; h++) {
                        if (h == g || h == f) continue;
                        num = num * 10 + h;
                        for (int i = 0; i < 10; i++) {
                            if (i == h || i == g || i == f) continue;
                            num = num * 10 + i;
                            for (int j = 0; j < 10; j++) {
                                if (j == i || j == h || j == g || j == f) continue;
                                num = num * 10 + j;
                                //db(num);
                                int numerator = num * N;
                                if (valid(numerator, num)) {
                                    ok = true;
                                    //db(numerator % num);
                                    if (numerator / 10000 == 0) {
                                        if (num / 10000 == 0) {
                                            //db2(num, num / 10000);
                                            printf("0%d / 0%d = %d\n", numerator, num, N);
                                        } else
                                            printf("0%d / %d = %d\n", numerator, num, N);
                                    } else {
                                        if (num / 10000 == 0) {
                                            //db2(num,num / 10000);
                                            printf("%d / 0%d = %d\n", numerator, num, N);
                                        } else
                                            printf("%d / %d = %d\n", numerator, num, N);
                                    }
                                }
                                num -= j;
                                num /= 10;
                            }
                            num -= i;
                            num /= 10;
                        }
                        num -= h;
                        num /= 10;
                    }
                    num -= g;
                    num /= 10;
                }
            }
            int temp = N;
            scanf("%d", &N);
            if (!ok)
                if(N != 0)
                printf("There are no solutions for %d.\n\n", temp);
                else
                printf("There are no solutions for %d.\n", temp);
            else printf("\n");
            if(N == 0) break;
        }
    }
    //printf("el tiempo para todo fue: %.3fs", (clock() - now) * 1.0 / (CLOCKS_PER_SEC) );
    return 0;
}

101 - The Blocks Problem, uva

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cctype>
#include <cmath>
#include <numeric>
#define escribir(a) cout << #a << "=" << a << endl;
using namespace std;
int block[25];
stack s[25], tmp;
void move_onto(int a, int b);
void move_over(int a, int b);
void pile_onto(int a, int b);
void pile_over(int a, int b);

int main() {
    int n, a, b;
    char ar_1[10], ar_2[10];
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            s[i].push(i);
            block[i] = i;
        }
        while (cin >> ar_1) {
            if (ar_1[0] == 'q')
                break;
            cin >> a >> ar_2 >> b;
            if (a != b && block[a] != block[b]) {
                if (ar_1[0] == 'm') {
                    if (ar_2[1] == 'n') {
                        move_onto(a, b);
                    } else
                        move_over(a, b);
                } else {
                    if (ar_2[1] == 'n') {
                        pile_onto(a, b);
                    } else {
                        pile_over(a, b);
                    }
                }

            }
        }
        for (int i = 0; i < n; i++) {
            cout << i << ":";
            if (s[i].empty())
                cout << endl;
            else {
                while (!s[i].empty()) {
                    tmp.push(s[i].top());
                    s[i].pop();
                }
                while (!tmp.empty()) {
                    cout << " " << tmp.top();
                    tmp.pop();
                }
                cout << endl;
            }
        }
    }
    return 0;
}

void move_onto(int a, int b) {
    while (s[block[a]].top() != a) {
        int t = s[block[a]].top();
        s[t].push(t);
        block[t] = t;
        s[block[a]].pop();
    }
    while (s[block[b]].top() != b) {
        int t = s[block[b]].top();
        s[t].push(t);
        block[t] = t;
        s[block[b]].pop();
    }
    s[block[b]].pop();
    block[b] = b;
    s[b].push(b);

    s[b].push(s[block[a]].top());
    s[block[a]].pop();
    block[a] = b;
}

void move_over(int a, int b) {
    while (s[block[a]].top() != a) {
        int t = s[block[a]].top();
        s[t].push(t);
        block[t] = t;
        s[block[a]].pop();
    }
    s[block[b]].push(s[block[a]].top());
    s[block[a]].pop();
    block[a] = block[b];
}

void pile_onto(int a, int b) {
    while (s[block[b]].top() != b) {
        int t = s[block[b]].top();
        s[t].push(t);
        block[t] = t;
        s[block[b]].pop();
    }
    s[block[b]].pop();
    block[b] = b;
    s[b].push(b);

    while (s[block[a]].top() != a) {
        tmp.push(s[block[a]].top());
        s[block[a]].pop();
    }

    tmp.push(s[block[a]].top());
    s[block[a]].pop();

    while (!tmp.empty()) {
        s[block[b]].push(tmp.top());
        block[tmp.top()] = block[b];
        tmp.pop();
    }
}

void pile_over(int a, int b) {
    while (s[block[a]].top() != a) {
        tmp.push(s[block[a]].top());
        s[block[a]].pop();
    }
    tmp.push(s[block[a]].top());
    s[block[a]].pop();

    while (!tmp.empty()) {
        s[block[b]].push(tmp.top());
        block[tmp.top()] = block[b];
        tmp.pop();
    }
}

105 - The Skyline Problem, uva

#include<iostream>
#include<vector>
#include<deque>
#include<cstring>
using namespace std;
int H[10000];
int main() {
    int min = 10000;
    int max = 0;
    int x, y, h;
    memset(H, 0, sizeof (H));
    while (cin >> x >> h >> y) {
        if (x < min)
            min = x;
        if (y > max)
            max = y;
        for (int i = x; i < y; i++) {
            if (H[i] < h)
                H[i] = h;
        }
    }
    int cambio = H[min];
    cout << min << " " << cambio;
    for (int i = min + 1; i <= max; i++) {
        if(cambio != H[i])
        {
            cambio = H[i];
            cout << " "<< i << " " << cambio;
        }
    }
    cout << endl;
    return 0;
}

10010 - Where's Waldorf?, uva

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<vector>
#include<map>
#include<utility>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << "  " << #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
char matriz[50][50];
int main() {
    int t, m, n, k;
    scanf("%d\n", &t);
	map > mapa;
    for(int r = 0; r < t; r++){
		if(r != 0) printf("\n");
		mapa.clear();
        scanf("%d %d\n", &m, &n);
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                scanf("%c", &matriz[i][j]);
				matriz[i][j] = tolower(matriz[i][j]);
            }
			getchar();
        }
		scanf("%d", &k);
		vector words(k);
		vector found(k, false);
		for (int i = 0; i < k; i++) {
			cin >> words[i];
			transform(words[i].begin(), words[i].end(), words[i].begin(), ::tolower);
		}
		getchar();
		//solution
		bool ok = false;
		for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
				for(int v = 0; v < k; v++){
					if(found[v]) continue;
					int tam = words[v].size();
					ok = false;
					for(int x = -1; x <= 1 && !ok; x++){
						for(int y = -1; y <= 1 && !ok; y++){
							if(x == 0 && y == 0 && tam != 1) continue;
							if(i + tam * x >= -1 && i + tam * x <= m)
								if(j + tam * y >= -1 && j + tam * y <= n){
									ok = true;
									for(int s = 0; s < tam & ok; s++){
										if(words[v][s] != matriz[i + s * x][j + s * y]) ok = false;
									}
									if(ok) found[v] = true;
									if(ok) mapa[words[v]].first = i + 1, mapa[words[v]].second = j + 1;
								}
						}
					}
				}
            }
        }
		for(int i = 0; i < words.size(); i++){
			if(mapa[words[i]].first != 0)
				printf("%d %d\n", mapa[words[i]].first, mapa[words[i]].second);  
		}
    }
    return 0;
}

299 - Train Swapping, uva

#include<iostream>
#include<sstream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main(){
	int t, n;
	scanf("%d", &t);
	for(int k = 0; k < t; k++){
		scanf("%d", &n);
		vector lista(n);
for(int r = 0; r < n; r++){
			scanf("%d", &lista[r]);
		}
		int res = 0;
		for(int i = n; i > 1; i--)
for(int j = 0; j + 1 < i; j++){
				if(lista[j] > lista[j + 1]) {
swap(lista[j], lista[j + 1]);
res++;
}
}
printf("Optimal train swapping takes %d swaps.\n", res);
}
return 0;
}

673 - Parentheses Balance, uva

#include<iostream>
#include<sstream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main(){
	int t;
	scanf("%d\n", &t);
	string cadena;
	for(int i = 0; i < t; i++){
		stack pila;
		getline(cin, cadena);
		if(cadena.size() == 0) {
			printf("Yes\n");
			continue;
		}
		int len = cadena.size();
		int k = 0;
		for(; k < len; k++){
			if(cadena[k] == '(' || cadena[k] == '[')
				pila.push(cadena[k]);
			else
				if(!pila.empty() && ((pila.top() == '[' && cadena[k] == ']' )||
				(pila.top() == '(' && cadena[k] == ')'))) pila.pop();
				else break;
		}
		if(pila.empty() && k == len) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

One Little, Two Little, Three Little Endians , uva

#include<iostream>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
string complemento2(string cad){
	for(int i = 0; i < 32; i++) 
		cad[i] = cad[i] == '1' ? '0' : '1';
	bool carry = true;
	for(int i = 31; i >= 0 && carry; i--){
		if(cad[i] == '0') {
			if(carry)
				cad[i] = '1', carry = false;
		}
		else
			if(carry) cad[i] = '0';	
	}
	return cad;
}
int to_int(string cad){
	int factor = 1;
	if(cad[0] == '1')
	cad = complemento2(cad), factor *= -1;
	int num = 0;
	for(int i = 0; i < 32; i++){
		if(cad[i] == '1')
		num += pow(2., 31 - i);
	}
	return factor * num;
}
int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		bitset<32> bit_set = n;
		string num_b = bit_set.to_string();
		string concat = "", res = "";
		for(int i = 1; i <= 32; i++)
			if (i % 8 != 0) concat += num_b[i - 1];
			else concat += num_b[i - 1], res = concat + res, concat = "";
		int rpta = to_int(res);
		printf("%d converts to %d\n", n, rpta);
	}
	return 0;
}

Problem A: Football (aka Soccer) , uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<cctype>
#include<cmath>
#include<vector>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << "  " << #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
struct team{
string name;
int total_points;
int games_played;
int wins;
int ties;
int losses;
int goal_scored;
int goal_against;
};
bool cmp(team a, team b){
	if (a.total_points > b.total_points) 
		return true;
	else {
		if (a.total_points == b.total_points){
			if(a.wins > b.wins) 
				return true;
			else {
					if (a.wins == b.wins) {
						if ((a.goal_scored - a.goal_against) > (b.goal_scored - b.goal_against))
							return true;
						else {
								if ((a.goal_scored - a.goal_against) == (b.goal_scored - b.goal_against)) {
									if (a.goal_scored > b.goal_scored)
										return true;
									else {
											if (a.goal_scored == b.goal_scored) {
												if (a.games_played < b.games_played)
													return true;
												else {
													if (a.games_played == b.games_played) {
														if (strcasecmp(a.name.c_str(), b.name.c_str()) <= 0)
															return true;
														else 
															return false;
													}
													else 
														return false;
												}
											}
											else
												return false;
										}
								}
								else
									return false;
							}
					}
					else {
						return false;
					}
			}
		}
		else {
			return false;
		}
	}
}
int main(){
	int N, T, G, ptosA, ptosB;
	string teamA, teamB;
	string tournament;
	string linea;
	scanf("%d\n", &N);
	for (int cases = 0; cases < N; cases++) {
		if(cases != 0) printf("\n");
		getline(cin , tournament, '\n');
		scanf("%d\n", &T);
		team equipos[T];
		for (int i = 0; i < T; i++) {
			getline(cin, equipos[i].name, '\n');
			//db(equipos[i].name);
			equipos[i].total_points = 0;equipos[i].games_played = 0;
			equipos[i].wins = 0;equipos[i].ties = 0;equipos[i].losses = 0;
			equipos[i].goal_scored = 0;equipos[i].goal_against = 0;
		}
		scanf("%d\n", &G);
		for (int i = 0; i < G; i++) {
			getline(cin, linea , '\n');
			//db(linea);
			char *st, *buf, sep[] = "#@";
			buf = strdup(linea.c_str());
			st = strtok(buf, sep);
			teamA = st;
			st = strtok(0, sep);
			ptosA = atoi(st);
			st = strtok(0, sep);
			ptosB = atoi(st);
			st = strtok(0, sep);
			teamB = st;
			/*db2(teamA, ptosA);
			db2(teamB, ptosB);*/
			for (int k = 0; k < T; k++){
				if(equipos[k].name == teamA){
					if(ptosA > ptosB) equipos[k].wins++, equipos[k].total_points += 3;
					if(ptosA == ptosB) equipos[k].ties++, equipos[k].total_points++;
					if(ptosA < ptosB) equipos[k].losses++;
					equipos[k].games_played++;
					equipos[k].goal_scored += ptosA;
					equipos[k].goal_against += ptosB;
				}
				if(equipos[k].name == teamB){
					if(ptosB > ptosA) equipos[k].wins++, equipos[k].total_points += 3;
					if(ptosB == ptosA) equipos[k].ties++, equipos[k].total_points++;
					if(ptosB < ptosA) equipos[k].losses++;
					equipos[k].games_played++;
					equipos[k].goal_scored += ptosB;
					equipos[k].goal_against += ptosA;
				}
			}
		}
		sort(equipos, equipos + T, cmp);
		printf("%s\n", tournament.c_str());
		for (int k = 0; k < T; k++) {
			printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n", k + 1, equipos[k].name.c_str(), equipos[k].total_points, equipos[k].games_played, equipos[k].wins, equipos[k].ties, equipos[k].losses, (equipos[k].goal_scored - equipos[k].goal_against), equipos[k].goal_scored, equipos[k].goal_against);
		}
	}
	
}

612 - DNA Sorting, uva

// topcoder.cpp: define el punto de entrada de la aplicación de consola.
//
//#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<utility>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
bool cmp(const pair<int, string>& a,const pair<int, string>& b) {
 return a.first < b.first;
}
int val(const char* a) {
 int len = strlen(a), cont = 0;
 for (int i = 0; i < len; i++)
  for (int j = i + 1; j < len; j++)
   if(a[i] > a[j]) cont++;
 return cont;
}
int main() {
 /*freopen("in.in", "r", stdin);
 freopen("ou.out", "w", stdout);*/
 char linea[1000];
 int test, n, m;
 bool first = true;
 gets(linea);
 test = atoi(linea);
 gets(linea);
 while (test--) {
  gets(linea);
  sscanf(linea, "%d %d", &n, &m);
  vector<pair <int, string> > lista(m);
  for (int i = 0; i < m; i++) {
   gets(linea);
   lista[i] = make_pair(val(linea), linea);
  }
  gets(linea);
  stable_sort(lista.begin(), lista.end(), cmp);
  if(!first) printf("\n");
  first = false;
  for (int i = 0; i < m; i++) {
   printf("%s\n", lista[i].second.c_str());
  }
 }
 return 0;
}

10258 - Contest Scoreboard, uva

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
using namespace std;
struct team {
	int id, solved[11], penalty[11];
	bool submit;
	friend bool operator<(const team& a, const team& b) {
		if(a.solved[10] > b.solved[10]) return true;
		if(a.solved[10] == b.solved[10] && a.penalty[10] < b.penalty[10]) return true;
		if(a.solved[10] == b.solved[10] && a.penalty[10] == b.penalty[10] && a.id < b.id) return true;
		return false;
	}
};
team equipos[101];
void reset() {
		for (int i = 0; i < 101; i++) {
			equipos[i].id = i;
			memset(equipos[i].solved, 0, sizeof equipos[i].solved);
			memset(equipos[i].penalty, 0, sizeof equipos[i].penalty);
			equipos[i].submit = false;
		}
}
void calcular(void) {
	for (int i = 1; i < 101; i++) {
		if(!equipos[i].submit) continue;
		for (int x = 1; x < 10; x++) {
			{
				if(equipos[i].solved[x]) {
					equipos[i].solved[10] ++;
					equipos[i].penalty[10] += equipos[i].penalty[x];
				}
			}
		}
	}
}
int main() {
	int test, contestant, problem, time;
	char l;
	bool first = true;
	string linea;
	getline(cin, linea);
	test = atoi(linea.c_str());
	getline(cin, linea);
	while (test--) {
		reset();
		while (getline(cin, linea) && linea.size()) {
			sscanf(linea.c_str(), "%d %d %d %c", &contestant, &problem, &time, &l);
			equipos[contestant].submit = true;
			if(equipos[contestant].solved[problem]) continue;
			if(l == 'C' || l == 'I') {
				if (l == 'C') {
					equipos[contestant].solved[problem] = 1;
					equipos[contestant].penalty[problem] += time;
				}
				else 
					equipos[contestant].penalty[problem] += 20;
			}
		}
		calcular();
		if(!first) printf("\n");
		first = false;
		sort(equipos, equipos + 101);
		for (int i = 0; i < 101; i++) {
			if(equipos[i].submit)
				printf("%d %d %d\n", equipos[i].id, equipos[i].solved[10], equipos[i].penalty[10]);
		}
	}
	return 0;
}

483 - Word Scramble, uva

#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main(){
	string cadena;
	stringstream ss;
	bool first;
	while(getline(cin, cadena)){
		ss.clear();
		first = true;
		ss << cadena;
		while(ss >> cadena){
			reverse(cadena.begin(), cadena.end());
			if(first) {
				cout << cadena;
				first = false;
			}
			else
				cout << " "<< cadena;
		}
		cout << endl;
	}
	return 0;
}

10082 - WERTYU, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " -- "<< #b << " = " << b << endl;
using namespace std;
string palabra;
string nuevo;
int main(){
	map mapa;
	mapa['B'] = 'V'; mapa['L'] = 'K'; mapa['W'] = 'Q'; mapa['8'] = '7'; mapa[','] = 'M';
	mapa['C'] = 'X'; mapa['M'] = 'N'; mapa['X'] = 'Z'; mapa['9'] = '8'; mapa['.'] = ',';
	mapa['D'] = 'S'; mapa['N'] = 'B'; mapa['Y'] = 'T'; mapa['0'] = '9'; mapa['/'] = '.';
	mapa['E'] = 'W'; mapa['O'] = 'I'; mapa['1'] = '`'; mapa['-'] = '0'; mapa[' '] = ' ';
	mapa['F'] = 'D'; mapa['P'] = 'O'; mapa['2'] = '1'; mapa['='] = '-';
	mapa['G'] = 'F'; mapa['R'] = 'E'; mapa['3'] = '2'; mapa['['] = 'P';	
	mapa['H'] = 'G'; mapa['S'] = 'A'; mapa['4'] = '3'; mapa[']'] = '[';
	mapa['I'] = 'U'; mapa['T'] = 'R'; mapa['5'] = '4'; mapa['\\'] = ']';
	mapa['J'] = 'H'; mapa['U'] = 'Y'; mapa['6'] = '5'; mapa[';'] = 'L';
	mapa['K'] = 'J'; mapa['V'] = 'C'; mapa['7'] = '6'; mapa['\''] = ';';
	/*int tam_map = mapa.size();
	db(tam_map);
	for(map:: iterator it = mapa.begin(); it != mapa.end(); ++it){
		db2(it->first, it->second);
	}*/
	while(getline(cin , palabra)){ 
		int len = palabra.size();
		nuevo = "";
		for(int i = 0; i < len; i++){
			nuevo += mapa[palabra[i]];
		}
		cout << nuevo << endl;
	}
	return 0;
}

10363 - Tic Tac Toe, uva

#include <iostream>
#include <vector>
#include <cstdio>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;

int main() {
	int t, X, O, michiX, michiO, puroX, puroO;
	cin >> t;
	vector lista(3);
	for(int i = 0; i < t; i++){
		X = O = 0;
		for(int k = 0; k < 3; k++){
			cin >> lista[k];
			for(int u = 0; u < lista[k].size(); u++){
				if(lista[k][u] == 'X') X++;
				if(lista[k][u] == 'O') O++;
			}
		}
		michiX = michiO = puroX = puroO = 0;
		for(int i = 0; i < 3; i++){
			puroX = 0;
			puroO = 0;
			for(int j = 0; j < 3; j++){
				if(lista[i][j] == 'X') puroX++;
				if(lista[i][j] == 'O') puroO++;
			}
			if(puroX == 3) michiX++;
			if(puroO == 3) michiO++;
			puroX = 0;
			puroO = 0;
			for(int j = 0; j < 3; j++){
				if(lista[j][i] == 'X') puroX++;
				if(lista[j][i] == 'O') puroO++;
			}
			if(puroX == 3) michiX++;
			if(puroO == 3) michiO++;
		}
		puroX = 0;
		puroO = 0;
		for(int i = 0; i < 3; i++){
			if(lista[i][i] == 'X') puroX++;
			if(lista[i][i] == 'O') puroO++;
		}
		if(puroX == 3) michiX++;
		if(puroO == 3) michiO++;
		puroX = 0;
		puroO = 0;
		for(int i = 0; i < 3; i++){
			if(lista[i][2 - i] == 'X') puroX++;
			if(lista[i][2 - i] == 'O') puroO++;
		}
		if(puroX == 3) michiX++;
		if(puroO == 3) michiO++;
		if(michiX == 0 && michiO == 0){
			if( X - 1 == O || X == O) cout << "yes" << endl;
			else cout << "no" << endl;
		}
		else
			if((michiX == 1 || michiX == 2) && michiO == 0){
				if(X - 1 == O) cout << "yes" << endl;
				else cout << "no" << endl;
			}
			else 
				if(michiX == 0 && michiO == 1)
					if(X == O) cout << "yes" << endl;
					else cout << "no" << endl;
				else
					cout << "no" << endl;
	}
	return 0;
}

573 - The Snail, uva

#include<iostream>
#include<cstdio>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main(){
	double h, d, u, f;
	int days = 0;
	while(cin >> h >> u >> d >> f && h != 0){
		days = 0;
		double climbed = 0;
		double fac = (f * u) / 100.;
		while(true){
			days++;
			if(u >= 0) climbed += u;
			u -= fac;
			if(climbed > h) break;
			climbed -= d;
			if(climbed < 0) break;
		}
		if(climbed > h) printf("success on day %d\n", days);
		else printf("failure on day %d\n", days);
	}
	return 0;
}

739 - Soundex Indexing, uva

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
map mapa;
string procesar_codigo(string palabra){
	string res = "";
	res += palabra[0];
	for(int i = 1; i < palabra.size() && res.size() < 5; i++){
		res += (mapa[palabra[i - 1]] != mapa[palabra[i]]) ? mapa[palabra[i]] : "";
	}
	if(res.size() == 5) res = res.substr(0,4);
	if(res.size() < 4)
	res += string(4 - res.size(), '0');
	return res;
}
int main(){
	string linea;
	mapa['B'] = "1"; mapa['C'] = "2"; mapa['J'] = "2"; mapa['D'] = "3"; mapa['N'] = "5";
	mapa['P'] = "1"; mapa['S'] = "2"; mapa['Q'] = "2"; mapa['T'] = "3"; mapa['R'] = "6";
	mapa['F'] = "1"; mapa['K'] = "2"; mapa['X'] = "2"; mapa['L'] = "4"; 
	mapa['V'] = "1"; mapa['G'] = "2"; mapa['Z'] = "2"; mapa['M'] = "5";
	
	mapa['A'] = ""; mapa['U'] = "";
	mapa['E'] = ""; mapa['Y'] = "";
	mapa['I'] = ""; mapa['W'] = "";
	mapa['O'] = ""; mapa['H'] = "";
	cout << "         NAME                     SOUNDEX CODE" << endl;
	while(cin >> linea){
		string res = string(9, ' ');
		res += linea;
		string aumento = string(25 - linea.size(),' ');
		res += aumento + procesar_codigo(linea);
		cout << res << endl;
	}
	string s = string(19,' ');
	s += "END OF OUTPUT";
	cout << s << endl;
	return 0;
}

11616 - Roman Numerals, uva

#include<iostream>
#include<cstdio>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int divisores[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string romanos[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int main(){
	string numero;
	int num;
	while(cin >> numero){
		int len = numero.size();
		num = 0;
		if(numero[0] > '0' && numero[0] <= '9'){
			int p = 1;
			for(int i = 0; i < len; i++){
				num += p * (numero[len - i - 1] - 48); 
				p *= 10;
			}
			string res = "";
			for(int i = 0; i < 13; i++){
				if(num >= divisores[i]){
					int div = num / divisores[i];
					num = num % divisores[i];
					for(int k = 0; k < div; k++)
						res += romanos[i];
				}
			}
			cout << res << endl;
			
		}
		else{
			for(int i = 0; i < len; i++){
				if(numero[i] == 'M') {
					num += 1000;
					continue;
				}
				if(numero[i] == 'C' && i + 1 < len && numero[i + 1] == 'M') {
					num += 900;
					i++;
					continue;
				}
				if(numero[i] == 'D') {
					num += 500;
					continue;
				}
				if(numero[i] == 'C' && i + 1 < len && numero[i + 1] == 'D') {
					num += 400;
					i++;
					continue;
				}
				else if(numero[i] == 'C') {
					num += 100;
					continue;
				}
				if(numero[i] == 'X' && i + 1 < len && numero[i + 1] == 'C') {
					num += 90;
					i++;
					continue;
				}
				if(numero[i] == 'L') {
					num += 50;
					continue;
				}
				if(numero[i] == 'X' && i + 1 < len && numero[i + 1] == 'L') {
					num += 40;
					i++;
					continue;
				}
				if(numero[i] == 'X') {
					num += 10;
					continue;
				}
				if(numero[i] == 'I' && i + 1 < len && numero[i + 1] == 'X') {
					num += 9;
					i++;
					continue;
				}
				if(numero[i] == 'V') {
					num += 5;
					continue;
				}
				if(numero[i] == 'I' && i + 1 < len && numero[i + 1] == 'V') {
					num += 4;
					i++;
					continue;
				}
				if(numero[i] == 'I') {
					num++;
					continue;
				}
			}
			cout << num << endl;
		}
	}
	return 0;
}

10141 - Request for Proposal, uva

#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<set>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " -- "<< #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main(){
	double compliance, min_price;
	int p, n, num_met;
	string linea, name_aux, name;
	double min_price_aux;
	int cont = 0;
	while(scanf("%d%d\n", &n , &p)){
		if(n == 0 && p == 0) break;
		min_price = numeric_limits::max();
		compliance = 0.;
		if (cont != 0)printf("\n");
		for(int k = 0; k < n; k++) getline(cin, linea, '\n');
		
		for(int t = 0; t < p; t++){
			getline(cin, name_aux, '\n');
			scanf("%lf%d\n",&min_price_aux, &num_met);
			for(int k = 0; k < num_met; k++)getline(cin, linea, '\n');
			if(num_met > compliance){
				compliance = num_met;
				min_price = min_price_aux;
				name = name_aux;
			}
			else{
				if(num_met == compliance && min_price_aux < min_price){
					min_price = min_price_aux;
					name = name_aux;
				}
			}
		}
		printf("RFP #%d\n%s\n", ++cont,name.c_str());
	}
	return 0;
}

11340 - Newspaper, uva

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " -- "<< #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main(){
	map mapa;
	int t = 0, keys, lines, valor;
	double pagar = 0.;
	string linea;
	char test[10], clave;
	bool first;
	cin.getline(test, 10, '\n');
	t = atoi(test);
	for(int i = 0; i < t; i++){
		mapa.clear();
		pagar =0.;
		cin.getline(test, 10, '\n');
		keys = atoi(test);
		for(int k = 0; k < keys; k++){
			getline(cin, linea);
			char *st, *buf, sep[] = " ";
			buf = strdup(linea.c_str());
			st = strtok(buf, sep);
			first = true;
			valor  = 0;
			while(st){
				if(first){
					clave = st[0];
					first = false;
				}
				else{
					valor = atoi(st);
				}
				st = strtok(0, sep);
			}
			mapa[clave] = valor;
		}
		cin.getline(test, 10, '\n');
		lines = atoi(test);
		//db(lines);
		for(int l = 0; l < lines; l++){
			getline(cin, linea);
			int len = linea.size();
			for(int v = 0; v < len; v++){
				if(mapa[linea[v]]) pagar += mapa[linea[v]] * 0.01;
			}
		}
		printf("%.2f$\n", pagar);
	}
	/*foreach(it, mapa){
		db2(it->first, it->second);
	}*/
	return 0;
}

10420 - List of Conquests, uva

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main(){
	int t;
	string linea;
	char test[10];
	cin.getline(test, 10,'\n');
	t = atoi(test);
	map mapa;
	for(int i = 0; i < t; i++){
		getline(cin, linea);
		char *st, *buf, sep[] = " ";
		buf = strdup(linea.c_str());
		st = strtok(buf, sep);
		while(st){
			mapa[st]++;
			break;
		}
	}
	foreach(it, mapa){
		printf("%s %d\n", it->first.c_str(), it->second);
	}
	return 0;
}

837 - Light and Transparency, uva

#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " -- "<< #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
struct segmento{
	double x0, x, factor;
	segmento(double px0, double px, double pfactor):x0(px0), x(px), factor(pfactor){};
};
int main(){
	int t, n;
	double x1, y1, x2, y2, factor;
	char num_seg[10];
	string linea;
	stringstream ss;
	cin.getline(num_seg, 10, '\n');
	t = atoi(num_seg);
	vector segmentos;
	vector puntos;
	for(int i = 0; i < t; i++){
		segmentos.clear();
		puntos.clear();
		getchar();
		cin.getline(num_seg, 10, '\n');
		n = atoi(num_seg);
		for(int k = 0; k < n; k++){
			getline(cin , linea);
			ss.clear();
			ss << linea;
			ss >> x1 >> y1 >> x2 >> y2 >> factor;
			puntos.push_back(x1);
			puntos.push_back(x2);
			if(x1 > x2) swap(x1, x2);
			segmento el_segmento(x1, x2, factor);
			segmentos.push_back(el_segmento);
		}
		//para los puntos
		set setpuntos(puntos.begin(), puntos.end());
		vector puntitos(setpuntos.begin(), setpuntos.end());
		sort(puntitos.begin(), puntitos.end());
		int puntos_size = puntitos.size();
		printf("%d\n", puntos_size + 1);
		printf("-inf %.3f 1.000\n",puntitos[0]);
		for(int k = 0; k + 1 < puntos_size; k++){
			factor = 1.0;
			double x = puntitos[k];
			for(int h = 0; h < segmentos.size(); h++){
				if(segmentos[h].x0 <= x && x < segmentos[h].x)
					factor *= segmentos[h].factor;
			}
			printf("%.3f %.3f %.3f\n",x, puntitos[k + 1], factor);
		}
		printf("%.3f +inf 1.000\n",puntitos[puntos_size - 1]);
		if(i + 1 != t) printf("\n");
		
		
	}
	return 0;
}

10703 - Free spots, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define db(a) cout << #a << " = " << a << endl;
int board[500][500];
using namespace std;
int main(){
	int W, H, N, X1, Y1, X2, Y2, total;
	while(scanf("%d%d%d", &W, &H, &N)){
		if(W == 0 && H == 0 && N == 0) break;
		total = W * H;
		for(int i = 0; i < H; i++)
				for(int j = 0; j < W; j++)
					board[i][j] = 1;
		for(int k = 0; k < N; k++){
			scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);
			X1--, Y1--, X2--, Y2--;
			if(X1 > X2) swap(X1, X2);
			if(Y1 > Y2) swap(Y1, Y2);
			for(int i = Y1; i <= Y2; i++)
				for(int j = X1; j <= X2; j++)
					if(board[i][j]) board[i][j] = 0, total--;
		}
		if(total) 
			if(total != 1) 
				printf("There are %d empty spots.\n", total);
			else 
				printf("There is one empty spot.\n");
		else
			printf("There is no empty spots.\n");
	}
	return 0;
}

11223 - O: dah dah dah, uva

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
string evaluar(string buf){
	 return buf.size() == 2 ? " " : "";
}
int main(){
	map mapa;
	mapa[".-"] = "A";mapa[".---"] = "J";mapa[".-."] = "R";mapa["--.."] = "Z";mapa["---.."] = "8";
	mapa["-..."] = "B";mapa["-.-"] = "K";mapa["..."] = "S";mapa["-----"] = "0";mapa["----."] = "9";
	mapa["-.-."] = "C";mapa[".-.."] = "L";mapa["-"] = "T";mapa[".----"] = "1";mapa[".-.-.-"] = ".";
	mapa["-.."] = "D";mapa["--"] = "M";mapa["..-"] = "U";mapa["..---"] = "2";mapa["--..--"] = ",";
	mapa["."] = "E";mapa["-."] = "N";mapa["...-"] = "V";mapa["...--"] = "3";mapa["..--.."] = "?";
	mapa["..-."] = "F";mapa["---"] = "O";mapa[".--"] = "W";mapa["....-"] = "4";mapa[".----."] = "'";
	mapa["--."] = "G";mapa[".--."] = "P";mapa["-..-"] = "X";mapa["....."] = "5";mapa["-.-.--"] = "!";
	mapa["...."] = "H";mapa["--.-"] = "Q";mapa["-.--"] = "Y";mapa["-...."] = "6";mapa["-..-."] = "/";
	mapa[".."] = "I";mapa["--.-"] = "Q";mapa["-.--.-"] = ")";mapa["--..."] = "7";mapa["-.--."] = "(";
	mapa[".-..."] = "&";mapa["---..."] = ":";mapa["-.-.-."] = ";";mapa["-...-"] = "=";mapa[".-.-."] = "+";
	mapa["-....-"] = "-";mapa["..--.-"] = "_";mapa[".-..-."] = "\"";mapa[".--.-."] = "@";mapa[""] = "";
	//freopen("ou.out", "w", stdout);
	int t = 0;
	char test[2];
	string linea, res = "", buf, morse;
	cin.getline(test, 2, '\n');
	t = atoi(test);
	for(int i = 0; i < t; i++){
		getline(cin , linea);
		res = "";
		buf = "";
		morse = "";
		for(int k = 0; k < linea.size(); k++){
			if(linea[k] == ' ') {
				res += mapa[morse];
				morse = "";
				buf += ' ';
			}
			else{
				res += evaluar(buf);
				buf = "";
				morse += linea[k];
			}
		}
		res += mapa[morse];
		if(i + 1 == t)
			printf("Message #%d\n%s\n", i + 1, res.c_str());
		else
			printf("Message #%d\n%s\n\n", i + 1, res.c_str());
	}
}

10683 - The decadary watch, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " -- "<< #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main(){
	string t;
	int HH, MM, SS, CC, g;
	while(cin >> t){
		HH = (t[0] - 48)*10 + (t[1] - 48);
		MM = (t[2] - 48)*10 + (t[3] - 48);
		SS = (t[4] - 48)*10 + (t[5] - 48);
		CC = (t[6] - 48)*10 + (t[7] - 48);
		g = HH * 3600 + MM * 60 + SS;
		g *= 100;
		g += CC;
		g = (125 * g) / 108;
		printf("%07d\n", g);
	}
	return 0;
}

11727 - Cost Cutting - UVA

#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main(){
 int a, b, c, t;
 cin >> t;
 int i = 1;
 while(t--){
  cin >> a >> b >> c;
  if(a > b) swap(a, b);
  if(a > c) swap(a, c);
  if(b > c) swap(b, c);
  cout << "Case "<< i++ << ": " << b << endl;
 }
 return 0;
}

661 - Blowing Fuses - UVA

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
#include 
using namespace std;
int main(){
 int n, m, c;
 int cont = 1;
 //freopen("in.in", "r", stdin);
 //freopen("ou.out", "w", stdout);
 while(cin >> n >> m >> c){
  if(n == 0 && m == 0 && c == 0) break;
  vector estado(n + 1, false);
  vector consumo(n + 1, 0);
  for(int i = 1; i <= n; i++){
   cin >> consumo[i];
  }
  int maxi = 0;
  int id = 0;
  int res = 0;
  bool blown = false;
  for(int i = 1; i <= m && !blown; i++){
   cin >> id;
   if(estado[id]){
    maxi -= consumo[id];
    estado[id] = false;
   }
   else{
    maxi += consumo[id];
    if(maxi > c) {
     blown = true;
     for(int r = i + 1; r <= m; r++) cin >> id;
    }
    estado[id] = true;
    res = max(res, maxi);
   }
  }
  cout << "Sequence " << cont++ << endl;
  if(!blown) {
   cout << "Fuse was not blown." << endl;
   cout << "Maximal power consumption was " << res << " amperes." << endl << endl;
  }
  else{
   cout << "Fuse was blown." << endl << endl;
  }
 }
 return 0;
}

10281 - Average Speed - UVA

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstdlib>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int seconds(int h, int m, int s){
 return h * 3600 + m * 60 + s;
}
int main(){
 string linea, tiempo;
 int h, m, s;
 float recorrido = 0;
 stringstream ss;
 /*freopen("in.in", "r", stdin);
 freopen("ou.out", "w", stdout);*/
 int current_time = 0;
 float velocidad_ini = 0;
 bool primero = true;
 while(getline(cin, linea)){
  ss.clear();
  ss << linea;
  bool first = true;
  while(ss >> linea){
   if(first){
    sscanf(linea.c_str(), "%d:%d:%d", &h, &m, &s);
    tiempo = linea;
    first = false;
   }
   else first = true;
  }
  if(first){
   if(primero){ 
    recorrido = 0; 
    primero = false;
    current_time = seconds(h, m, s);
   }
   else {
    recorrido += (seconds(h, m, s) - current_time) * velocidad_ini / 3600.;
    current_time = seconds(h , m, s);
   }
   velocidad_ini = atoi(linea.c_str());
  }
  else{
   int tiempo_reporte = seconds(h, m, s) - current_time;
   float distancia = velocidad_ini * tiempo_reporte / 3600.;
   distancia += recorrido;
   printf("%s %.2f km\n", tiempo.c_str(), distancia);
  }
 }
 
 return 0;
}

10901 - Ferry Loading III - UVA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define db(a) cout << #a << " = " << a << endl;
#define foreach(it,l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main() {
 int c, n, t, m, val, kr = 0, kl = 0, cap = 0, time = 0, cont = 0;
 char direccion[20];
 scanf("%d", &c);
 for (int k = 0; k < c; k++) {
  queue<int> left, right;
  scanf("%d %d %d", &n, &t, &m);
  kr = kl = 0;
  vector<int> posiciones(m);
  cont = 0;
  for (int i = 0; i < m; i++) {
   scanf("%d %s", &val, direccion);
   if(strcmp(direccion,"left") == 0) 
    left.push(val), kl++,posiciones[cont++] = 0;
   else 
    right.push(val), kr++,posiciones[cont++] = 1;
  }
  vector<int> listaL(kl), listaR(kr);
  kl = kr = cap = time = 0;
  string ini = "left";
  while (!left.empty() || !right.empty()) {
   if (!left.empty() && !right.empty()) {
    if(left.front() > time && right.front() > time) {
     if(left.front() > right.front()) {
      time += right.front() - time;
      if(ini == "left") time += t;
      ini = "right";
     }
     else {
      time += left.front() - time;
      if(ini == "right") time += t;
      ini = "left";
     }
    }
   }
   else {
    if (left.empty()) {
     if (right.front() > time) {
      time += right.front() - time;
      if(ini == "left") time += t;
      ini = "right";
     }
    }
    else {
     if (left.front() > time) {
      time += left.front() - time;
      if(ini == "right") time += t;
      ini = "left";
     }
    }
   }
   if (ini == "left") {
    cap = 0;
    while (cap < n && !left.empty() && left.front() <= time) {
     //printf("left %d\n", time + t);
     listaL[kl++] = time + t;
     left.pop();
     cap++;
    }
    time += t;
    ini = "right";
   }
   else {
    cap = 0;
    while (cap < n && !right.empty() && right.front() <= time) {
     //printf("right %d\n", time + t);
     listaR[kr++] = time + t;
     right.pop();
     cap++;
    }
    time += t;
    ini = "left";
   }
  }
  kl = kr = 0;
  for (int i = 0; i < m; i++) {
   if (!posiciones[i])
    printf("%d\n", listaL[kl++]);
   else
    printf("%d\n", listaR[kr++]);
  }
  if(k + 1 != c) printf("\n");
 }
 return 0;
}

336 - A Node Too Far - UVA

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int main() {
	int from, to, nc, ttl, t = 1, llega, total_nodes;
	map< int,vector > adyacencia;
	map< int, int > dist;
	while (cin >> nc && nc) {
		adyacencia.clear();
		for (int i = 0; i < nc; i++) {
			cin >> from >> to;
			adyacencia[from].push_back(to);
			adyacencia[to].push_back(from);
		}
		total_nodes = adyacencia.size();
		while (cin >> from >> ttl) {
			if (from == 0 && ttl == 0) break;
			dist.clear();
			queue q;
			q.push(from);
			dist[from] = 0;
			while (!q.empty()) {
				int u = q.front(); q.pop();
				//printf("Visit %d, Layer %d\n", u, dist[u]);
				for (int i = 0; i < adyacencia[u].size(); i++) {
					if (!dist.count(adyacencia[u][i])) {
						dist[adyacencia[u][i]] = dist[u] + 1;
						q.push(adyacencia[u][i]);
					}
				}
			}
			llega = 0;
			for (map::iterator it = dist.begin(); it != dist.end(); it++) {
				if (it->second <= ttl) llega++;
			}
			printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", t++, total_nodes - llega, from, ttl);
		}
	}
	return 0;
}

727 - Equation - UVA

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <stack>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main ()
{
  char c[2];
  int cont = 0, casos;
  void *p;
  string res = "";
  scanf("%d", &casos);
  gets(c);
  gets(c);
  for (int i = 0; i < casos; i++) {
 res = "";
 stack<char> pila;
  while(1) {
   p = gets(c);
   if (p == NULL) break;
   if (c[0] == '\0') break;
   //original += c[0];
   if (isdigit(c[0])) res += c[0];
   else {
    if (c[0] == ')') {
     while(pila.top() != '(') {
      res += pila.top();
      pila.pop();
     }
     pila.pop();
     continue;
    }
    if (c[0] == '(') {
     pila.push(c[0]);
     continue;
    }    
    if(c[0] != '*' && c[0] != '/' && c[0] != '+' && c[0] != '-') continue;
    if (pila.empty()) {
     pila.push(c[0]);
     continue;
    }
    while(!pila.empty() && pila.top() != '(' && ((pila.top() == '*' || pila.top() == '/')
    || !((pila.top() == '+' || pila.top() == '-') && (c[0] == '*' || c[0] == '/')))) {
      res += pila.top();
      pila.pop();
    }
    pila.push(c[0]);
   }
  }
 while (!pila.empty()) {
  res += pila.top();
  pila.pop();
 }
 //db(original);
 if(i + 1 == casos)
  printf("%s\n", res.c_str());
 else
  printf("%s\n\n", res.c_str());
  }
  return 0;
}

514 - Rails - UVA

#include<cstdio>
#include<stack>
using namespace std;
int main() {
 int n, val;
 while (1) {
  scanf("%d", &n);
  if (n == 0) break;
  while (1) {
   scanf("%d", &val);
   if (val == 0) {
    printf("\n");
    break;
   }
   stack A, B;
   A.push(val);
   for (int i = 1; i < n; i++) {
    scanf("%d", &val);
    A.push(val);
   }
   int i = n;
   for (; i >= 1;) {
    if (!B.empty() && B.top() == i) {
     B.pop();
     i--;
     continue;
    }
    if (A.empty()) break;
    if (A.top() != i) B.push(A.top());
    else i--;
    A.pop();
    
   }
   if (A.empty() && B.empty()) puts("Yes");
   else puts("No");
  }
 }
 return 0;
}

127 - Accordian Patience - UVA

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<stack>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
using namespace std;
int total = 0;
struct carta {
 char *kind;
 carta(char *kind) : kind(kind) {}
};
void move(vector< stack<carta> >& cartas,const int& target,const int& source) {
 cartas[target].push(cartas[source].top());
 cartas[source].pop();
 if(cartas[source].empty()) total--, cartas.erase(cartas.begin() + source);
 
}
bool can(vector< stack<carta> >& cartas,const int& target,const int& source) {
 return cartas[target].top().kind[0] == cartas[source].top().kind[0] ||
 cartas[target].top().kind[1] == cartas[source].top().kind[1];
}
void jugar(vector< stack<carta> >& cartas) {
int i = 0;
again:
 for (; i < total; i++) {
  if (i >= 3 && can(cartas, i - 3, i)) {
   move(cartas, i - 3, i);
   i = i - 3;
   goto again;
  }
  else if( i >= 1 && can(cartas, i - 1, i)) {
   move(cartas, i - 1, i); 
   i = i - 1;
   goto again;
  }
 }
}
int main() {
 char line[200], line2[200];
 bool fin = false;
 while(1) {
  total = 52;
  vector< stack<carta> > cartas(52);
  gets(line);
  if(line[0] == '#') break;
  char *st, sep[] = " ";
  st = strtok(line, sep);
  int i = 0;
  while (st) {
   carta card(st);
   cartas[i++].push(card);
   st = strtok(0, sep);
  }
  gets(line2);
  st = strtok(line2, sep);
  while (st) {
   carta card(st);
   cartas[i++].push(card);
   st = strtok(0, sep);
  }
  jugar(cartas);
  printf("%d pile%s remaining:", total, (total > 1) ? "s" : "");
  for (int i = 0; i < total; i++) {
   if(!cartas[i].empty()) printf(" %d", cartas[i].size());
  }
  printf("\n");
 }
 return 0;
}

11495 - Bubbles and Buckets - UVA

#include<cstdio>
using namespace std;
int lista[100000], res = 0;
void merge(const int& ini, const int& med, const int& fin) {
 int i = ini;
 int j = med + 1;
 int k = 0;
 int vector[fin - ini + 1];
 while (i <= med && j <= fin) {
  if(lista[i] <= lista[j])
   vector[k++] = lista[i++];
  else
   vector[k++] = lista[j++], res += med - i + 1;
 }
 while (i <= med) vector[k++] = lista[i++];
 while (j <= fin) vector[k++] = lista[j++];
 
 for (i = 0; i < k; i++) lista[ini + i] = vector[i];
 
}
void merge_sort(const int& ini, const int& fin) {
 if (ini < fin) {
  int med = (ini + fin) / 2;
  merge_sort(ini, med);
  merge_sort(med + 1, fin);
  merge(ini, med, fin);
 }
}
int main() {
 int n;
 while(scanf("%d", &n) && n) {
  res = 0;
  for (int i = 0; i < n; i++)
   scanf("%d", lista + i);
  merge_sort(0, n - 1);
  if(res % 2 == 0) 
   puts("Carlos");
  else
   puts("Marcelo");
 }
 return 0;
}

10810 - Ultra-QuickSort - UVA

#include<cstdio>
#include<cstdlib>
using namespace std;
long long res = 0;
void juntar(int* lista, const int& ini,const int& med, const int& fin) {
 int vector[fin - ini + 1];
 int i = ini;
 int j = med + 1;
 int k = 0;
 while (i <= med && j <= fin) 
  if (lista[i] <= lista[j])
   vector[k++] = lista[i++];
  else
   vector[k++] = lista[j++], res += med - i + 1;
 while (i <= med) vector[k++] = lista[i++];
 while (j <= fin) vector[k++] = lista[j++];
 
 for (i = 0; i < k; i++) lista[ini + i] = vector[i];
 //free(vector);
}
void merge_sort(int* lista,const int& ini,const int& fin) {
 if (ini < fin) {
  int med = (ini + fin) / 2;
  merge_sort(lista, ini, med);
  merge_sort(lista, med + 1, fin);
  juntar(lista, ini, med, fin);
 }
}
void mostrar(int* lista, const int& n) {
 for (int i = 0; i < n; i++)
  printf("%d ", *(lista + i));
 printf("\n");
}
int main() {
 int n, lista[500000];
 while(scanf("%d", &n)) {
  if (n == 0) break;
  res = 0;
  for (int i = 0; i < n; i++)
   scanf("%d", lista + i);
  merge_sort(lista, 0, n - 1);
  printf("%lld\n", res);
 }
 return 0;
}

11040 - Add bricks in the wall

#include<iostream>
#include<cstring>
using namespace std;
int main() {
 ios_base::sync_with_stdio(false);
 int matriz[9][9], t;
 cin >> t;
 while (t--) {
  memset(matriz, 0, sizeof matriz);
  for (int i = 0; i < 5; i++) {
   for (int k = 0; k < i + 1; k++) {
    cin >> matriz[i * 2][k * 2];
   }
  }
  for (int i = 0; i < 9; i += 2) {
   for (int k = 1; k < i; k += 2){
    matriz[i][k] = (matriz[i - 2][k - 1] - matriz[i][k - 1] - matriz[i][k + 1]) / 2;
    matriz[i - 1][k - 1] = matriz[i][k - 1] + matriz[i][k];
    matriz[i - 1][k] = matriz[i][k] + matriz[i][k + 1];
   }
  }
  for (int i = 0; i < 9; i++) {
   bool first = true;
   for (int j = 0; j < i + 1; j++) {
    if (first) {
     cout << matriz[i][j];
     first = false;
    }
    else
     cout << " " << matriz[i][j];
   }
   cout << endl;
  }
 }
 return 0;
}

Equation - TJU

#include<cstdio>
#include<cmath>
using namespace std;
int main() {
	int n, t, ways, z;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		scanf("%d", &n);
		ways = 0;
		for (int x = 0; x <= 1000; x++)
			for (int y = x; y <= 1000; y++) {
				if(n - x * x - y * y < 0) break;
				z = sqrt(n - x * x - y * y);
				if(z <= 1000 && z * z == (n - x * x - y * y)) {
					if(x == y) ways++;
					else ways += 2;
				}
			}
		printf("%d\n", ways);
	}
	return 0;
}

344 - Roman Digititis - UVA

#include<iostream>
#include<map>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int main() {
	int n;
	string romanos[] = {"c", "xc", "l", "xl", "x", "ix", "v", "iv", "i"}; 
	char rom[] = {'c', 'l', 'x', 'v', 'i'}; 
	int val[] = {100, 90, 50, 40, 10, 9, 5, 4, 1}; 
	while(cin >> n) {
		if(n == 0) break;
		map mapa;
		for (int k = 1; k <= n; k++) {
			int m = k;
			string cad = "";
			for (int i = 0; i < 9; i++) {
				int div = m / val[i];
				m = m % val[i];
				for (int u = 0; u < div; u++) {
					cad += romanos[i];
				}
			}
			//db(cad);
			for (int i = 0; i < cad.size(); i++)
				mapa[cad[i]]++;
		}
		cout << n << ": ";
		for (int i = 4; i >= 0; i--) {
			if(i != 0)
				cout << mapa[rom[i]] << " " << rom[i] << ", ";
			else
				cout << mapa[rom[i]] << " " << rom[i];
		}
		cout << endl;
	}
	return 0;
}

Reloj - CodeForces

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << "  " << #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
string reves(int a) {
	char arr[10];
	sprintf(arr, "%02d", a);
	int len = strlen(arr);
	reverse(arr , arr + len);
	return arr;
}
int main() {
	int H, M;	
	string hora;
	while(cin >> hora) {
		char res[10];
		bool find = false, first = true;
		sscanf(hora.c_str(), "%d:%d", &H, &M);
		for (int h = 0; h < 24 && !find; h++) {
			int m = 0;
			if(first) {
				m = M + 1;
				first = false;
			}
			for (; m < 60 && !find; m++) {
				char mc[10];
				sprintf(mc, "%02d", m);
				if(reves((h + H) % 24) == mc) 
				sprintf(res, "%02d:%02d", (h + H) % 24, m), find = true;
			}
		}
		cout << res << endl;
	}
	return 0;
}

Multiple of 11

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	string numero = "";
	while(cin >> numero && numero != "0"){
		int tam = numero.size();
		int sumpar = 0,sumimpar = 0;
		for(int i = 0; i < tam; i++){
			if(i % 2 == 0) sumimpar += numero[tam - i - 1] - 48;
			else sumpar += numero[tam - i - 1] - 48;
		}
		if((sumimpar - sumpar) % 11 == 0) cout << numero << " is a multiple of 11." << endl; 
		else cout << numero << " is not a multiple of 11." << endl; 
	}
	return 0;
}

Count Square

#include<iostream>
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main() {
    int h, v;
	ios_base::sync_with_stdio(false);
    while(cin >> h >> v) {
        vector H(h), V(v);
        for (int i = 0; i < h; i++)  cin >> H[i];
        for (int i = 0; i < v; i++)  cin >> V[i];
        vector difH, difV;
		map mapaH, mapaV;
        for (int i = 0; i + 1 < h; i++)
            for (int j = i + 1; j < h; j++)
                mapaH[H[j] - H[i]]++;
        for (int i = 0; i + 1 < v; i++)
            for (int j = i + 1; j < v; j++)
                mapaV[V[j] - V[i]]++;
        int ways = 0;
        map ::iterator it;
        for (it = mapaH.begin(); it != mapaH.end(); it++)
            ways += it->second * mapaV[it->first];
        cout << ways << endl;
    }
    return 0;
}

PKU 3517 And Then There Was One

#include<cstdio>
#include<iostream>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl;
using namespace std;
int lista[10000];
bool func_del(int a) {
 return a == -1;
}
int* borrar_si(int *ini, int *fin) {
 int *hasta = ini;
 for (; ini != fin; ini++) {
  if (!func_del(*ini)) *hasta++ = *ini;
 }
 return hasta;
}
int main() {
 int n, k, m;
 while ( scanf("%d%d%d", &n, &k, &m) ) {
  if (n == 0 && k == 0 && m == 0) break;
  for (int i = 0; i < n; i++) lista[i] = i + 1;
  int start = m - 1;
  int n2 = n;
  for (int i = 0; i < n - 1; i++) {
   lista[start] = -1;
   start += k;
   if(start >= n2) {
    start -= n2;
    n2 = borrar_si (lista, lista + n2) - lista;
    start %= n2;
   }
  }
  for (int i = 0; i < n2; i++) 
   if(lista[i] != - 1) {
    printf("%d\n", lista[i]);
    break;
   }
 }
 return 0;
}

11960 - Divisor Game - UVA

#include<cstdio>
#define MAX 1009
using namespace std;
int crivo[MAX + 1];
int primos[MAX + 1];
int maximos[1000001];
int numbers[1000001];
int n_primos = 0;
void init_crivo() {
 int i, j;
 for (i = 2; i <= MAX; i++) {
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (j = i; i * j <= MAX; j++)
    crivo[i * j] = 1;
  }
 }
}
int NOD(int n) {
 if(n == 1) return 1;
 if(n <= MAX && !crivo[n]) return 2;
 int j, r = 1;
 for (int i = 0; primos[i] * primos[i] <= n; i++) {
  j = 1;
  while(n % primos[i] == 0) {
   n /= primos[i];
   j++;
  }
  r *= j;
  if(n == 1) return r;
 }
 if(r == 1) return 2;
 return r * 2;
}
int main() {
 int k, t, n;
 init_crivo();
 for (int i = 1; i <= 1000000; i++) {
  maximos[i] = NOD(i);
  numbers[i] = maximos[i] >= maximos[numbers[i - 1]] ? i : numbers[i - 1];
 }
 scanf("%d", &t);
 for(k = 0; k < t; k++) {
  scanf("%d", &n);
  printf("%d\n", numbers[n]);
 }
 return 0;
}

palindromics primes TopCoder

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
class PrimePalindromic {
 public:
  string str(int n) {
   char arr[10];
   sprintf(arr, "%d", n);
   return arr;
  }
  bool pal(string s) {
   int len = s.size();
   for (int i = 0; i < len / 2; i++)
    if(s[i] != s[len - i - 1]) return false;
   return true;
  }
  int count(int A, int B) {
   int T[20];
   int res = 0;
   for (int k = A; k <= B; k++) {
    int num = k, j = 0;
    for (int i = 2; i <= sqrt(num); i++)
     while(num % i == 0) num /= i, T[j++] = i;
    if(num > 1) T[j++] = num;
    bool find = false;
    do {
     string s = "";
     for (int i = 0; i < j; i++)
      s += str(T[i]);
     if(pal(s)) find = true;
    } while(next_permutation(T, T + j) && !find);
    if(find) res++;
   }
   return res;
  }
};
int main() {
 int a, b;
 while(cin >> a >> b) {
  cout << PrimePalindromic().count(a, b) << endl;
 }
 return 0;
}

Goldbach's Conjecture - TJU

#include<cstdio>
#define MAX 1010
int crivo[MAX + 1];
int primos[MAX + 1];
int n_primos = 0;
using namespace std;
void init_crivo() {
for (int i = 2; i <= MAX; i++)
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (int j = i; i * j <= MAX; j++)
    crivo[i * j] = 1;
  }
}
bool es_primo(int n) {
 if(n == 1) return false;
 int i = 0;
 while(primos[i] * primos[i] <= n) {
  if(n % primos[i] == 0) return false;
  i++;
 }
 return true;
}
int main() {
 init_crivo();
 int n, a, b;
 while(scanf("%d", &n)) {
  if(n == 0) break;
  bool find = false;
  a = 2, b = n - 2;
  while(a < n && b > 0 && !find) {
if(es_primo(a) && es_primo(b)) 
printf("%d = %d + %d\n", n, a, b), find = true;
a++, b--;
}
if(!find) printf("Goldbach's conjecture is wrong.\n");
}
return 0;
}

10699 - Count the factors - UVA

#include<cstdio>
#define MAX 1010
using namespace std;
int crivo[MAX + 1];
int primos[MAX + 1];
int n_primos = 0;
void init_crivo() {
 for (int i = 2; i <= MAX; i++)
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (int j = i; i * j <= MAX; j++) 
    crivo[i * j] = 1;
  }
}
int main() {
 int n, m, cont;
 init_crivo();
 while(scanf("%d", &n)) {
  if (n == 0) break;
  cont = 0;
  m = n;
  bool divide;
  for (int i = 0; primos[i] * primos[i] <= n; i++) {
   divide = false;
   while(n % primos[i] == 0) n /= primos[i], divide = true;
   if(divide)cont++;
  }
  if(n != 1) cont++;
  printf("%d : %d\n", m, cont);
 }
 return 0;
}

Numeros Amigos

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#define db(a) cout << #a << " = " << a << endl;
using namespace std;
int amigo(int n) {
 int m = 0;
 for (int i = 1; i * i <= n; i++) {
  if(n % i == 0)
   m += i + n / i;
  if(i * i == n) m -= i;
 }
 m -= n;
 int t = 0;
 for (int i = 1; i * i <= m; i++) {
  if(m % i == 0)
   t += i + m / i;
  if(i * i == m) t -= i;
 }
 t -= m;
 if(t == n) return m;
 return -1;
}
int main() {
 int n;
 ios_base::sync_with_stdio(false);
 while(cin >> n && n != 0) {
  cout << amigo(n) << endl;
 }
 return 0;
}

algorithm to determine if a number has a friend number, if not then it shows you -1 instead.

Programadores

11462 - Age Sort - UVA

#include<cstdio>
#include<map>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int main() {
	int n, leido, cant;
	map mapa;
	while(scanf("%d", &n)) {
		if(n == 0) break;
		mapa.clear();
		for (int i = 0; i < n; i++) {
			scanf("%d", &leido);
			mapa[leido]++;
		}
		bool first = true;
		foreach(it, mapa) {
			cant = it->second;
			for (int i = 0; i < cant; i++)
				if(first) printf("%d", it->first), first = false;
				else printf(" %d", it->first);
		}
		printf("\n");
	}
	return 0;
}

11239 - Open Source - UVA

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " = " << #b << " = " << b << endl;
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
struct proyecto {
 string nombre;
 int cantidad;
 proyecto(string nombre1 = "", int cantidad1 = 0) : nombre(nombre1), cantidad(cantidad1) {}
};
bool cmp(proyecto a, proyecto b) {
 if(a.cantidad > b.cantidad) return true;
 if(a.cantidad < b.cantidad) return false;
 if(a.nombre < b.nombre) return true;
 return false;
}
int main() {
 string line;
 map<string, set<string> > mapa;
 set<string> s;
 vector<proyecto> res;
 string capital;
 while(getline(cin, line)) {
  if(line == "0") break;
  if(line[0] == '1') {
   foreach(it_set, s) {
   int cont = 0;
   foreach(it, mapa)
    if(it->second.count(*it_set)) cont++;
   
   if(cont > 1) 
    foreach(it, mapa) 
     if(it->second.count(*it_set)) it->second.erase(it->second.find(*it_set));
   }
   foreach(it, mapa) {
    res.push_back(proyecto(it->first, it->second.size()));
   }
   sort(res.begin(), res.end(), cmp);
   foreach(it, res) {
    printf("%s %d\n", it->nombre.c_str(), it->cantidad);
   }
   res.clear();
   mapa.clear();
   s.clear();
   continue;
  }
  if(line[0] < 'A' || line[0] > 'Z') {
   mapa[capital].insert(line);
   s.insert(line);
  }
  else mapa[line], capital = line;
 }
 return 0;
}

use STL map and set for a best perfomance of the problem.

11800 - Determine the Shape - Solution UVA

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#include<utility>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " -- "<< #b << " = " << b << endl;
#define foreach(it, l) for(typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
typedef pair<long long, long long> punto;
#define x(p) p.first
#define y(p) p.second

long long producto_cruz(punto a, punto b){
 return x(a) * y(b) - y(a) * x(b);
}
long long producto_punto(punto a, punto b){
 return x(a) * x(b) + y(a) * y(b);
}
long long norma(punto a){
 return (x(a) * x(a) + y(a) * y(a));
}
int main(){
 int t = 0;
 int r1, r2, r3, r4;
 long long tama, tamb, tamc, tamd;
 bool exito;
 punto a, b, c, d;
 punto v1, v2, v3, v4;
 cin >> t;
 for(int i = 0; i < t; i++){
  scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &x(a), &y(a), &x(b), &y(b), &x(c), &y(c), &x(d), &y(d));
  int buscar[] = {1, 2, 3};
  vector<punto> puntos;
  puntos.push_back(a);
  puntos.push_back(b);
  puntos.push_back(c);
  puntos.push_back(d);
  do{
   x(v1) = x(puntos[buscar[0]]) - x(a);
   y(v1) = y(puntos[buscar[0]]) - y(a);
   
   x(v2) = x(puntos[buscar[1]]) - x(puntos[buscar[0]]);
   y(v2) = y(puntos[buscar[1]]) - y(puntos[buscar[0]]);
   
   x(v3) = x(puntos[buscar[2]]) - x(puntos[buscar[1]]);
   y(v3) = y(puntos[buscar[2]]) - y(puntos[buscar[1]]);
   
   x(v4) = x(a) - x(puntos[buscar[2]]);
   y(v4) = y(a) - y(puntos[buscar[2]]);
   
   r1 = producto_cruz(v1, v2);
   r2 = producto_cruz(v2, v3);
   r3 = producto_cruz(v3, v4);
   r4 = producto_cruz(v4, v1);
   
   if((r1 > 0 && r2 > 0 && r3 > 0 && r4 > 0)||(r1 < 0 && r2 < 0 && r3 < 0 && r4 < 0))
    exito = true;
   else exito = false;
  }while(!exito && next_permutation(buscar, buscar + 3));
  
  tama = norma(v1);
  tamb = norma(v2);
  tamc = norma(v3);
  tamd = norma(v4);
  
  if(producto_punto(v1, v2) == 0 && producto_punto(v2, v3) == 0
   && producto_punto(v3, v4) == 0 && producto_punto(v4, v1) == 0){
   if(tama == tamb && tamb == tamc && tamc == tamd)
    printf("Case %d: Square\n", i + 1);
   else
    printf("Case %d: Rectangle\n", i + 1);
  }
  else{
   if(tama == tamb && tamb == tamc && tamc == tamd)
    printf("Case %d: Rhombus\n", i + 1);
   else{
     if(tama == tamc && tamb == tamd)
    printf("Case %d: Parallelogram\n", i + 1);
     else{
     if(producto_cruz(v1, v3) == 0 || producto_cruz(v2, v4) == 0) 
      printf("Case %d: Trapezium\n", i + 1);
     else
      printf("Case %d: Ordinary Quadrilateral\n", i + 1);
       }
   }
  }
 }
 return 0;
}

this problem has a tricky situation, when you need to find the correct sequence of points so that we can find the side of the poligon instead of diagonals to cope with this, 4 vectors are built in each step of a next_permutation because we need to try with every posibility because the points can be given in non order and we do this with a fixed point then we try with the other 3 in next_permutation then inside each next_permutation we built the 4 vectors assuming that one comes after another forming a cycle then to know if we have a correct configuration (a cycle with the sides not diagonals) we have to notice that if we make cross product with 2 consecutives vectors it can be negative or positive, no matters which was, what matter is that all of this products should be either positive or negative , this means that the vectors that we have formed are in the sides of the poligon not forming diagonals. (you can try this with an arbitrary poligon and the you are to realize that if we make a vector with the sides not with the diagonals as a cycle all the consecutives cross products will be the same sign) , if we have made this with vectors which some of them was forming a diagonal the sign will be different than the rest, well once we have the sides of the poligon we just find the size of these vectors and apply some properties of vector to determine which shape they are forming, that's all hope this help you.

406 - Prime Cuts

#include<cstdio>
#define MAX 1000
using namespace std;
int crivo[MAX + 1];
int primos[MAX + 1];
int n_primos = 0;
void init_crivo() {
 primos[n_primos++] = 1;
 for (int i = 2; i <= MAX; i++)
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (int j = i; i * j <= MAX; j++)
    crivo[i * j] = 1;
  }
}
int main() {
 int n, c;
 init_crivo();
 while(scanf("%d%d", &n, &c) != EOF) {
  int cont = 0;
  while(primos[cont++] <= n && cont <= n_primos);
  cont--;
  int a, b;
  if(cont % 2 != 0) {
   a = cont / 2 - (2 * c - 1) / 2;
   if(a < 0) a = 0;
   b = cont / 2 + (2 * c - 1) / 2;
   if(b >= cont) b = cont - 1;
  }  
  else {
   a = cont / 2 - c;
   if(a < 0) a = 0; 
   b = cont / 2 + c - 1;
   if(b >= cont) b = cont - 1;
  }
  printf("%d %d:", n, c);
  for (int i = a; i <= b; i++)
   printf(" %d", primos[i]);
  printf("\n\n");
 }
 return 0;
}

In this problem we just simply find primes with crivo and then find the number of primes that we are going to use, or be it those number which are primes and less or equal to n, after that we just simply calculate if cont is even we have to show the amount 2*c from the center to both sides , c to left and c to right from the center, if cont is odd then we have another formula almost equal to the even and we expands it from the center to the left and to the right , that's it.

11428 - Cubes Solution

#include<iostream>
#include<cstdio>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
using namespace std;
int cubo(int a) {
 return a * a * a;
}
int main() {
   int n, x, y;
   while(scanf("%d", &n)) {
    if(n == 0) break;
    x = y = 0;
    while(1) {
     if(n == cubo(x) - cubo(y)){
      printf("%d %d\n", x, y);
      break;
     }
     if(n < cubo(x) - cubo(y)) y++;
     if(n > cubo(x) - cubo(y)) x++;
      if(cubo(x) - cubo(y) == 0 || x >= 60 || y>= 59) {
          printf("No solution\n");
          break;
      }
    }
   }
  return 0;
}

I just simply iterate looking for a pair x, y that satisfy n = x^3 - y^3 and I do it until
x >= 60 || y>= 59 because the diference between them is greater than 10,000 this means that
there is no solution.
for example if n = 1 then:
1 = 1^3 - 0^3 then printf "1 0"
2 = 0^3 - 0^3 doesn't match ... so I keep it up looking for the next candidate
2 = 1^3 - 0^3 equal to 1 so also, doesn't match again and as this is less than n = 2 x must be greater so increase it again ...
2 = 2^3 - 0^3 this is 8 , we have exceeded so we need to modify y now. so we increse it.
2 = 2^3 - 1^3 this is 7 , this goes being the same (or be it greater) so y++ again
2 = 2^3 - 2^3 this becomes less than 2 again so it means that there is no solution

The same logic applies for the rest of numbers.
I hope your comments.