Algoritmos y Demas

Felicidades a todos los que participaron en el final de la Universidad Politecnica de Tlaxcala, aqui les dejo la solucion de los problemas

Problema A: Palabras
En este problema solo hay que ver si una cadena se puede formar con las letras de otra cadena

# include <stdio.h>
# include <string.h>

# define MAX 1000000

char wordA[MAX + 1], wordB[MAX+1];
int hash[256];

main(){
  int x;
  while( scanf("%s %s", wordA, wordB) != EOF ){
  	memset( hash, 0, sizeof( hash ));
  	for( x = 0; x < strlen(wordA); x++)
  	  hash[ wordA[x] ]++;
  	for( x = 0; x < strlen(wordB); x++)
  	  hash[ wordB[x] ]--;
  	 for( x = 0; x < 256 ; x++) if( hash[ x ] < 0 ) break;
  	 printf("%s\n", ( x < 256) ? "NO" : "YES");
  }
  return 0;	
}

Problema B: El señor de los anillos
Señor de los anillos, un problema que es definitivamente un dijkstra, lo complicado de este dijkstra es ver que nodos estan vistos por Sauron, como pueden ver las recurrencias son para los nodos que Sauron ve los nodos es de 1 a 7, de esa menera si sacamos el LCM de todos estos numeros tenemos esto (2*2*3*5*7) este es el modulo que necesitamos para saber si se repite sobre cualquier nodo, si nosotros ya calculamos el nodo X con el modulo Y, entonces ya no hay que evaluarlo de nuevo.

# include <stdio.h>
# include <string.h>

# define MOD (2*2*3*5*7)
# define MAX 102

int periodo[MAX+1];
int graph[MAX+1][MAX+1] , vis[MAX+1][MAX+1];

int distance[ MAX + 1 ][ MOD + 2];

main(){
  int n, m, dis, node, mod, x, y, a, b, nextnode;
  while( scanf("%d %d", &n, &m) != EOF && ( n || m )) {
     for( x = 1; x <= n; x++) scanf("%d", &periodo[ x ]);
     periodo[ 0 ] = MOD + 1;
     memset( graph, 0, sizeof( graph ));
     for( x = 0; x < m; x++){
       scanf("%d %d", &a, &b);
       graph[a][b] = graph[b][a] = 1;
     }
     for( x = 0; x <= n; x++) graph[x][x] = 1;
     for( node = 0; node <= n; node++)
     for( mod = 0; mod <= MOD; mod++){
       vis[ node ][ mod ] = 0;
       distance[ node ][ mod ] = (1<<30);	
     }
     node = 0;
     mod = 0;
     distance[ node ][ mod ] = 0;
     while( node != -1){
       dis = distance[ node ][ mod ];
       vis[node][ mod ] = 1;
       if( node == n ) break;
       for( nextnode = 0; nextnode <= n; nextnode++ ) if( graph[node][nextnode] == 1){
       	 if( distance[nextnode][ (mod + 1 ) % MOD ] > dis + 1 && (mod + 1) % periodo[ nextnode ] != 0 ){
       	   	distance[ nextnode ][ ( mod + 1 ) % MOD ] = dis + 1;
       	 }
       }
       node = -1;
       dis = (1<<30);
       for( x = 0; x <= n; x++)
         for( y = 0; y <= MOD; y++) if(vis[x][y] == 0 && distance[x][y] < dis){
            dis = distance[x][y];
            node = x;
            mod = y;
         }
     }
     printf("%d\n", ( node == -1 ) ? -1 : dis );
  }
  return 0;	
}

Problema C: Dados
Es un problema de conteo, ver de cuantas maneras distintas puedo colocar los dados para que me salga la suma solicitada, se puede hacer con un programacion dinamica o bien con un backtraking, que serviria de la misma manera, o bien cuatro fors con bastantes ifs.

# include <stdio.h>
# include <string.h>

# define MAX 5
# define MAX_CARAS 40
# define MAX_SUMA 100

int dados[MAX+1][MAX_CARAS+1];
int ndados[MAX+1];
int din[MAX+1][MAX_SUMA+1], S, n;

int solve(int position, int suma){
  int res = 0, x;
  if( suma > S ) return 0;
  if( position == n ) return S == suma ? 1 : 0;
  if( din[position][suma] != -1) return din[position][suma];
  for( x = 0; x < ndados[ position ]; x++)
    res += solve( position + 1, suma + dados[ position ][ x ]);
  return din[position][suma] = res;
}

main(){
  int  x, y, prod,  a , b;
  while( scanf("%d %d", &n, &S) != EOF && ( n || S)){
     prod = 1; 
     for( x = 0; x < n; x++){
       scanf("%d", &ndados[ x ]);	
       for(y = 0; y < ndados[ x ]; y++){
       	 scanf("%d", &dados[x][y]);
       }
       prod *= ndados[x];
     }	
     memset( din, -1, sizeof( din ));
     a = solve(0, 0);
     b = prod;
     if( a == b ) printf("1\n");
     else if( a == 0 ) printf("0\n");
     else printf("%d/%d\n", a , b);
  }
  return 0;
}

Problema D: Palíndromo
Se puede hacer con una programacion dinamica para que sea rapido o bien cuatro fors ya que el tamaño de la cadena es pequeña y saldria a tiempo.

# include <stdio.h>
# include <string.h>

# define MAX 100

int din[MAX+1][MAX+1];
char word[MAX+1];

int ispalindrome(int a, int b){
  if( a >= b) return 1;
  if(word[a] != word[b]) return 0;
  if( din[a][b] != -1) return din[a][b];
  return din[a][b] = ispalindrome( a + 1, b - 1);
}

main(){
  int a, b, n, cont;
  while( scanf("%s", word) != EOF ){
     memset( din, -1, sizeof( din ));
     n = strlen(word);
     cont = 0;
     for( a = 0; a < n; a++)
     for( b = a; b < n; b++)
       cont += ispalindrome(a, b );
     printf("%d\n", cont);
  }
  return 0;	
}

Problema E: Buscando Cuadrados
El problema de encontrar una submatrix sobre otras, en especifico sobre este problema como las matrices son pequeñas, entonces podemos hacer fuerza bruta, y con cuatro fors comparar si la matriz A esta en todas las posiciones iniciales que podamos colocarle en la matriz B, si queremos optimizarlo tendriamos que meternos un poco con el KMP, para poder hacer un conteo rapido.

# include <string.h>
# include <stdio.h>

# define MAX 100

char map[MAX+1][MAX+1], submap[MAX+1][MAX+1];

main(){
  int n, size, row, col, r, c, cont, query, q;
  while( scanf("%d", &n) != EOF && n ){
     for( row = 0; row < n; row++) scanf("%s", map[row]);
     scanf("%d", &query);
     for( q = 0; q < query ; q++){
        scanf("%d", &size);	
        cont = 0;
        for( row = 0; row < size ; row++) scanf("%s", submap[row]);
        for( row = 0 ; row < n; row++)
        for( col = 0 ; col < n; col++){
           for( r = 0; r < size && r + row < n ; r++){
             for( c = 0; c < size && c + col < n ; c++) 
               if( map[row+r][col+c] != submap[r][c]) break;
             if( c < size ) break;	
           }
           if( r >= size ) cont++;
        }
        printf("%d\n", cont);
     }
  }
  return 0;	
}

Problema F: Molde!
El problema nos indica que debemos hacer un convex hull, posteriomente sacar el perimetro y el area del convex encontrado.

# include <stdio.h>
# include <string.h>
# include <math.h>

# define MAX 100000

typedef struct { int x, y; } Point;

Point Poligono[MAX+1];
Point convex[MAX+1];
int vis[MAX+1];

int n;

double valumen, perimetro;

double abso( double a ){ return a < 0.0 ? -a : a; }

long long cross_product(Point a, Point b, Point c){
   return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}

long long cross(Point A, Point B, Point C){
  Point AB;
  Point AC;
  AB.x = B.x-A.x;
  AB.y = B.y-A.y;
  AC.x = C.x-A.x;
  AC.y = C.y-A.y;
  return AB.x * AC.y - AB.y * AC.x;
}

double area2D_Polygon( int n, Point* V ) {
    double area = 0;
    int  i, j, k;   
    if (n < 3) return 0; 
    for (i=1, j=2, k=0; i<n; i++, j++, k++) {
        area += V[i].x * (V[j].y - V[k].y);
    }
    area += V[n].x * (V[1].y - V[n-1].y); 
    return abso(area / 2.0);
}

double distance( Point a, Point b ){
  return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) ) ;	
}


double solve( int n ){
   Point p, ptmp, pposible;
   int nconvex = 0, x, pos, posa, post;
   double area;
   memset( vis, 0, sizeof( vis ));
   if( n == 1) return 0;
   if( n == 2) return distance( Poligono[0], Poligono[1]) * 2.0;
   p = Poligono[0];
   pos = 0;
   for( x = 1; x < n; x++){
   	  if(p.x > Poligono[x].x || (p.x == Poligono[x].x && p.y > Poligono[x].y)){
   	     p = Poligono[x];
   	     pos = x;
   	  }
   }
   posa = pos;
   while( 1 ){
      vis[pos] = 1;	
      convex[nconvex++] = p;
      posa = pos;
      for(x = 0; x < n; x++){
      	if( vis[x] == 0){
      	   pos = x;
      	   break;	
      	}
      }
      for( x = x + 1; x < n; x++){
          if( cross( Poligono[posa],Poligono[x], Poligono[pos]) < 0 ){
         	pos = x;
         }else if(cross( Poligono[posa],Poligono[x], Poligono[pos])  == 0 && distance( Poligono[posa] , Poligono[ pos ])
         	       < distance( Poligono[posa] , Poligono[ x ])){
         	   pos = x;	
         }
      }
      p = Poligono[ pos ];
      if( vis[ pos ] == 1) break;
   }
   perimetro = 0.0;
   convex[ nconvex] = convex[ 0 ];
   for( x = 0; x < nconvex; x++) perimetro += distance( convex[ x ], convex[ (x + 1) % nconvex]);
   area =  area2D_Polygon( nconvex, convex);
   printf("%.2lf %.2lf %.2lf\n", perimetro, area, valumen / area);
}


main(){
  int x;
  while( scanf("%d %lf", &n, &valumen) != EOF && ( n != 0 || valumen != 0 )){
     for( x = 0; x < n; x++) scanf("%d %d", &Poligono[ x ].x, &Poligono[ x ].y);	
     solve( n );
  }
  return 0;	
}

Cualquier sugerencia, explicacion mas detallada, favor de enviarme un correo a rodrigo.burgos@gmail.com

Concurso Semifinal UTP

Felicidades a todos, por participar en este tipo de competicion, si quieren ver los problemas y resultados puede verlos en el blog oficial http://concursodeprogramacionupt.wordpress.com/ aqui les dejo los codigos de cada uno de los problemas espero les gusten.

Problema A:

El problema A se tenia que saber cual es el alumno con la coordenada Y mas cercana a 0, el unico truco seria ver que tambien puede ser negativo el valor.

# include <stdio.h>
# include <string.h>
# define MAX 100

typedef struct { char nombre[1000];  int X, Y; } CONTESTANT;

CONTESTANT contestant[ MAX + 1];

int abso( int a ){ return a < 0 ? -a : a; }

main(){
  int ncases , cases, ncontestant, closer, cntResponse, x;
  for( scanf("%d", &ncases), cases = 1 ; cases <= ncases ; cases++ ) {
  	scanf("%d", &ncontestant);
  	closer = (1<<30);
  	for( x = 0; x < ncontestant; x++){
  	   	scanf("%s %d %d", contestant[ x ].nombre, &contestant[ x ].X, &contestant[ x ].Y );
  	   	if( closer > abso( contestant[x].Y ) ){
  	   	  closer = abso( contestant[x].Y );
  	   	}
  	}
  	cntResponse = 0;
  	for( x = 0; x < ncontestant ; x++ ){
  	  if( closer == abso( contestant[x].Y)) {
  	    if( cntResponse != 0 ) printf(" ");
  	    printf("%s", contestant[x].nombre );
  	    cntResponse++;
  	  }	
  	}
  	printf("\n");
  }
  return 0;	
}

Problema B:

Un problema un poco dificil para aquellos que empiezan en esto de la programacion , pero necesario en cualquier concurso, son los problemas de programacion dinamica, este un poquito dificil ya que requeria programación dinamica mas mascara de bits

# include <stdio.h>
# include <string.h>

int n;
char map[6][1002];
int din[1<<6][1002];
int block[2][6];

int min( int a, int b ){ return a < b ? a : b; }

int contbits( int mask ){ return mask == 0 ? 0 : contbits( mask >> 1 ) + ( mask & 1); }

int solve(int r, int c, int dr, int dc, int position){
    int res = (1<<22), cst;
	if( r >= 5 || r < 0 || c >= 2 ) return (1<<22);
	if( r == dr && c == dc ) return map[r][position] - '0';
   	if( block[c][r] == 1 || block[c][r] == 2 || block[c][r] == 10) return (1<<22);
   	block[c][r] = 10;
   	cst = (map[r][position] == '@') ? 0 : map[r][position]-'0';
   	res = min( res, solve( r+1, c, dr , dc, position )+ cst);
   	res = min( res, solve( r-1, c, dr , dc, position )+ cst);
   	res = min( res, solve( r, c+1, dr , dc, position+1 )+ cst);
   	block[c][r] = 0;
   	return res;
}

int mark( int r, int c, int dr, int dc, int position, int rt, int aspectedResult){
	int cst;
	if( r >= 5 || r < 0 || c >= 2 || rt > aspectedResult) return 0;
	if( r == dr && c == dc ){
	   if( aspectedResult == rt + map[r][position] - '0'){
 	     block[c][r] = 1;
	     return 1;	
	   }
	   return 0;
	}
	if( block[c][r] == 1 || block[c][r] == 2 || block[c][r] == 10) return 0;
	block[c][r] = 10;
	cst = map[r][position] == '@' ? 0 : map[r][position]-'0';
	if( mark( r+1, c, dr , dc, position, cst + rt, aspectedResult ) ){
	  block[c][r] = 1;
	  return 1;	
	}
   	 if( mark( r-1, c, dr , dc, position, cst + rt, aspectedResult  )){
	  block[c][r] = 1;
	  return 1;	
	}
   	 if( mark( r, c+1, dr , dc, position+1, cst + rt, aspectedResult )){
	  block[c][r] = 1;
	  return 1;	
	}
	block[c][r] = 0;
	return 0;
}

int cost( int position, int mask, int newmask ){
  int x, last, y, a, b;
  int r = 0, rt;
   memset( block, 0, sizeof( block ));
   if( position != 0 ) for( x = 0; x < 5; x++) block[0][x] = 1;
   for( x = 0 ; x < 5; x++) if( ( mask & (1<<x) )   > 0 ) block[0][x] = 2;
   for( x = 0 ; x < 5; x++) if( ( newmask & (1<<x) )   > 0 ) block[1][x] = 2;
   last = 0;
   for( x = 0 ; x < 5; x++) 
     if( ( mask & (1<<x) )   > 0 ) {
        for( y = last ; y < 5; y++) if( ( newmask & (1<<y) )   > 0 ){
        	block[0][x] = 0;
        	block[1][y] = 0;
        	rt = solve(x, 0, y, 1, position);
        	if( rt < (1<<22)){
        	  mark( x, 0, y, 1, position, 0, rt);
        	  r += (rt - ( map[x][position] == '@' ? 0: map[x][position] -'0'));
        	} else r = rt;
        	last = y+1;
        	block[0][x] = 2;
        	block[1][y] = 2;
        	break;
        }
     }
   return r;
}

int alfalfasMoves( int mask, int position ){
  int newmask, cst, tmp;
  int res = (1<<22);
  if( position >= n -1 ) return 0;
  if(din[mask][position] !=-1) return din[mask][position];
  for(newmask = 0; newmask < (1<<5) ; newmask++) if( contbits( newmask) == 3){
  	cst =  cost( position, mask, newmask ) ;
  	if( cst < (1<<22)){
  		cst += alfalfasMoves( newmask, position + 1);
  		if( cst < res ){
  			tmp = newmask;
  	  		res = min( res, cst ) ;
  		}
  	}
  }  
  return din[mask][position] = res;
}

main(){
  int r, mask, x;
  while( scanf("%d", &n ) != EOF && n ) {
    for( x = 0; x < 5; x++) scanf("%s", map[ x ]);
    mask = 0;
    for( x = 0 ; x < 5; x++) 
      if( map[x][0] == '@' ){
        mask |= (1<<x);	
      }
    memset( din, -1, sizeof( din ));
    r =  alfalfasMoves(mask, 0);
    printf("%d Jijuan%s\n", r , (r == 1 ? "" : "s")); 
  }
  return 0;	
}

Problema C:

Es un problema de busqueda en profundidad, o amplitud, aun que es mas secillo programar la profunidad marcando en la matriz VIS los lugares a dondes puede ir Diego.

# include <stdio.h>
# include <string.h>

# define MAX 100

char map[MAX+1][MAX+1];
int vis[MAX+1][MAX+1];
int R, C;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

void mark( int r, int c ){
  int dir;
  if( r < 0 || r >= R || c < 0 || c >= C ) return;	
  if( vis[r][c] == 1 || map[r][c] == 'M') return;
  vis[r][c] = 1;
  for( dir = 0; dir < 4; dir++)
    mark( r + dx[ dir ], c + dy[ dir ]);
}

main(){
  int ncases, cases, row;
  int ri, ci, rd, cd;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    scanf("%d %d", &R, &C);
    for( row = 0; row < R; row++){
      scanf("%s", map[ row ]);	
    }	
    scanf("%d %d", &ri, &ci);
    scanf("%d %d", &rd, &cd);
    memset( vis, 0, sizeof( vis ) );
    mark( ri - 1 , ci - 1 );
    if( vis[ rd - 1][ cd - 1] == 1 ) printf("SI\n");
    else printf("NO\n");
  }
  return 0;	
}

Problema D:
Problema de contar caracteres, practicamente es un for que recorra la cadena de la posicion A a la posicion B contando el caracter.

# include <string.h>
# include <stdio.h>

# define MAX_TEXT 100000

char text[MAX_TEXT + 1];

main(){
  int ncases, cases;
  int a, b, q, nquery, cont;
  char car;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    scanf("%s", text);
    scanf("%d", &nquery);	
    for( q = 0; q < nquery; q++){
    	scanf(" %c %d %d", &car, &a, &b);
    	a--; b--;
    	for( cont = 0 ; a <= b ; a++ ) 
    	  if( text[ a ] == car ) cont++;
    	printf("%d\n", cont);
    }
  }
  return 0;	
}

Problema E:

El problema mas sencillo del concurso, solo hay que imprimir la tabla de multiplicar del numero dado, aqui tal vez lo que les falto en el concurso y por el motivo que fueran muchos Time Limit time limit exceeded, es por que tenian que espera esta el fin de archivo, en entrada estadar como en cualquier file, podemos leer el scanf hasta un EOF que es fin de archivo, vean el codigo para mayor comprension, tambine pueden usar la funcion foef( FIEL *pf), pero en vez de un archivo solo colocando feof( stdin ) , que indicaria entrada estandar.

# include <string.h>
# include <stdio.h>

main(){
  int dig, n;
  while( scanf("%d", &n) != EOF ){
  	for( dig = 1; dig <= 10; dig++)
  	  printf("%dx%d=%d\n", n, dig, dig * n );
  }
  return 0;	
}

Problema F:

El problema F es un problema de geometria computacional, basicamente con solo saber el algoritmo de punto en un poligono podemos resolver este problema.

# include <stdio.h>
# include <string.h>

# define MAX_POLIGON 100
# define MAX_ELEMENT 200

typedef struct { int x, y; } Point;

Point Poligon[MAX_POLIGON+1][MAX_ELEMENT+2];
int npoligon[MAX_POLIGON + 1];


int cn_PnPoly( Point P, Point* V, int n ){
    int i;
    int    cn = 0; 
    for ( i=0; i<n; i++) {    
       if (((V[i].y <= P.y) && (V[i+1].y > P.y))     /* an upward crossing */
        || ((V[i].y > P.y) && (V[i+1].y <=  P.y))) { /* a downward crossing */
            
            double vt = (double)(P.y  - V[i].y) / (double)(V[i+1].y - V[i].y);
            if (P.x <  V[i].x + vt * (V[i+1].x - V[i].x)) 
                 ++cn; 
        }
    }
    return (cn&1); 

}

int hashInsidePoligon[MAX_POLIGON+1];

main(){
  int n, cont, x, y, m;
  Point source;
  while( scanf("%d", &n) != EOF && n ){
    for( x = 0; x < n; x++){
      scanf("%d", &npoligon[ x ]);	
      for( y = 0; y < npoligon[ x ] ; y++) scanf("%d %d", &Poligon[x][y].x, &Poligon[x][y].y);
      Poligon[x][y]  = Poligon[x][y-1];
    }
    memset(hashInsidePoligon, 0, sizeof(hashInsidePoligon));
    scanf("%d", &m);
    for( x = 0; x < m ; x++){
       scanf("%d %d", &source.x, &source.y );	
       for( y = 0; y < n; y++) 
         if( cn_PnPoly( source, Poligon[y] , npoligon[ y ]) )  hashInsidePoligon[ y ] = 1;
    }
    cont = 0;
    for( x = 0; x < n; x++) if(hashInsidePoligon[x] == 1) cont++;
    printf("%d\n", cont);
  }
  return 0;	
}

Cualquier duda o si quieren que explique mas a grandes rasgos una solucion me puede escribir a rodrigo.burgos@gmail.com