Nacional Inter politécnicas Tlaxcala 2013

Les comparto las soluciones de los problemas, en cuanto este los problemas en la pagina oficial, les comparto la liga.

Problema A

/*
Problema: A , solucion alterna
Autor: Rodrigo Burgos Dominguez
*/
# include <stdio.h>
# include <string.h>

int map[10][10];

int min(int a, int b){ return a < b ? a: b; }
int max(int a, int b){ return a > b ? a: b; }
int abso( int a ){ return a < 0 ? -a : a; }

int distance( int a, int b, int x, int y ){
    return  max( abso( a - x ) , abso( b - y ) );
}

int getDistance( int a, int b){
  int x, y, r = (1<<22);
  for( x = 1; x <= 8; x++)
  for( y = 1; y <= 8; y++)
    if( map[x][y] == 1)
       	r = min(r, distance(a, b, x, y));
   return r;
}

main(){
  int ncases, cases, x, y, mx, my, ly, lx, dm, dl;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
     for( x = 1; x <= 8; x++)	
     for( y = 1; y <= 8; y++)
       scanf("%d", &map[x][y]);
     scanf("%d %d", &mx, &my);
     scanf("%d %d", &lx, &ly);
     dm = getDistance( mx, my);
     dl = getDistance( lx, ly);
     printf("%s %d\n", ( dm < dl ? "Mario" : ( dm > dl ? "Luigi" : "Ambos")) , min( dm, dl ) );
  }
  return 0;	
}

Problema B

/*
  Problema: Sokoban
  Concurso: CONPI
  Autor: Rodrigo Burgos Dominguez
*/

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

int queue[1000000*2][7], N, nqueue;
char vis[10][10][10][10][10][10], map[11][11];
int nbox, boxx[2], boxy[2];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

void insert(int srow, int scol, int brow, int bcol, int bdrow, int bdcol, int distance){
  if( vis[srow][scol][brow][bcol][bdrow][bdcol] == 1 ) return;
  vis[srow][scol][brow][bcol][bdrow][bdcol] = 1;
  queue[nqueue][ 0 ] = srow;
  queue[nqueue][ 1 ] = scol;
  queue[nqueue][ 2 ] = brow;
  queue[nqueue][ 3 ] = bcol;
  queue[nqueue][ 4 ] = bdrow;
  queue[nqueue][ 5 ] = bdcol;
  queue[nqueue][ 6 ] = distance;
  nqueue++;
}

int move( int dir, int sr, int sc, int br, int bc, int bdr, int bdc, int dis){
   if( map[sr][sc] != '#'){
   	  if( sr == br && sc == bc ){
   	     br += dx[dir];
   	     bc += dy[dir];
   	     if( map[br][bc] == '#' || ( br == bdr && bc == bdc ) ) return 0;
   	     insert( sr, sc, br, bc, bdr, bdc, dis);	
   	     return 1;
   	  }else
   	    if(sr == bdr && sc == bdc ){
	   	     bdr += dx[dir];
	   	     bdc += dy[dir];
	   	     if( map[bdr][bdc] == '#' || ( br == bdr && bc == bdc ) ) return 0;
	   	     insert( sr, sc, br, bc, bdr, bdc, dis);	
	   	     return 1;
	   	  }else{
	   	     insert( sr, sc, br, bc, bdr, bdc, dis);	
	   	     return 1;
	   	  }
   }
   return 0;
}

int solve(int sr, int sc){
  int dis, br, bc, bdr, bdc, next, dir;
  memset( vis, 0, sizeof(vis)); 
  nqueue = 0;
  insert( sr, sc, boxx[0], boxy[0], boxx[1], boxy[1], 0);
  for(next = 0; next < nqueue ; next++){
  	 sr = queue[next][0];
  	 sc = queue[next][1];
  	 br = queue[next][2];
  	 bc = queue[next][3];
  	 bdr = queue[next][4];
  	 bdc = queue[next][5];
  	 dis = queue[next][6];
  	 if( map[br][bc] == '*' && ( nbox < 2 || map[bdr][bdc] == '*')){
  	    return dis;
  	 }
  	 for( dir = 0; dir < 4; dir++)
  	   move( dir, sr + dx[dir], sc + dy[ dir ], br, bc,  bdr, bdc, dis + 1);	
  }
  return -1;
}

main(){
  int x, y, ncases, cases, sr, sc;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
     scanf("%d", &N);	
     for( x = 0; x < N; x++) scanf("%s", map[x]);
     nbox = 0;
     memset( boxx , 0, sizeof( boxx ));
     memset( boxy , 0, sizeof( boxy ));
     for( x = 0; x < N; x++)
     for( y = 0; y < N; y++){
       if( map[x][y] == '$' || map[x][y] == '@'){
           boxx[nbox] = x;
           boxy[nbox] = y;
           nbox++;
           map[x][y] = ( map[x][y] == '@' ) ? '*' : '.';
       }
       if( map[x][y] == 's'){
         sr = x;
         sc = y;	
       }
     }
     printf( "%d\n", solve(sr, sc) );
  }
  return 0;	
}

Problema C

/*
Problema C: Solucion alterna
Autor: Rodrigo Burgos Dominguez
*/

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

int ataque[10], position[10];
int defensa[10];

int gana( int a, int d, int A, int D){
   if( a - 5 >= A) return 1;
   if( A - 5 >= a) return 0;
   if( d - 15 >= D) return 1;
   if( D - 15 >= d) return 0;
   return (a + d) - (A + D) >= 50;
}

main(){
  int cases, ncases, x, y;
  for( scanf("%d", &ncases) , cases = 1; cases <= ncases ; cases++){
    for( x = 0; x < 8; x++ ) scanf("%d", &ataque[x]);
    for( x = 0; x < 8; x++ ) scanf("%d", &defensa[x]);
    for( x = 0; x < 8; x++) position[x] = x;
    for( x = 8; x > 1; x /= 2){
      for( y = 0; y < x ; y+=2){
         position[y/2] = ( gana( ataque[position[y]] , defensa[ position[ y ] ], ataque[position[y + 1]] , defensa[ position[ y + 1] ]) == 1 ) ? position[ y ] : position[ y + 1]; 
         }
      }
    printf("%d\n", position[ 0 ]+1);
  }
  return 0;
}

Problema D

/*
Problema D: Solucion Alterna
Autor: Rodrigo Burgos Dominguez
*/
# include <stdio.h>
# include <string.h>

int hash[256];
char line[10000];

main(){
  int ncases, cases, x;
  double costR, costC, costT, total;
  for( gets(line), sscanf(line, "%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
     gets(line); sscanf(line, "%lf %lf %lf", &costR, &costC, &costT);	
     memset( hash, 0, sizeof( hash ));
     gets(line); 
     for( x =0; x < strlen(line) ; x++) hash[ line[x] ]++;
     gets(line); 
     for( x =0; x < strlen(line) ; x++) hash[ line[x] ]++;
     total = (double)hash['R']*costR*.2;
     total+= (double)hash['C']*costC*.3;
     total+= (double)hash['T']*costT*.4;
     
     total -= ((double)hash['B']*1.0);
     total -= ((double)hash['P']*2.0);
     total -= ((double)hash['H']*1.5);
     printf("%s\n%.1lf\n", (total <= 0 ? "Pierde" : "Gana"), total);
  }
  return 0;	
}

Problema E

/*
Autor: Rodrigo Burgos Dominguez
*/
# include <stdio.h>
# include <string.h>

int prime[100], nprime;
int c[100];

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

long long count(int n, int p){
    long long r, cnt = 0;
    for( r = p; r <= (long long)n; r *= (long long)p)
      cnt += n / r;
    return cnt;
}

main(){
  int x, y, n, base, cases, ncases, cont;
  long long sol, t;
  nprime = 0;
  for( x = 2; x <= 36; x++)
    if(c[x] == 0 )
     for( prime[nprime++] = x,  y = 2*x ; y <= 36 ; y += x) c[ y ] = 1;
  for( scanf("%d", &ncases), cases = 1 ; cases <= ncases ; cases++ ){
     scanf("%d %d", &n, &base);
     sol = -1;
     for( x = 0; x < nprime && prime[x] <= base ; x++){
     	for(cont = 0; base % prime[ x ] == 0 ; cont++){
     		base /= prime[x];
     	}
     	if( cont > 0 ){
     	   t = count(n, prime[x]) / (long long)cont;
     	   if( sol == -1) sol = t;
     	   sol = min( sol, t);
     	}
     }	
     printf("%lld\n", sol);
  }
  return 0;	
}

Problema F

/*
Problema F: Solucion Alterna
Autor: Rodrigo Burgos Dominguez
*/
# include <stdio.h>
# include <string.h>

int sol[11][11], mat[11][11];

main(){
  int ncases, cases, n, x, y, k, same;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
  	scanf("%d", &n);
  	for( x = 0; x < n; x++)
  	for( y = 0; y < n; y++)
  	  scanf("%d", &mat[x][y]);
  	same = 1;
    for( x = 0; x < n; x++)
    for( y = 0; y < n; y++){
       sol[x][y] = 0;
       for( k = 0; k < n; k++)
         sol[x][y] += mat[x][k]*mat[k][y];
       if( sol[x][y] != mat[x][y]) same = 0;
    }
    for( x = 0; x < n; x++){
      for( y = 0; y < n; y++){
        if(y != 0) printf(" ");
      	 printf("%d", sol[x][y]);
      }
      printf("\n");
    }
    printf("%d\n", same);
  }
  return 0;	
}

Problema G

/*
Autor: Rodrigo Burgos Dominguez
*/
# include <stdio.h>
# include <string.h>

# define MAX_ROW 30

int n, m;
char tablero[MAX_ROW+1][MAX_ROW+1];
int mark[MAX_ROW+1][MAX_ROW+1][2];
char vis[MAX_ROW+1][MAX_ROW+1];

int dr[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dc[8] = {2, -2, 2, -2, 1, -1, 1, -1};

int match( int row, int col){
   int r, c, dir;
   if( vis[row][col] == 1) return 0;
   vis[row][col] = 1;
   for( dir = 0; dir < 8; dir++){
      r = row + dr[dir];	
      c = col + dc[dir];
      if( r < 0 || r >= n || c < 0 || c >= m ) continue;
      if( tablero[r][c] == '.' && (  mark[r][c][0] == -1 || match( mark[r][c][0], mark[r][c][1] ) ) ){
      	  mark[r][c][0] = row;
      	  mark[r][c][1] = col; 
      	  mark[row][col][0] = r;
      	  mark[row][col][1] = c; 
      	  return 1;
      }
   }
   return 0;
}

main(){
  int ncases, cases, sol, x, y, contDots;
  for(scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++){
  	scanf("%d %d", &n, &m);
  	contDots = 0;
  	for(x = 0; x < n; x++){
  	  scanf("%s", tablero[ x ]);
  	  for( y = 0; y < m; y++)
  	    if(tablero[x][y] == '.') contDots++;
  	}
  	memset( mark , -1, sizeof( mark ));
  	sol = 0;
  	for( x = 0; x < n; x++)
  	for( y = 0; y < m; y++) 
  	  if(mark[x][y][0] == -1 && tablero[x][y] == '.'){
  	      memset( vis, 0, sizeof( vis ));
  	      if( match( x , y ) ) sol++;
  	  }
  	printf("%d\n", contDots - sol);
  }
  return 0;	
}