Translate

martes, 14 de agosto de 2012

UVA 10407 Simple division

UVA 10407 Simple division


http://uva.onlinejudge.org/external/104/10407.html
Buenos dias a todos, les comparto este problema, practicamente se trata de encontrar un numero que al dividir a toda una lista de numeros regresen todos el mismo residuo, en el algoritmo que expongo abajo se puede ver que la solucion la pongo como un "Fuerza Bruta pero no tanto" ya que mi idea no se basa tanto en las propiedades de la division del numero y como no soy un matematico puro no se me ocurre directamente como sacar una solucion con estas propiedades.
Esta solucion radica en el hecho si tomo dos numeros distintos la cantidad de numeros que al dividirlo me resulte el mismo residuo no son muchos, por tal motivo lo primero que hago es quitar todos los numero repetidos:
  // ESTO VA FUERA DEL MAIN
  int compare( int *a, int *b){ return *a - *b; }
  // FIN DE LO QUE VA FUERA DEL MAIN
  
  
    qsort( list, n, sizeof( int ), compare );
    nsize = 1;
    for( x = 1; x < n; x++){
       if( list[ x ] != list[ x - 1]){
           list[ nsize++ ] = list[x];
       }
    }


Primero ordeno, y luego si son distintos los guardo en la ultima posicion libre que tengo, primero n es el tamaño de mi lista y al final nsize sera mi nuevo tamaño de la lista.
Dejo reposar el algoritmo por unos segundos, y despues calculo todos los numeros que dividen a los numeros mas pequeños, ya que trato de procesar la menor cantidad de operaciones:
  // ESTO VA FUERA DEL MAIN
  int compare2( int *a, int *b){ return abs(*a) - abs(*b); }
  // FIN DE LO QUE VA FUERA DEL MAIN

    qsort( list, nsize, sizeof( int ), compare2 );
    npa = 0;
    for( div = 1; div <= max( abs(list[0]) , abs(list[ 1 ]) ); div++)
       if( ((list[ 0 ] % div) + div ) % div == ((list[ 1 ] % div) + div ) % div) posibleAnswer[ npa++ ] = div;
Orderno la nueva lista sin elementos repetidos, pero en vez de ordenarlo de menor a mayor, los ordeno de menor a mayor, pero aplicando la funcion de valor absoluto a los numeros. Despues procedo a fuerza bruta ver todos los numero que su residuo sea igual del primer y el segundo elemento de la lista,

Por que hago (( A % div) + div) % div ?

Cuando era niño me preguntaba si los numero negativos al dividirlos sus residuos eran positivos, bueno asi es, pero cuando lo haces en C/C++ eso no es cierto, el residuo es negativo y lo tienes que volver positivo, por eso primero saco el residuo de A / div , despues le sumo div, esto asegura que se vuelva positivo, y por ultimo le vuelvo a sacar el residuo, ya que si era positivo el residuo al sumarle div se saldria del rango de [0, div - 1].
Ya despues de que cuajo la solucion, lo que resta es hacer un barrido con todos los numeros pero en vez de checar todos los divisores posibles, solo revisamos las pisibles soluciones ( en este caso las guarde en posibleAnswer ), y al momento de varificar si el nuevo numero tambien tiene como resuduo una posible solucion, se van eliminando los que no cumplen.
    for( x = 2; x < nsize; x++){
      nextsize = 0;
      for( div = 0; div < npa; div++){
        if(  ((list[ 0 ] % posibleAnswer[ div ])+ posibleAnswer[ div ] ) % posibleAnswer[ div ] 
             == ( ( list[ x] % posibleAnswer[div]) + posibleAnswer[ div ] ) % posibleAnswer[ div ] ){
           posibleAnswer[ nextsize++ ] = posibleAnswer[ div];
        }
      }
      npa = nextsize;
    }

Al final solo hay que imprimir el ultimo valor de nuestras posibles soluciones posibleAnswer[ npa - 1]

/* 
 Autor: Rodrigo Burgos Dominguez
 Problema: UVA 10407 Simple division
 Solucion: Fuerza Bruta pero no tanto.
*/

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


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

int compare( int *a, int *b){ return *a - *b; }
int compare2( int *a, int *b){ return abs(*a) - abs(*b); }

int list[ 1002 ], n;
int posibleAnswer[1000*1000], npa;

main(){
  int a, b, x, y,  nsize, nextsize, div;
  while(1){
    for( n = 0; scanf("%d", &list[ n ]) != EOF && list[ n ] != 0 ; n++);
    if( n == 0 ) break;
    qsort( list, n, sizeof( int ), compare );
    nsize = 1;
    for( x = 1; x < n; x++){
       if( list[ x ] != list[ x - 1]){
           list[ nsize++ ] = list[x];
       }
    }
    qsort( list, nsize, sizeof( int ), compare2 );
    npa = 0;
    for( div = 1; div <= max( abs(list[0]) , abs(list[ 1 ]) ); div++)
       if( ((list[ 0 ] % div) + div ) % div == ((list[ 1 ] % div) + div ) % div) posibleAnswer[ npa++ ] = div;
    for( x = 2; x < nsize; x++){
      nextsize = 0;
      for( div = 0; div < npa; div++){
        if(  ((list[ 0 ] % posibleAnswer[ div ])+ posibleAnswer[ div ] ) % posibleAnswer[ div ] 
             == ( ( list[ x] % posibleAnswer[div]) + posibleAnswer[ div ] ) % posibleAnswer[ div ] ){
           posibleAnswer[ nextsize++ ] = posibleAnswer[ div];
        }
      }
      npa = nextsize;
    }
    printf("%d\n", posibleAnswer[ npa - 1]);
  }
  return 0; 
}
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
Manuel me copartio su solucion ya reducida matematicamente, vean como el algoritmo que el muestra es corto y elegante basandose en las propiedad de los numeros: http://thnkndblv.blogspot.mx/2012/08/10407-simple-division.html

2 comentarios:

fanatico dijo...

una version similar de este problema aparecio en la ronda de calificación del code jam 2010 Problem B. Fair Warning el analisis del problema es bastante detallado

fanatico dijo...

por cierto, felicidades, tu blog es fantastico...explicas con mucho detalle los algoritmos...