Hacker Cup 2012 Qualification Round

Hacker Cup 2012 Qualification Round

Billboards

Este problema practicamente es de simulacion, uno va incrementando el tamaño de las letras y al final valida que no se salgan del tamaño maximo de filas y columnas.

# include 
# include 

char words[1001][1001], line[1001];
int nwords;

main(){
  int ncases, cases, sol, row, col, W, H, x;
  char *buf;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++ ){
   scanf("%d %d", &W, &H);
   gets( line );
   nwords = 0;
   for( buf = strtok( line, " \n" ) ; buf != NULL ; buf = strtok( NULL, " \n") ){
     strcpy( words[ nwords++ ], buf  ); 
   }
   row = 0;
   for( sol = 1;  ; sol++){
      col = 0;
      row = sol;
      for( x = 0 ; x < nwords ; x++ ){
         if( sol * strlen( words[ x ] ) + col + ( col > 0 ? sol : 0 ) <= W ){
            col = sol * strlen( words[ x ] ) + col + ( col > 0 ? sol : 0 );
         }else {
          if( col == 0 ) break;
          col = 0;
           row += sol;
           x--; 
         } 
      }
      if( x < nwords ) break;
      if( row > H ) break;
   }
   printf("Case #%d: %d\n", cases, sol - 1 );
  } 
  return 0; 
}//

Auction

Un problema realmente dificil, la fuerza bruta no funciona, lo que mas me pude acercar fue a una solucion 10^14 que no correria en tiempo, como estan los modulos tanto para W como para P a lo mas de 10^7, siempre se puede encontrar un ciclo menor o igual a eso, y con eso podemos ver que el LCM ( largo de W, largo de P ) es el maximo ciclo que tenemos que recorrer, el unico problema con eso es que este LCM puede ser mas grande incluso que N. ( alguien tiene alguna idea para resolverlo??? ).

Not solved.

Alphabet Soup

Este problema se puede resolver con una tecnica de hash, en un arreglo una cuenta cuantas veces esta una letra ( en H guardo el numero de letras que hay en HACKERCUP ), teniendo las letras de HACKERCUP contadas, contamos las de cada uno de los casos de prueba ( en hash ) , y para obtener la solucion solo dividimos cada letra de hackercup encontrada en el caso de prueba con las que tenemos en nuestra palabra base, el minimo de ellas es la respuesta.

# include 
# include 

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

int H[256];
int hash[256];
char line[1002];
char hackercup[ 12 ] ="HACKERCUP";

main(){
  int x, cases, ncases, length, sol;
  memset( H, 0, sizeof( H ));
  for( x = 0; x < strlen( hackercup ) ; x++) H[ hackercup[ x ] ]++;
  for( gets( line ) , sscanf(line, "%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
   gets( line );
   memset( hash, 0, sizeof( hash ));
   length = strlen( line );
   for( x = 0; x < length ; x++ ){
     hash[ line[ x ] ]++; 
   }
   sol = (1<<22);
   for( x = 0; x < strlen( hackercup ) ; x++) sol = min( sol, hash[ hackercup[ x ] ] / H[ hackercup[ x ] ] ) ;
   printf("Case #%d: %d\n", cases, sol);
  }
  return 0;
}//

Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com