UVA 12444 Bits and Piecest (Greedy)

UVA 12444 Bits and Piecest

http://uva.onlinejudge.org/external/124/12444.html
Este problema a simple vista parece difícil, pero al analizar un poco como se comporta los operadores binarios de AND y OR, nos damos cuenta que siempre debe tener los dos números, tanto A como B, los mismo bits de C, si existiera un bit en C que no estuviera prendido en D entonces hay un error, para encontrar el número cuya diferencia de |B - A| sea mínima, solo hace falta notar que todos los bits que no están C pero si están en D, el bit con valor mas alto se asigna a el valor de B y todos los demás bits se suman a A.

/*
  Problem: UVA 12444 Bits and Pieces
  Autor: Rodrigo Burgos Dominguez
  Problem: Let A and B be non-negative integers and let C = A&B and D = A|B. Given C and D, 
           can you find A and B such that the absolute difference (|A-B|) is minimal?
  Solution: greedy
*/

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

int transform[2][32];

long long max( long long a, long long b){ return a > b ? a : b; }
long long min( long long a, long long b){ return a < b ? a : b; }

void trans(int indice, long long number){
  int pos;
  memset( transform[ indice ], 0, sizeof( transform[ indice ]));
  for( pos = 0; number > 0 ; pos++){ 
    transform[indice][pos] = (number % 2);
    number /= 2;
  }
}

main(){
  int cases, ncases, notSolution, x;
  long long C, D, A, B, pot, last;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
   scanf("%lld %lld", &C, &D);
   trans( 0, C );
   trans( 1, D );
   notSolution = A = B  = last = 0;
   for( x = 0, pot = 1; x < 32; x++, pot *= 2){
     if( transform[ 0 ][ x ] > 0 && transform[1][x] == 0 )  notSolution = 1;
     if( transform[ 0 ][ x ] > 0 ){
        A += pot;
        B += pot;
     }else if( transform[ 1 ][ x ] > 0 ){
       A += last;
        last = pot;
     }
   }
   B += last;
   if( notSolution == 1 ) printf("-1\n");
   else printf("%lld %lld\n", min(A,B), max(A,B));
  }
  return 0; 
}

Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com