Página donde publicaré cosas sobre los concursos de programación.
Eh estado escribiendo en otro blog, aquí les comparto los posts que hice, ( este blog también es mío pero lo tenia descuidado).
Programación Dinámica
http://algorithmmx.blogspot.mx/2013/11/problema-e-eleven-regional.html
Matching Bipartito
http://algorithmmx.blogspot.mx/2013/11/problema-attacking-rooks-regional.html
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;
}
Este problema nos dice que teniendo puntos en un tablero, nosotros podemos trazar líneas horizontales y verticales que conecten el punto con el extremo del tablero, con la restricción de que no toque otro punto o otra línea que conecte otro punto con la orilla del tablero ( Esto es un circuito electrónico que conecta un punto del circuito con la orilla ya que en la orilla esta la corriente). La tarea es encontrar el costo mínimo de hacer esto, ya que cada cm de línea que utilicemos tiene un costo.
Lo primero que se me ocurrió fue hacer un flujo máximo a costo mínimo, cada punto del tablero serian dos nodos un nodo incidente y otro adyacente, donde cada nodo incidente y adyacente que represente un nodo tendría una arista de costo 1 o de capacidad 1 , esto para evitar que pasara por el mas de un cable , si existiera un punto en esta coordenada simplemente esta arista no existiría, y de hecho resolvía el problema general, de conectar con el mínimo cable todos los puntos, pero el problema tiene una restricción, que solo pueden ser líneas rectas, esta solución encuentra un cableado donde se puede modificar la dirección del cable.
Después de pensar un rato mas encontré algo interesante, que es el tamaño del chip ( o del tablero) es menor a 30, y solo hay 50 puntos , si nosotros ordenamos de menor a mayor , por coordenadas Y y posteriormente por X, tenemos que cuando coloquemos un punto P[pos] después de P[pos – 1 ], este punto o esta arriba ( P[pos-1].y < P[pos – 1].Y ) o esta a la derecha ( P[pos-1].x < P[pos].x) , con esto podemos saber dos cosas, primero si puedo conectar el punto P[pos] a la derecha , ya que si P[pos-1].y == P[pos].y no es posible, y llevando el control del rango [A,B], donde A es el punto donde inicia el tablero visible de arriba y B es la posición del tablero donde termina el espacio visible, a que me refiero con campo visible, por ejemplo el campo visible al inicio es de 0 a 31, si un punto esta en la coordenada X = 5 y se conecta con otro a la izquierda tapa todos los nodos del 0 al 5 entonces el campo visible de tablero superior es de 6 al 31, si existiera otro que fuera a la derecha a partir de X = 9 , se tendría un campo visible de 6 al 8, entonces si nosotros llevamos esto en nuestra dinámica o mejor dicho en nuestra memorización , podríamos saber si puedo conectarme arriba y a la izquierda y como siempre se puede conectar a la derecha , casi se tiene resuelto el problema, para resolver el problema de si puede ir hacia abajo , simplemente llevamos otro rango [a,b], este rango es el rango permitido de colocar un punto, si nosotros colocamos un punto que va hacia abajo partiría en dos el tablero, y si un punto se quiere conectar al a izquierda solo podría hacerlo si el b = 31 , o si quiere ir a la derecha tendría que a ser igual a cero ( a=0) , si garantizamos que al partir el tablero ( conectarlo hacia abajo no hay un punto en ese trayecto) entonces solo restaría agregar los puntos siguiente dependiendo si están de lado de una partición o si están del otro lado.
Aquí les dejo el código:
/*Autor: Rodrigo Burgos Dominguez*/
# include <stdio.h>
#include <string.h>
typedef struct { int x, y; } POINT;
POINT p[100];
int AA, n;
int compare( POINT *a, POINT *b){
if( a->y != b->y)
return a->y - b->y;
return a->x - b->x;
}
int min( int a, int b){ return a < b ? a: b;}
int max( int a, int b){ return a > b ? a: b;}
int din[51][32][32][32][32];
int mapMax[100];
int mapMin[100];
int ladosMax[100];
int ladosMin[100];
int solve( int position, int A, int B, int a, int b){
int res = (1<<22), path = -1, tres, cst = 0;
if( position >= n ) return 0;
if( din[position][A][B][a][b] != -1) return din[position][A][B][a][b];
if( p[position].x <= a || p[position].x >= b )
return din[position][A][B][a][b] = solve( position + 1, A, B, a, b);
/* ARRIBA */
if( p[position].y <= mapMin[ p[ position ].x ] && p[ position ].x < B && p[ position ].x > A){
tres = solve( position + 1 , A, B, a, b ) + p[ position ].y ;
if( tres < res ){
res = tres;
path = 0;
cst = p[ position ].y;
}
}
/* IZQUIERDA */
if( p[position].x <= ladosMin[ p[ position ].y ] && a == 0 ){
tres = solve( position + 1 , max( A, p[ position].x), B, a, b ) + p[ position ].x ;
if( tres < res){
res = tres;
path = 1;
cst = p[ position ].x;
}
}
/* DERECHO */
if( p[position].x >= ladosMax[ p[ position ].y ] && b == 31 ){
tres = solve( position + 1 , A, min( B, p[position].x ), a, b ) + ( AA - p[ position ].x);
if(tres < res){
res = tres;
path = 2;
cst = ( AA - p[ position ].x);
}
}
/* ABAJO */
if( p[position].y >= mapMax[ p[ position ].x ]){
tres = solve( position + 1 , A, B, a, p[ position].x ) + solve( position + 1, A, B, p[ position ].x , b)+ ( AA - p[ position ].y );
if( tres < res){
res = tres;
path = 3;
cst = ( AA - p[ position ].y );
}
}
/* printf("(%d %d) %d %d %d %d %d -> %d -> path %d cost %d\n", p[position].x, p[ position].y, position, A, B, a, b, res, path, cst);*/
return din[position][A][B][a][b] = res;
}
main(){
int x, res;
while( scanf("%d %d", &AA, &n) != EOF ){
memset( din, -1, sizeof( din ));
for( x = 0; x <= AA; x++){
mapMax[ x ] = -(1<<22);
mapMin[ x ] = (1<<22);
ladosMax[x] = -(1<<22);
ladosMin[x] = (1<<22);
}
for( x = 0; x < n; x++){
scanf("%d %d", &p[x].x, &p[x].y);
mapMax[ p[x].x ] = max(mapMax[ p[x].x ], p[x].y);
mapMin[ p[x].x ] = min(mapMin[ p[x].x ], p[x].y);
ladosMax[ p[x].y ] = max(ladosMax[ p[x].y ] , p[x].x);
ladosMin[ p[x].y ] = min(ladosMin[ p[x].y ] , p[x].x);
}
qsort( p, n, sizeof( POINT ), compare );
res = solve( 0, 0, 31, 0, 31);
if(res >= (1<<22))
printf("No solution\n");
else
printf("The total length of wire used is %d\n", res);
}
return 0;
}
El pasado 27 de junio del 2013 en la pagina de cuba http://coj.uci.cu/ se llevo a cabo un concurso progresivo, en este link pueden ver los problemas http://coj.uci.cu/contest/cproblems.xhtml?cid=1301 , fueron 30 problemas a resolverse en 10 días, aquí voy a colocar algunos que se me hicieron interesantes de explicar, hoy explicare el siguiente
2422 – Betty and the Modular Exponentiation
Este problema es relativamente sencillo si se tiene los conocimiento de divide y vencerás y además saber como exponenciar un numero a la n de una forma logarítmica, ya que eso pedían el problema, dado a y b imprimir 
/* Autor: Rodrigo Burgos Dominguez*/
# include <stdio.h>
# include <string.h>
# define MOD ((long long)1000000000)
long long pot( long long a, long long b){
long long r;
if( b == 0 ) return 1;
if( b == 1 ) return a % MOD;
r = pot( a , b / 2);
r = (r * r ) % MOD;
if(b % 2 == 1) r = (r * a) % MOD;
return r;
}
main(){
int ncases, cases, a, b;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++){
scanf("%d %d", &a, &b);
printf("%lld\n", pot(((long long)a)%MOD, (long long)b));
}
return 0;
}
Buenas noches, ya tiene tiempo que no escribo pero aqui les dejo las ligas donde pueden ver los proximos concursos donde pueden participar de manera online:
En codeforces: (proximos concursos) que es una pagina rusa donde uno puede competir por dos horas y por lo regular son 5 problemas a resolver. Hay un concurso el proximo sábado entonces esten atentos.
Tambien puede prepararse en Topcoder en este link (calendar) pueden ver los proximos concursos de este mes y hasta el mes de diciembre por lo mientras.
En la pagina de juez online de Cuba hay varios concursos por venir, pero por el momento son privados, habría que preguntar al administrados cuales son los requisitos para participar.
PD: Apenas paso la final mundial y aqui están los resultados ranklist donde dos equipos mexicanos participaron, y el nuevo campeon del mundo es de Rusia : St. Petersburg National Research University of IT, Mechanics and Optics.
Subo los programas vistos en clase
problema 10530
#include <stdio.h>
#include <string.h>
char hash[11];
main(){
int n,i,honesto=1;
char line[20];
while(gets(line), sscanf(line, "%d",&n)!=EOF&&n!=0){
gets(line);
if(strcmp(line,"too high")==0){
if(hash[n]==2)honesto=0;
for(i=n;i<=10;i++)hash[i]=1;
}
else if(strcmp(line,"too low")==0){
if(hash[n]==1)honesto=0;
for(i=n;i>=1;i--)hash[i]=2;
}
else{
printf("%s\n",( honesto==1 && hash[n] == 0 )?"Stan may be honest":"Stan is dishonest");
memset(hash,0,sizeof(hash));
honesto=1;
}
}
retu
problema: 11005
# include <stdio.h>
# include <string.h>
int cost[37];
int costPerBase[37];
main(){
int ncases, cases, nquery, minValue, x, base;
long long num, numtmp;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
for( x = 0; x < 36; x++) scanf("%d", &cost[ x ]);
if( cases != 1) printf("\n");
printf("Case %d:\n", cases);
scanf("%d", &nquery);
for( x = 0; x < nquery ; x++){
scanf("%lld", &num);
memset(costPerBase, 0, sizeof(costPerBase));
minValue = 10000000;
for( base = 2; base <= 36; base++){
numtmp = num;
while( numtmp > 0 ){
costPerBase[ base ] += cost[ numtmp % base ];
numtmp /= base;
}
if(costPerBase[base] < minValue) minValue = costPerBase[base];
}
printf("Cheapest base(s) for number %lld:", num);
for( base = 2; base <= 36; base++ )
if( costPerBase[base] == minValue) printf(" %d", base);
printf("\n");
}
}
return 0;
}
Clase 16 de Marzo 2013
Se les comunica que los proximos dos fines de semana no habra clase, entonces nuestra proxima clase seria el sabado 7 de abril, de todos modos yo voy a estar contestando correos, aquellos que tengas dudas de los problemas de tareas no duden en escribirme a rodrigo.burgos@gmail.com
Les coloco los codigos que hicimos en clase:
Permutaciones
Como sacar todas las permutaciones de una cadena donde todos los elementos son diferernte:
# include <stdio.h>
# include <string.h>
char cad[100], path[100];
char mark[100];
void backtrack( int level ){
int x;
if( level == strlen( cad )){
cad[ level ] = '\0';
printf("%s\n", path);
}
for( x = 0; x < strlen( cad ); x++)
if( mark[x] == 0 ){
mark[x] = 1;
path[ level ] = cad[x];
path[ level + 1] = '\0';
backtrack( level + 1);
mark[x] = 0;
}
}
main(){
while( scanf("%s", cad) != EOF ){
memset( mark, 0, sizeof( mark ));
backtrack( 0 );
}
return 0;
}
Búsqueda Binaria.
la función busbiniter es la forma iterativa de la búsqueda binaria, también tenemos la función busbinrec que es la función recursiva.
# include <stdio.h>
# include <string.h>
int n;
int list[100000];
int busbiniter( int inf, int sup, int val ){
int med;
while( inf <= sup ){
med = (inf + sup ) / 2;
if( list[ med ] == val ) return med;
if( list[med] < val ) inf = med + 1;
else sup = med - 1;
}
return -1;
}
int busbinrec( int inf, int sup, int val ){
int med = ( inf + sup ) / 2;
if( inf > sup ) return -1;
if( list[ med ] == val ) return med;
if( list[med] < val ) return busbinrec( med + 1, sup, val);
return busbinrec( inf, med - 1, val);
}
main(){
int x, val;
n = 0;
for( x = 0 ; x <= 100000; x+= 3) list[n++] = x;
while( scanf("%d", &val) != EOF ){
printf("%d\n", busbiniter( 0, n - 1, val ) ) ;
}
return 0;
}
Tour del caballo
Este código resuelve el problema que vimos en clase, dado el un tablero de ajedrez de N x N, y la posición inicial del caballo encontrar un camino donde el caballo visite todos los cuadros del tablero.
# include <stdio.h>
# include <string.h>
int board[100][100];
int dr[8] = {2,2,-2,-2,-1,-1,1,1};
int dc[8] = {1,-1,1,-1,2,-2,2,-2};
int n;
int backtrack(int level, int r, int c){
int dir, x, y, res = 0;
if( level == n * n + 1 ){
for( x = 0; x < n; x++){
for( y = 0; y < n; y++) printf("%3d", board[x][y]);
printf("\n");
}
printf("---\n");
return 1;
}
if( r < 0 || r >= n || c < 0 || c >= n ) return 0;
if( board[r][c] != 0 ) return 0;
board[r][c] = level;
for( dir = 0; dir < 8; dir++)
res += backtrack(level + 1, r + dr[ dir ] , c + dc[ dir ] );
board[r][c] = 0;
return res;
}
main(){
int posr, posc;
int r;
while( scanf("%d %d %d", &n, &posr, &posc) != EOF ){
memset(board, 0, sizeof( board ));
r = backtrack(1, posr, posc);
printf("%d\n", r);
}
return 0;
}
Problema del Sudoku
El siguiente programa resuelve el problema del sudoku, como vismo en clase es muy util utilizar el bactraking y para evitar crecer mucho el codigo utilizamos la tecnica de hash, con la filas, columnas y los cuadrantes.
# include <stdio.h>
# include <string.h>
int hashRow[10][10];
int hashCol[10][10];
int hashCua[10][10];
int numcuad[10][10];
char sudoku[10][10];
int print(){
int x, y;
for( x = 0; x < 9; x++){
for( y = 0; y < 9; y++) printf("%c", sudoku[x][y]);
printf("\n");
}
printf("---\n");
}
int backtrack( int row, int col ){
int dig, x;
if( row == 10 ){
print();
return 1;
}
if( col == 10 ) return backtrack( row + 1, 1 );
if( sudoku[row-1][col-1] != '_') return backtrack( row , col + 1);
for( dig = 1 ; dig <= 9; dig++){
if( hashRow[ row ][ dig ] == 1 ) continue;
if( hashCol[ col ][ dig ] == 1 ) continue;
if( hashCua[ numcuad[row -1][col -1 ] ][ dig ] == 1 ) continue;
hashRow[ row ][ dig ] = 1;
hashCol[ col ][ dig ] = 1;
hashCua[ numcuad[row -1][col -1 ] ][ dig ]= 1;
sudoku[row-1][col-1] = '0' + dig;
if( backtrack( row, col + 1) ) return 1;
hashRow[ row ][ dig ] = 0;
hashCol[ col ][ dig ] = 0;
hashCua[ numcuad[row -1][col -1 ] ][ dig ]= 0;
sudoku[row-1][col-1] = '_';
}
return 0;
}
main(){
int x, y, ncases, cases, row, col;
for(x = 0; x < 9; x++)
for( y = 0; y< 9; y++){
numcuad[x ][ y ] = ( ((x / 3) ) * 3 + (y / 3) ) + 1;
}
for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++ ){
memset( hashRow, 0, sizeof( hashRow));
memset( hashCol, 0, sizeof( hashCol));
memset( hashCua, 0, sizeof( hashCua));
for(row = 0; row < 9;row++){
scanf("%s", sudoku[row]);
for( col = 0; col < 9; col++)
if( sudoku[row][col] != '_'){
hashRow[ row + 1 ][ sudoku[row][col] - '0'] = 1;
hashCol[ col + 1 ][ sudoku[row][col] - '0'] = 1;
hashCua[ numcuad[row][col] ][ sudoku[row][col] - '0'] = 1;
}
}
backtrack( 1, 1 );
}
return 0;
}
Problemas:
Backtracking
http://uva.onlinejudge.org/external/1/167.html (Problema de las 8 reinas, utilizen la tecnica de hash, sobre fila, columna y diagonales, pueden poner una matriz como hicimos en el problema del sudoku para saber que diagonal le corresponde, recuerden que son dos tipos de diagonales).
http://uva.onlinejudge.org/external/5/524.html ( Problema de bactracking y primos , ya estan listos para estos problemas ).
http://uva.onlinejudge.org/external/5/574.html (Pueden ordenar los elementos para hacer una poda eficiente al bactrackign).
http://uva.onlinejudge.org/external/6/624.html
http://uva.onlinejudge.org/external/6/628.html
http://uva.onlinejudge.org/external/105/10582.html
http://uva.onlinejudge.org/external/6/677.html ( revisen la primera clase y el probleam del The lord of the ring, para ver como crear una matriz de adyacencia, en la siguiente clase veremos grafos, pero con lo que saben pueden resolver este problema).
http://uva.onlinejudge.org/external/7/750.html (Otro problema de las 8 reinas).
http://uva.onlinejudge.org/external/103/10344.html
http://uva.onlinejudge.org/external/8/868.html (aun que se puede hacer un algoritmo mas rapido con memorizacion es buena practica para un backtraking.)
http://uva.onlinejudge.org/external/103/10309.html (recursividad con memorizacion, notar que todas son de 10 x 10 , por tanto solo hay 10 1’s o 0’s , ¿eso no les recuerda a los bits ?.)
Binary Search:
http://uva.onlinejudge.org/external/106/10611.html
http://uva.onlinejudge.org/external/107/10742.html
http://uva.onlinejudge.org/external/110/11057.html
http://uva.onlinejudge.org/external/118/11876.html
Suerte, y recuerden que pueden resolver problemas aun que no esten en la lista.
Saludos.
Buenos días a todos, les comparto el código que hicimos en clase:
/*
Autor : Rodrigo Burgos Dominguez.
Problema: Regional 2006 ACM Mexico,
*/
# include <stdio.h>
# include <string.h>
# define MAX 1000000
int prime[MAX +1], nprime, hash[ 256], hashprime[ MAX + 1];
char criba[MAX+1], cad[MAX+1];
void update( int n, int oper ){
int x, pt;
for( x = 0; x < nprime && x <= n; x++){
for( pt = prime[x] ; pt <= n ; pt *= prime[ x ])
hashprime[ x ] += ( n / pt ) * oper;
}
}
int abso( int a ){ return a < 0 ? -a: a; }
int potencia( int a, int b ){
int res = 1;
for( ; b > 0 ; b-- ) res *= a;
return res;
}
main(){
int x, y, ncases, cases, res, pot, val, n;
nprime = 0;
for( x = 2; x <= MAX ; x++)
if( criba[ x ] == 0 )
for( y = x * 2, prime[ nprime++ ] = x ; y <= MAX ; y+= x) criba[y] = 1;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
scanf("%s", cad);
n = strlen(cad);
memset( hash, 0, sizeof( hash ));
memset( hashprime, 0, sizeof( hashprime));
for( x = n - 1; x >= 0 ; x-- ) hash[ cad[ x ] ]++;
update( n , 1 );
for( x = 'a' ; x <= 'z'; x++){
update( hash[ x ] , -1);
}
res = 1;
for( x = 1; x < n; x++)
if( prime[x] != 5 )
res = (res * potencia( prime[x], hashprime[ x ])) % 10;
pot = abso( hashprime[ 0 ] - hashprime[ 2 ]);
val = ( hashprime[0] < hashprime[2]) ? 5 : 2;
res = (res * potencia( val, pot) ) % 10;
printf("%d\n", res);
}
return 0;
}
Lo que vimos en clase, que son los primos como sacarlos con la criba de Eratóstenes, factorizar un numero, conteo rápido de primos en un Factorial, saber obtener el numero de ceros y el ultimo numero distinto de cero.
Aquí les dejo los problemas para que practiquen, necesito que los envíen a la uva para ver si están entendiendo , si tienen dudas envíenme un correo a rodrigo.burgos@gmail.com con sus respectivas dudas.
Problemas:
Prime Cuts
http://uva.onlinejudge.org/external/4/406.html
Goldbach’s Conjecture
http://uva.onlinejudge.org/external/5/543.html
nota: 6 <= n <= 1,000,000 utilizen un hash para ver si un numero es primo (pueden usar el arreglo de la criba ) y solo iterar los 78,000 primos.
recuerden que la lectura de este seria asi:
while( scanf("%d", &n) != EOF && n != 0 ){
…
}
Problem G: Simply Emirp
http://uva.onlinejudge.org/external/102/10235.html
Problem E – Prime Words
http://uva.onlinejudge.org/external/109/10924.html
Problem F: The primary problem.
http://uva.onlinejudge.org/external/109/10948.html
Factors and Factorials
http://uva.onlinejudge.org/external/1/160.html
Nota: utilicen la técnica de conteo que les enseñe, de ver cuantos dos , tres, cincos hay en un N factorial para resolver este problema. Lean bien la salida como se debe hacer, si tiene dudas me escriben sus dudas.
Product of digits
http://uva.onlinejudge.org/external/9/993.html
How many zeros and how many digits?
http://uva.onlinejudge.org/external/100/10061.html
Nota: Deben leer sobre lo logaritmos.
Divisors
http://uva.onlinejudge.org/external/2/294.html
Factorial Factors
http://uva.onlinejudge.org/external/8/884.html
I – Find Terrorists
http://uva.onlinejudge.org/external/12/1246.html
Problem D – Count the factors
http://uva.onlinejudge.org/external/106/10699.html
Twin Primes
http://uva.onlinejudge.org/external/103/10394.html
Almost Prime Numbers
http://uva.onlinejudge.org/external/105/10539.html
Nota: el valor hiigh < 10^12 , esto es muy grande, pero deben darse cuenta, que un almost prime es un no primo que es divisible por un solo primo esto quiere decir que un almost primer es de la forma P^2, P^3 … P^n, como el valor mas peque es p^2, si buscamos un primo que sea mas grade de un 1000,000 = 10^6, su cuadrado seria mayor 10^12 que es nuestro tope, entonces basta con tener todos los primos menores a 10^6.
Factorial Frequencies
http://uva.onlinejudge.org/external/3/324.html
Problem A – Prime Distance
http://uva.onlinejudge.org/external/101/10140.html
Just the Facts
http://uva.onlinejudge.org/external/5/568.html
Prime Factors
http://uva.onlinejudge.org/external/5/583.html
Problem D: GCD LCM
http://uva.onlinejudge.org/external/113/11388.html
Largest Prime Divisor
http://uva.onlinejudge.org/external/114/11466.html
el numero es menor o igual 14 digitos, esto quiere decir que con un nomero 10^7 es suficiente para saber el cual es el primo mas grande.
Problem C: Composite Prime
http://uva.onlinejudge.org/external/110/11086.html
Coloco las paginas que les mencione el la clase pasada:
http://uva.onlinejudge.org/index.php
Deben crear su cuenta:, para poder enviar problemas
Otras paginas donde puede practicar es en topcoder
http://www.topcoder.com/tc
Y para ver reseñas de los problemas que se han puesto en sus concusos revisen esta liga:
http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
También tienen tutoriales.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index
Esta es la lista de problemas de esta semana:
http://uva.onlinejudge.org/external/121/12149.html
(formula , puedes usar una formula y un for).
La lectura seria algo como esto:
main( ){
while( scanf(“%d”, &n) ¡= EOF && n ¡= 0 ){
…..
}
return 0;
}
ya que dice que termina cuando la línea contenga un 0.
http://uva.onlinejudge.org/external/121/12157.html voy a poner como se resuelve este en java para que los que usen Java no tengan problemas de enviar sus código:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public final static int COST_PER_COMPANY[] = {10,15};
public final static int TIME_PER_COMPANY[] = {30,60};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
for(int ncases = scan.nextInt(), cases = 1 ; cases <= ncases ; cases++ ){
int cost[] = new int[2];
Arrays.fill(cost, 0); // esto es lo mismo que el memset en C o C++, solo que hay que hacer
// por cada dimencion de nuestro arreglo.
int numCalls = scan.nextInt();
for( int x = 0; x < numCalls ; x++ ){
int callDuration = scan.nextInt();
for( int company = 0 ; company < 2; company++ ){
cost[ company ] += ( (callDuration / TIME_PER_COMPANY[ company ] )+ 1) * COST_PER_COMPANY[company];
}
}
System.out.printf("Case %d: ", cases);
if( cost[ 0 ] == cost[ 1 ]){
System.out.printf("Mile Juice %d\n", cost[ 0 ] );
}else{
if( cost[ 0 ] < cost[ 1 ])
System.out.printf("Mile %d\n", cost[ 0 ] );
else
System.out.printf("Juice %d\n", cost[ 1 ] );
}
}
}
}
Como pueden ver, no agrego el pakage, y la clase se llama Main, esto es muy importante, en la uva lo que envien en codigo Java lo guardara en un Main.java y lo compilara, si no tiene la clases el nombre de Main les mandara un compile error:
Main.java:5: class P12157 is public, should be declared in a file named P12157.java
public class P12157 {
^
1 error
Entonces abusados con esto.
les dejo los demas problema:
http://uva.onlinejudge.org/external/123/12372.html
http://uva.onlinejudge.org/external/123/12342.html
http://uva.onlinejudge.org/external/100/10055.html
http://uva.onlinejudge.org/external/100/10071.html
http://uva.onlinejudge.org/external/100/10038.html
http://uva.onlinejudge.org/external/100/10035.html
http://uva.onlinejudge.org/external/101/10189.html
http://uva.onlinejudge.org/external/101/10110.html
http://uva.onlinejudge.org/external/101/10127.html
http://uva.onlinejudge.org/external/122/12289.html
http://uva.onlinejudge.org/external/122/12250.html
http://uva.onlinejudge.org/external/122/12279.html
http://uva.onlinejudge.org/external/122/12243.html
Hoy entre de nuevo a Topcoder, el SRM 565 con un poco de emoción y recelo debido a que no eh entrado a un concursos tipo Topcoder desde ya hace 11 meses, y como era de esperarse me fue muy mal, sacando 0 puntos.
En los próximos meses pretendo entrenar a alumnos para los Regionales de ACM y debo ponerme a practicar aun que sea en CodeForces y Topcoder, también debo hacer la misma tarea que ellos hacen, cada problema que no podamos resolverlo en el concurso tratarlo de sacar de tarea y aquí voy a explicar algunos de ellos como se resuelven.
Empecemos, este el problema:
Resumiendo el problema: tienes que crear un método llamado minimumPrice que reciba dos arreglos long[] dread y int[] Price , tu tienes que pasar por una serie de mostro en el orden establecido , cada mostro es sobornable y por lo tanto puedes pagar un precio ( que va de 1 a 2 ) , si lo pagas el mostro te apoyara con los siguientes mostros, si no lo pagas el te atacar si y solo si su temor ( que es igual a su valentía ) es mayor que la suma de todos los mostros que se hallan comprado.
Tu tarea es calcular el mínimo precio para pasar por todos los mostros sin ser atacado.
Con esta información se puede plantear una dinámica muy sencilla de posición x temor , el numero de mostros es menor a 50 , pero el temor esta entre 1 y 10^12, lo cual arruina completamente esta dinámica simple.
Pase varios minutos sin encontrar una manera de resolver el problema de manera optima con una programación dinámica, por lo tanto hice un glotón que sospechaba fuertemente no era suficiente para resolver todos los casos de prueba y así fue.
Revisando soluciones de otros programadores y viendo como lo resolvieron, la programación dinámica era correcta, solo que en vez de tomar la posición y la bravura, era la posición y el precio guardando la suma de todos los miedos ( me recordó a una película no se por que) o mejor dicho maximizando la suma de todos los mostros sobornados con un costo especifico, y de ahí basarnos para calcular si el siguiente mostro se puede sobornar o se puede pasar derecho con cierta cantidad de dinero, si no se puediera se marcaria con -1 o con algún valor para determinar con ese costo no se pudo superar ese mostro.
Veamos el código:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class MonstersValley {
public:
int minimumPrice(vector <long long>, vector <int>);
};
long long din[51][101];
int MonstersValley::minimumPrice(vector<long long> dread, vector <int> price) {
memset(din, -1, sizeof( din )); // marcamos como imposible todas las posiciones
din[0][price[0]] = dread[ 0 ]; // la unica manera de pasar al primero mostro es sobornandolo
for( int currentMonster = 1; currentMonster < dread.size() ; currentMonster++ ){
for( int cost = 0; cost <= dread.size() * 2 ; cost++)
if(din[currentMonster - 1][ cost] >= 0 ){
if( din[currentMonster -1][ cost] >= dread[ currentMonster ] )
din[currentMonster][cost ] = max(din[currentMonster][cost ] , din[currentMonster-1][cost ] );
din[currentMonster][cost +price[currentMonster]] =
max(din[currentMonster][cost + price[currentMonster]] ,
din[currentMonster-1][cost ] + dread[currentMonster]);
}
}
for(int cost = 0; cost <= dread.size() * 2 ; cost++ ){
if(din[dread.size() - 1 ][ cost ] >= 0 ) return cost;
}
return -1;
}
//Powered by [KawigiEdit] 2.0!
Algoritmos y Demas 