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.