Problema E: MCDFAC UNMSM-FISI 2011

Concurso de Programación UNMSM-FISI 2011

Problema E: MCDFAC

Descargar problema: UNMSM-FISI 2011 Problema E

import java.io.*;

public class ProblemaE
{
    public static void main( String args[] ) throws Exception
    {
        BufferedReader br = new BufferedReader( new InputStreamReader( 
                                                System.in ) );

        int numCasos;       // Cantidad de casos a analizar
        int a, b;           // Par de valores a analizar
        int mcd;            // MCD 
        int[] exp;          
        int limite;         // Limite hasta donde se buscaran divisores

        String[] valores;

        numCasos = Integer.parseInt( br.readLine() );

        for( int i = 0; i < numCasos; i ++ )
        {
            // Leemos los valores de entrada
            valores = br.readLine().split( " " );

            a = Integer.parseInt( valores[ 0 ] );
            b = Integer.parseInt( valores[ 1 ] );

            mcd = 1;

            // Verificamos si el segundo es multiplo de 2
            if( b % 2 == 0 )
            {
                exp = factor( b, 2 );

                b = exp[ 0 ];

                // Calculamos el menor exponente de 2, en los 2 numeros
                mcd = (int)Math.pow( 2, Math.min( exp[ 1 ], maximo( a, 2 ) ) );
            } 
   
            // Numero maximo que puede ser divisor de 'b'
            limite = (int)Math.sqrt( b );

            for( int j = 3; j <= limite; j = j + 2 )
            {
                // Buscamos los siguientes divisores de 'b'
                if( b % j == 0 )
                {
                    exp = factor( b, j );
                    b = exp[ 0 ];
   
                    // Calculamos el menor exponente de 'j' en los 2 numeros
                    mcd *= Math.pow( j, Math.min( exp[ 1 ], maximo( a, j)));

                    // Calculamos el nuevo limite
                    limite = (int)Math.sqrt( b );
                }
            }

            // Si el resto es diferente de 1, es un primo, lo añadimos al MCD
            if( b != 1 && b <= a )
    mcd *= b; 

            System.out.println( "Caso #" + (i+1) + ": " + mcd ); 
        }
    }

    // Calcula el exponente de 'divisor' en la descomposicion canonica de 'n'
    public static int[] factor( int n, int divisor )
    {
        int[] exp = { n, 0 };

        while( exp[ 0 ]  % divisor == 0 )
        {
            exp[ 1 ] ++;
            exp[ 0 ] /= divisor;
        }

        return exp;
    }

    // Calcula el exponente de 'divisor' en la descomposicion canonica de n!
    public static int maximo( int n, int divisor )
    {
        int maximo = 0;

        while( n >= divisor )
        {
            n = n/divisor;
            maximo += n;
        }

        return maximo;
    }
}

Problema C: Validador de Entrada UNMSM-FISI 2011

Concurso de Programación UNMSM-FISI 2011

Problema C: Validador de Entrada

Descargar problema: UNMSM-FISI 2011 Problema C

public class ProblemaC
{
    // Indica si se termino de leer la linea
    static boolean termino;

    public static void main( String args[] ) throws Exception
    {
        int numCasos[]; // Numero de casos que se analizaran
        int a[], b[];   // Limite inferior y superior del intervalo
        int[] valoresA; // Almacena los prefijos de 1, 2, ... digitos de a
        int[] valoresB; // Almacena los prefijos de 1, 2, ... digitos de b
        int[] numero;   // Numero que se analizara
        int pos;
        long temp;
 
        numCasos = leer();

        for( int i = 0; i < numCasos[ 0 ]; i ++ )
        {
            termino = false;

            a = leer();
            b = leer();

            // Creamos los prefijos de 1, 2, ... digitos de a y b
            valoresA = new int[ a[1] ];
            valoresB = new int[ a[1] ];
   
            // Hacemos una copia de los valores de a y b
            int copiaA = a[ 0 ], copiaB = b[ 0 ];
 
            for( int j = valoresA.length - 1; j >= 0; j -- )
            {
                // Guardamos los prefijos
                valoresA[ j ] = copiaA;
                valoresB[ j ] = copiaB;

                // Generamos los siguientes prefijos
                copiaA /= 10;
                copiaB /= 10;
            } 

            System.out.print( "Caso #" + (i+1) + ":" );

            // Leemos los numeros a comparar
            while( !termino )
            {
                numero = leer();
                temp = 10l * numero[ 0 ];
    
                if( numero[ 1 ] >= a[ 1 ] )
                    pos = a[ 1 ] - 1;
                else
                    pos = numero[ 1 ] - 1;
                
                // Si el numero leido es mayor que el limite inferior, debera 
                // estar dentro de los valores del intervalo
                if( numero[ 0 ] >= valoresA[ pos ] )
                {
                    if( numero[ 0 ] <= valoresB[ pos ] )
                        System.out.print( " 1" );
                    else
                        System.out.print( " 0" );
                } 
   
                // Si el numero leido es menor que el limite inferior, el mismo
                // numero multiplicado por 10 debera estar dentro del intervalo
                else if( temp  >= valoresA[ pos ] && temp <= valoresB[ pos ] )
                    System.out.print( " 1" );
                else
                    System.out.print( " 0" ); 
            }
   
            System.out.println();
        } 
    }
    
    // Retorna el siguiente numero de la entrada, ademas de su longitud
    public static int[] leer() throws Exception
    {
        int[] numero = new int[ 2 ];
        int car = System.in.read();
  
        while( car > 47 && car < 58 )
        {
            numero[ 0 ] = 10 * numero[ 0 ] + car - 48;
            numero[ 1 ] ++;

            car = System.in.read();
        }
  
        // Si se encontro el fin de linea, indicamos que se termino la linea
        if( car == '\n' )
            termino = true;

        // Si encontramos una coma nos saltamos el espacio en blanco
        else if( car == ',' )
            System.in.read();
  
        return numero;
    }
}

Problema B: Número Profundo UNMSM-FISI 2011

Concurso de Programación UNMSM-FISI 2011

Problema B: Número Profundo

Descargar problema: UNMSM-FISI 2011 Problema B

import java.io.*;

public class ProblemaB
{
    public static void main( String args[] ) throws Exception
    {
        int numero, cantNumeros, indice, producto, copia;

        // Permitira leer los datos de entrada
        BufferedReader br = new BufferedReader( new InputStreamReader(
            System.in ) );

        // Cantidad de casos que se analizaran
        cantNumeros = Integer.parseInt( br.readLine() );

        for( int i = 0; i < cantNumeros; i ++ )
        {
            numero = Integer.parseInt( br.readLine() );
            indice = 0;

            // Seguimos procesando el numero mientras tenga mas de 1 digito
            while( numero > 9 )
            {
                producto = 1;
                copia = numero;

                // Cada producto parcial se multiplica por el digito de la derecha
                while( copia > 0 )
                {
                    producto = producto * ( copia % 10 );
        
                    // Eliminamos el digito más a la derecha
                    copia = copia / 10;
                }

                // Actualizamos el numero
                numero = producto;

                indice ++;
            }

            System.out.println( "Caso #" + (i+1) + ": " + indice );
        }
    }
}

Problema A: Dígitos Divisores UNMSM-FISI 2011

Concurso de Programación UNMSM-FISI 2011

Problema A: Dígitos Divisores

Descargar problema: UNMSM-FISI 2011 Problema A

import java.io.*;

public class ProblemaA
{
    public static void main( String args[] ) throws IOException
    {
        // Permitira leer datos ingresados
        BufferedReader br = new BufferedReader( new InputStreamReader(
                                                System.in ) );

        // Cantidad de numeros que se analizaran
        int cantNumeros = Integer.parseInt( br.readLine() );

        // Almacena cada numero leido
        int numero;

        // Cantidad de digitos de 'numero' que pueden dividir a numero
        int cantDivisores;

        // Permitira trabajar con el numero sin modificar el original
        int copia;

        for( int i = 0; i < cantNumeros; i ++ )
        {
            numero = Integer.parseInt( br.readLine() );

            copia = numero;

            cantDivisores = 0;
   
            // Procesamos cada digito que este más a la derecha
            while( copia > 0 )
            {
                // Verificamos que el digito sea diferente de cero
                // y si puede dividir a 'numero'
                if( copia % 10 != 0 && numero % ( copia % 10 ) == 0 )
                    cantDivisores ++;

                // Eliminamos el digito de más a la derecha
                copia = copia / 10;
            }  

            // Mostramos la salida
            System.out.println( "Caso #" + (i + 1) + ": " + cantDivisores);
        }
    }
}