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
Algoritmos y Demas 