Translate

martes, 22 de mayo de 2012

Factors in Bin-packing instances

ACM Mexico Centro America y el Caribe 2004, Factors in Bin-packing instances


http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1100
Estaba recordando el regional cuando pasamos en primer lugar en una competencia donde al final del concurso teníamos 3 problemas y en el que estábamos peleándonos por tres mas pos-concurso, al final acabamos con 5 problema y pasamos al mundial.
Ese concurso fue inolvidable, como la BUAP gano con 5 problemas y también otro equipo de la BUAP intento con éxito hackear el PCS^2, al final los descubrieron pero fue épico, ya que en la lista del regional aparecía la BUAP en primer lugar con los alfalfas y en ultimo lugar con los BUAPandrosos.
Y es por ello que volví a ver los problemas del concurso y hay uno que no leí y que tampoco resolvimos por un solo caso de prueba, nos comentaron después los jueces, prácticamente el problema es dada un numero div = [n*f + .99999 ] que se calcula de multiplicar dos variables que te dan en el problema, hacer que una lista dada tenga exactamente el numero div de elementos que sean divisores de una variable C (dada en la entrada) .
Entonces para resolver el problema es ver cuantos números ya dividen a C, y ver si necesitamos mas divisores o menos, también nos pide el problema que sea el menor numero de unidades que se tengan que restar o sumar a los números.
Ya que sabemos si el numero de divisores es menor o mayor al valor esperado ( div ), entonces para cada numero en la lista calculamos el costo de transformarlo a un divisor o bien a un no divisor si queremos incrementar o decrementar los divisores.
Ordenamos por costo, y al final con un for vamos marcando el numero de divisores que nos sobran o nos hacen falta para que se impriman con el cambio, siempre de menor a mayor, si el costo es 0, entonces no podemos usar esos números por que ya son o divisores o no divisores.
Les dejo el código:

# include "stdio.h"
# include "string.h"

typedef struct { int value, nextValue, cost, position, changed; } TYPE;

TYPE types[1000000];

int solution[100000];

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

int compare( TYPE *a, TYPE *b){
  if( a->cost != b->cost) return a->cost - b->cost;
  return a->position - b->position;
}

main(){
  int n, c, contDivisors;
  int expectedValue, x, c1, c2, r;
  double value;
  while( scanf("%lf", &value ) != EOF ){
     scanf(" %d , %d", &n, &c);
     expectedValue = (int)(value * (double)n + (double)0.9999999999999);
     contDivisors = 0;
     for(x = 0; x < n; x++){
       scanf("%d", &types[ x ].value);
       contDivisors += (types[x].value != 0 && (c % types[x].value) == 0) ? 1 : 0;
     }
     for(x = 0; x < n; x++){
       types[x].position = x;
       if( contDivisors <= expectedValue ){
        /* UP */
        c1 = c2 = 0;
        for( r = types[x].value ; r <= c; r++ ){
         if( r != 0 &&  (c % r) == 0 ) break;
         c1++;
        }
        /* DOWN */
        for( r = types[x].value ; ; r-- ){
         if( r != 0 && (c % r) == 0 ) break;
         c2--;
        }
        types[x].cost = min( c1, -c2);
        if( -c2 < c1 ) types[x].nextValue = types[x].value + c2;
        else types[x].nextValue = types[x].value + c1;
        types[x].changed = 0;
       }else{
        /* UP */
        c1 = c2 = 0;
        for( r = types[x].value ; r <= c; r++ ){
         if( r == 0 && (c % r) != 0 ) break;
         c1++;
        }
        if( r > c ) c1 = (1<<28);
        /* DOWN */
        for( r = types[x].value ; ; r-- ){
         if(r == 0 && (c % r) != 0 ) break;
         c2--;
        }
        types[x].cost = min( c1, -c2);
        if( -c2 < c1 ) types[x].nextValue = types[x].value + c2;
        else types[x].nextValue = types[x].value + c1;
        types[x].changed = 0;
       }
     }
     qsort( types, n, sizeof( TYPE ), compare );
     for( x = 0; x < n && contDivisors != expectedValue ; x++){
      if( types[x].cost == 0 ) continue;
      contDivisors += ( contDivisors > expectedValue ) ? -1 : 1;
      types[x].changed = 1;
     }
     for( x = 0; x < n; x++){
       solution[types[x].position ] = ( types[x].changed ) ? types[x].nextValue : types[x].value;  
     }
     printf("%d, %d\n", n, c);
     for( x = 0; x < n; x++){
      printf("%d\n", solution[ x ]);
     }
  }
  return 0; 
}
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com

7 comentarios:

Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.
Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.
Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.
Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.
Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.
Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.
Anónimo dijo...
Este comentario ha sido eliminado por un administrador del blog.