Título: Binaries Palindromes
ID: 1101
Descripción
Given two positive integers, determine which are the integers in this range that have a palindrome binary representation. It will include ends of the interval.
Especificación de entrada
The input has the following format: In the first line an integer n, 50 <= n <= 200, indicating the intervals will be analyzed below. Then will follow n lines, each of which contains the numbers that define the range separated by a blank space. The numbers that make up the range are in the range from 1 to 200000.
Especificación de salida
The output consists of n lines, each line will be the set of numbers whose binary equivalents are palindromes. The numbers in this sequence are separated by a blank space. If there is no binary palindromes in the interval, the line is changed leaving this completely blank.
Ejemplo de entrada
6
247 333
375 609
70 154
124 301
956 961
682 769
Ejemplo de salida
255 257 273 297 313 325
381 387 403 427 443 455 471 495 511 513 561 585
73 85 93 99 107 119 127 129 153
127 129 153 165 189 195 219 231 255 257 273 297
693 717 765
http://coj.uci.cu/24h/problem.xhtml?abb=1101
Solucion:
Una opción para solucionar este problema consiste en almacenar en un vector todos los números menores o igual a 200000 cuya representación binaria es un palindromo. Luego para cada intervalo
buscamos si sus elementos estan en el vector de palindromos.
Ahora tenemos que ver como saber si la representación binaria de un numero es un palindromo. Lo primero que se le ocurre a cualquier persona es:
Convertir el numero a binario.
Almacenar esta representacion binaria en un vector de caracteres.
Recorrer desde los 2 extremos hacia el centro, verificando que los caracteres en posiciones
opuestas sean los mismos.
Esa solución es muy burda y lenta. Otra opción mucho más es invertir el numero en base 2, y luego comparar si este nuevo numero invertido es igual al original:
// Invertir un numero en base 'b'
int inverso = 0;
while( num > 0 )
{
inverso = b * inverso + ( num % b );
num = num / b;
}
return num == inverso
Es de notar que para el caso de base 2, podemos usar los operadores de bit: <<, >>, &.
Debemos de notar que no es necesario invertir completamente el numero, sino solo hasta que en num se almacene la mitad izquierda y en inverso se almacene la mitad derecha. Luego realizar la igualdad.
Tambien debemos de tener cuidado con el caso especial que se da cuando el numero tiene una cantidad impar de bits.
Por tanto el algoritmo para saber si la representacion binaria de un numero es un palindromo es la siguiente:
// Saber si un numero es palindromo en binario
int inverso = 0;
while( num > inverso )
{
inverso = ( inverso << 1 ) + ( num & 1 );
num = num >> 1;
}
if( num == inverso )
return true;
return num == ( inverso >> 1 );
Solución en Java
import java.io.IOException;
public class Problema1101 {
static char bufferSalida[] = new char[ 800000 ];
static int longitud;
static int tamanio = 0;
public static void main(String[] args) throws IOException
{
// Cantidad de casos que se analizaran
int N = sig();
// Almacenara todos los palindromos menores que 200009
int palin[] = new int[ 1000 ];
// Limites del intervalo donde se buscaran los primos binarios
int inf, sup;
int cont = 0;
// Indica si se encontro al menos un palindromo
boolean hayPalin;
for( int i = 1; i <= 200000; i = i + 2 )
{
if( esPalindromo( i ) )
palin[ cont ++ ] = i;
}
// Palindromo que servira como limite superior
palin[ cont ++ ] = 200009;
for( int i = 0; i < N; i ++ )
{
// Limites inferior y superior del intervalo
inf = sig(); sup = sig();
cont = 0;
// Ubicamos el primer palindromo
while( palin[ cont ] < inf )
cont ++;
hayPalin = false;
while( true )
{
if( palin[ cont ] > sup )
break;
// Mientras sea menor que sup, lo anadimos a la salida
salida( palin[ cont ] + " " );
cont ++;
// Se encontro al menos un palindromo
hayPalin = true;
}
// Eliminamos el ultimo espacio en blanco
if( hayPalin )
tamanio --;
bufferSalida[ tamanio ++ ] = '\n';
}
System.out.print( new String( bufferSalida, 0, tamanio ) );
}
// Anade salida, al buffer que almacena el output del problema
public static void salida( String salida )
{
longitud = salida.length();
salida.getChars( 0, longitud, bufferSalida, tamanio );
tamanio = tamanio + longitud;
}
public static int sig() throws IOException
{
int car = System.in.read();
int num = 0;
do
{
num = 10 * num + car - 48;
car = System.in.read();
}
while( car > 47 && car < 58 );
return num;
}
public static boolean esPalindromo( int num )
{
int inverso = 0;
while( num > inverso )
{
inverso = ( inverso << 1 ) + ( num & 1 );
num = num >> 1;
}
if( num == inverso )
return true;
return num == ( inverso >> 1 );
}
}
Solución en C ANSI
#include
int esPalindromo( int );
int main()
{
// Almacena todos los palindromos menores que 200009
int palindromos[ 1000 ];
// Cantidad de casos a analizar
int N;
// Limites del intervalo donde se buscaran los palindromos
int inf, sup;
int i, cont = 0;
// Almacenamos todos los palindromos
for( i = 1; i <= 200000; i = i + 2 )
{
if( esPalindromo( i ) )
palindromos[ cont ++ ] = i;
}
// Palindromos que servira de techo
palindromos[ cont ] = 200009;
scanf( "%d", &N );
for( i = 0; i < N; i ++ )
{
// Limites inferior y superior del intervalo
scanf( "%d %d", &inf, &sup );
cont = 0;
// Ubicamos el primer palindromo
while( palindromos[ cont ] < inf )
cont ++;
int espacio = 0;
while( 1 )
{
if( palindromos[ cont ] > sup )
break;
if( espacio ) printf( " " );
// Mientras sea menor que sup, lo anadimos a la salida
printf( "%d", palindromos[ cont ++ ] );
espacio = 1;
}
printf( "\n" );
}
return 0;
}
int esPalindromo( int num )
{
int inverso = 0;
while( num > inverso )
{
inverso = ( inverso << 1 ) + ( num & 1 );
num = num >> 1;
}
if( num == inverso )
return 1;
return num == ( inverso >> 1 );
}
Great 03!
ResponderEliminar