Download Solucionario del Nivel 2 (2011) - usando PSEINT

ACM – ICPC Bolivia
Solucionario Consolidado
Utilizando PSeInt
1ra Olimpiada Boliviana de Informática
Estado Plurinacional de Bolivia, febrero de 2013
Contenidos
Final Nacional 2011 ............................................................................................................ 1
Problema A: Múltiplo Pequeño ...................................................................................... 1
Problema B: El resto ....................................................................................................... 3
Problema C: Cuando Ver Películas................................................................................. 4
Problema D: La granja de Juan y José ............................................................................ 6
Clasificatorio 2011 .............................................................................................................. 7
Problema A - Acuario ..................................................................................................... 7
Problema B - Bits .......................................................................................................... 10
Problema C - Tienda de Botas ...................................................................................... 12
Problema D - Serie curiosa ........................................................................................... 14
Alberto J. Suxo Riveros
<[email protected]>
Alberto J. Suxo Riveros
1
ACM – ICPC Bolivia
Final Nacional 2011
Problema A: Múltiplo Pequeño
Muchos números naturales de base 10 consisten en múltiples números 1 y 0. Por
ejemplo el número once 11, el diez 10 el ciento uno 101.
Dado un numero X se desea conocer cuál es el múltiplo más pequeño de X que puede
formarse exclusivamente de unos y ceros.
Si X = 55 el múltiplo más pequeño que podemos formar con unos y ceros es 110.
Entrada
En la entrada defina X = 7.
Salida
Escriba en una línea el número formado por unos y ceros más pequeño que es múltiplo
de X.
Ejemplos
X
2
5
10
25
Respuesta
10
10
10
100
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : Multiplos Pequeños
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
// Verifica si un numero esta compuesto
// unicamente por unos y ceros
SubProceso resultado <- verificar ( numero )
Definir num Como Entero;
Definir resultado Como Logico;
resultado <- Verdadero;
num <- numero;
Mientras num > 0 Hacer
Si num%10 > 1 Entonces
resultado <- Falso;
FinSi
num <- num / 10;
FinMientras
FinSubProceso
Proceso MultiploPequeno
Definir x, m Como Entero;
Definir buscar Como Logico;
Alberto J. Suxo Riveros
1
ACM – ICPC Bolivia
Leer x;
buscar <- Verdadero;
m <- 0;
Mientras buscar Hacer
m <- m + 1;
Si verificar( x*m ) Entonces
Escribir (x*m);
buscar <- Falso;
FinSi
FinMientras
FinProceso
Alberto J. Suxo Riveros
2
ACM – ICPC Bolivia
Problema B: El resto
Los números de Fibonacci se generan con la ecuación:
f n = f n−1 + f n−2
La lista de números generados por esta secuencia son 1, 1, 2, 3, 5, 8, 13, 21,... etc. Los
primeros números de esta secuencia se definen como sigue:
i
Fib(i)
0
1
1
1
2
2
3
3
4
5
5
8
6
13
7
21
Dado un número X se desea conocer el resto de dividir un determinado número
Fibonacci por X.
Por ejemplo si X = 7, y i = 6 en resto seria 13 %7 = 6.
Entrada
Defina en su programa i = 19 y X = 29.
Salida
Escriba en una línea el resto de dividir el Fibonacci i por X.
Ejemplos
i
3
6
3
x
7
9
11
Respuesta
3
4
3
Solución
// Olimpiada Boliviana De Informatica
// Problema : El Resto
// Autor
: Alberto Suxo
// Copyright: Team SIM
// Lenguaje : Pseudocodigo PSeInt
// *******************************
Proceso Resto
Definir x, i Como Entero;
Definir Fib, n Como Entero;
Dimension Fib[100];
Leer i;
Leer x;
Fib[0] <- 1;
Fib[1] <- 1;
Para n<-2 Hasta i Hacer
Fib[n] <- Fib[n-1] + Fib[n-2];
FinPara
Escribir ( Fib[i] % x );
FinProceso
Alberto J. Suxo Riveros
3
ACM – ICPC Bolivia
Problema C: Cuando Ver Películas
En la ciudad de La Paz existen diferentes lugares para ver películas pero ninguno como
el Cine IOI. El precio de las entradas en este cine varía dependiendo el día, 10
Bolivianos los días Miércoles 30 Bolivianos los Sábados y Domingos y 20 Bolivianos los
demás días.
Considerando que hoy es Lunes y solo podemos ver una película al día, ayúdanos a
elegir los días en los que tenemos que ver N películas de tal forma que nos salga lo
más económico posible.
Entrada
Defina en su programa los días para ver películas en 92 y el número de películas a ver
en 62.
Entrada
Por cada caso de prueba imprima una línea con el mínimo costo para ver películas.
Ejemplos
Días para ver Películas
2
3
7
Número Películas
1
1
7
Resultado
20
10
150
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : Cuando Ver Peliculas
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
Proceso CuandoverPeliculas
Definir dias, peliculas Como Entero;
Definir P, D Como Entero;
Definir resp, i, j, aux Como Entero;
Dimension P[7];
Dimension D[100];
Leer dias;
Leer peliculas;
P[0] <- 20;
P[1] <- 20;
P[2] <- 10;
P[3] <- 20;
P[4] <- 20;
P[5] <- 30;
P[6] <- 30;
Para i<-0 Hasta dias-1 Hacer
D[i] <- P[i%7];
FinPara
// Ordenar
Para i<-0 Hasta dias-2 Hacer
Alberto J. Suxo Riveros
4
ACM – ICPC Bolivia
Para j<-i+1 Hasta dias-1 Hacer
Si D[i] > D[j] Entonces
aux <- D[i];
D[i] <- D[j];
D[j] <- aux;
FinSi
FinPara
FinPara
resp <- 0;
Para i<-0 Hasta peliculas-1 Hacer
resp <- resp + D[i];
FinPara
Escribir resp;
FinProceso
Alberto J. Suxo Riveros
5
ACM – ICPC Bolivia
Problema D: La granja de Juan y José
Juan y José tienen una granja de gallinas y vacas, un día se les ocurrió contar el
número de cabezas y el número de patas de los animales (vacas y gallinas) en la
granja. Juan contó un total de 3 cabezas y José contó un total de 8 patas del total de
animales en la granja. Juan hizo algunos cálculos y determino que existen 3 gallinas y 1
vaca. José noto que Juan tarda demasiado en hacer los cálculos, así que pide tu ayuda
para poder obtener una solución general del problema.
Nota.- Una gallina tiene 1 cabeza y 2 patas. Una vaca tiene 1 cabeza y 4 patas. Si la
solución existe, esta siempre es única.
Entrada
En su programa defina el número de cabezas = 8200 y del patas = 18844.
Salida
Escriba en la salida separado por un espacio el número de gallinas y el segundo es el
número de vacas. En caso de no existir solución imprimir -1;
Ejemplos
Cabezas
3
10
1
Patas
8
40
3
Resultado
2 1
0 10
-1
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : La Granja de Juan y Jose
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
Proceso Granja
Definir cabezas, patas Como Entero;
Definir gallinas, vacas Como Entero;
Leer cabezas;
Leer patas;
Si patas%2 = 1 Entonces
Escribir -1; //"No hay Solucion";
Sino
vacas <- patas/2 - cabezas;
gallinas <- cabezas - vacas;
Si vacas<0 | gallinas < 0 Entonces
Escribir -1; //"No hay Solucion";
Sino
Escribir gallinas, " ", vacas;
FinSi
FinSi
FinProceso
Alberto J. Suxo Riveros
6
ACM – ICPC Bolivia
Clasificatorio 2011
Problema A - Acuario
Es bien conocido que en un acuario algunos peces se pueden comer a otros. Usted
tiene un acuario que contiene una cantidad de peces del cual conoce el tamaño.
Usted sabe que un pez se puede comer a otro, solo cuando está en el rango de: el
doble de tamaño o 10 veces más grande.
Se quiere agregar un pez a la pecera, pero queremos determinar el tamaño para no
causar conflictos de comerse con otros peces.
Considerando esto usted debe escoger un pez que esté entre los siguientes tamaños
•
•
No hay riesgo de ser comido por otro pez si su tamaño no está entre 1/10 y 1/2
inclusive, del tamaño de otro pez.
No tiene tentación de comerse a otro pez si el tamaño de los otros peces no
están entre 1/10 y 1/2 inclusive de su tamaño.
Por ejemplo si los tamaños de los peces están entre 1 y 12 y queremos insertar un pez,
ese puede tener tres posibles tamaños. Los posibles tamaños para el pez que están
fuera del rango establecido son 1, 11, 12.
Entrada
La entrada consiste de varias líneas. La primera línea de un caso de prueba consiste en
el tamaño más pequeño. La segunda línea consiste en el tamaño más grande que
puede tener. La tercera línea tiene el número de peces en el acuario. La cuarta línea
tiene los tamaños de los peces del acuario separados por un espacio.
Salida
Escriba en una línea el número de tamaños que puede hallar y que no causen conflictos
entre peces.
Ejemplos de entrada
Ejemplos de salida
Ejemplo 1
1
12
1
1
Ejemplo 2
2
999
6
941 797 120 45 7 120
Salida del Ejemplo 1
3
Salida del Ejemplo 2
10
Alberto J. Suxo Riveros
7
ACM – ICPC Bolivia
Problema
Para el dato de entrada siguiente escriba un programa que halle la respuesta.
3
997
16
10 11 12 13 14 16 82 83 84 85 720 730 740 750 760 770
La respuesta que debes entregar es:
147
Análisis y Solución
La solución del problema es bastante sencilla:
Se debe tomar todos los tamaños de los peces desde el más pequeño que en nuestro
programa llamaremos tamMin hasta el más grande que denominaremos tamMax.
Para cada uno de los tamaños de peces se verifica si algún pez se lo puede comer. Si
no se lo puede comer contamos este tamaño como una solución.
Al final imprimimos cuantas soluciones hemos encontrado.
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : Acuario
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
SubProceso resp <- come( a, b )
Definir resp como Logico;
Definir min, max Como Real;
min <- a/10.0;
max <- a/2.0;
Si min<=b && b<=max Entonces
resp <- Verdadero;
Sino
resp <- Falso;
FinSi
FinSubProceso
Proceso Acuario
Definir n, tamMin, tamMax Como Entero;
Definir i, j, respuesta como Entero;
Definir valido como Logico;
Definir Pez Como Entero;
Dimension Pez[200];
Leer tamMin;
Leer tamMax;
Leer n;
Alberto J. Suxo Riveros
8
ACM – ICPC Bolivia
Para i<-0 Hasta n-1 Hacer
Leer Pez[i];
FinPara
respuesta <- 0;
Para i<-tamMin Hasta tamMax Hacer
valido <- Verdadero;
Para j<-0 Hasta n-1 Hacer
Si come(i,Pez[j]) || come(Pez[j],i) Entonces
valido <- Falso;
FinSi
FinPara
Si valido Entonces
respuesta <- respuesta + 1;
FinSi
FinPara
Escribir respuesta;
FinProceso
Alberto J. Suxo Riveros
9
ACM – ICPC Bolivia
Problema B - Bits
Las computadoras operan en números binarios. Casi todos los cálculos se realizan
manipulando 0’s y 1’s. Para que las computadoras puedan utilizar los números que le
damos hay que convertirlos de la base 10 que normalmente usamos, a la base binaria
(2). En muchas ocasiones es ´útil determinar cuantos bits se requieren para representar
un número, con la finalidad de ahorrar espacio. Por ejemplo cualquier número menor a
256 se puede representar con 8 bits.
Para hallar el equivalente decimal de un número binario procedemos como sigue: Para
cada número 1 sumamos las potencias 2i donde i el número de dígitos a la derecha del
uno. Por ejemplo el equivalente decimal del número binario 10100 se halla como sigue:
a la derecha del primer 1 hay 4 dígitos dando 24 = 16, a la derecha del segundo 1 hay
dos dígitos que representa 22 = 4. Sumando ambos tenemos su equivalente decimal
que es 20.
Entrada
La entrada contiene el número que queremos representar en binario.
Salida
Escriba en una línea el número mínimo de bits que se requiere para representar este
número.
Ejemplos de entrada
Ejemplos de salida
32
12
1
6
4
1
Problema
Para el dato de entrada siguiente escriba un programa que halle la respuesta.
1500
La respuesta que debes entregar es:
11
Análisis y Solución
Para hallar el número de bits necesarios para representar un número en binario
hallamos el logaritmo en base 2.
Veamos algunos ejemplos. El número 8 se escribe en binario 1000 o sea todos
números menores a 8 se pueden representar con 3 bits. 8−1 = 7 en binario 111. Con 4
bits podemos representar hasta el número 15.
Vemos que entonces 23 = 8 y con 3 + 1 bits podemos representar hasta el 15.
Resolviendo con logaritmos hallamos la respuesta.
Como la función logaritmos no es en base 2 es necesario hacer el cambio de base.
Alberto J. Suxo Riveros
10
ACM – ICPC Bolivia
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : Bits
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
Proceso Bits
Definir n, respuesta como Entero;
Leer n;
respuesta <- LN(n)/LN(2) + 1;
Escribir respuesta;
FinProceso
Alberto J. Suxo Riveros
11
ACM – ICPC Bolivia
Problema C - Tienda de Botas
Una tienda de botas ha recibido un embarque de una fábrica. Consiste en N botas
izquierdas y N botas para el pie derecho. Una bota izquierda con otra derecha harán un
par si son del mismo tamaño.
Cada bota solo puede pertenecer a un solo par. Los empleados de la tienda de botas
quieren crear N pares de botas. Afortunadamente la fábrica ha prometido cambiar
cualquier número de botas en el embarque por nuevas en diferentes tamaños.
Se tiene todas las botas izquierdas y derechas con sus números. Escriba un programa
que devuelva el mínimo número de botas que deben ser intercambiadas.
Entrada
Los datos de entrada consiste de varias líneas, la primera línea contiene el número N de
botas izquierdas. Las botas derechas son la misma cantidad. La segunda línea contiene
N números que representan los tamaños de las botas izquierdas. La tercera línea
contiene N números con los tamaños de las botas derechas.
Salida
Escriba en una línea con el mínimo numero de botas a ser intercambiadas.
Ejemplos de entrada
Ejemplo
3
1 3 1
2 1 3
Ejemplo
2
1 3
2 2
Ejemplo
7
1 2 3 4
2 4 6 1
de entrada 1
de entrada 2
de entrada 3
5 6 7
3 7 5
Ejemplos de salida
Salida para el ejemplo 1
1
Salida para el ejemplo 2
2
Salida para el ejemplo 3
0
Problema
Para el dato de entrada siguiente escriba un programa que halle la respuesta.
10
5 2 1 4 7 9 1 1 3 4
2 5 1 3 4 6 3 2 2 5
La respuesta que debes entregar es:
5
Alberto J. Suxo Riveros
12
ACM – ICPC Bolivia
Análisis y Solución
Este programa consiste en saber cuántos pares de botas debemos intercambiar. Para
esto primero ordenamos las botas por talla y vemos cuales igualan. De los que no
igualan debemos hacer el cambio. La forma adecuada se muestra en psudocodigo.
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : Tienda de Botas
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
Proceso TiendaDeBotas
Definir n Como Entero;
Definir Izq, Der Como Entero;
Definir i, j, aux, resp Como Entero;
Definir seguir Como Logico;
Dimension Izq[200];
Dimension Der[200];
Leer n;
// Leer todas las botas izquierdas
Para i<-0 Hasta n-1 Hacer
Leer Izq[i];
FinPara
// Leer todas las botas derechas
Para i<-0 Hasta n-1 Hacer
Leer Der[i];
FinPara
resp <- n;
Para i<-0 Hasta n-1 Hacer
seguir <- Verdadero;
Para j<-0 Hasta n-1 Hacer
Si seguir && Izq[i] = Der[j] Entonces
Der[j]<- -1;
resp <- resp - 1;
seguir <- Falso;
FinSi
FinPara
FinPara
Escribir resp;
FinProceso
Alberto J. Suxo Riveros
13
ACM – ICPC Bolivia
Problema D - Serie curiosa
Se tiene una serie que tiene como datos de la misma d números los mismos que son
enteros positivos. Por ejemplo si se tiene los siguientes 4 números datos de la serie: 1,
2, 3, 4; los restantes se generan así:
1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6........
El problema es que se quiere encontrar el n-ésimo, en el ejemplo planteado el 7mo
elemento será 4.
Entrada
Se da como entrada dos números enteros positivos n, d, el primero corresponde al nésimo elemento que se quiere encontrar y el segundo es la cantidad de números dato
que la serie tendrá. d puede estar entre 3 y 10 inclusive; y n puede estar entre 1 y
100000 inclusive.
En la siguiente línea se encuentran d números enteros que son los datos iniciales de la
serie.
Salida
La salida es un entero positivo que corresponde al n-ésimo número de la serie.
Ejemplos de entrada
10
5
1 3 5 7 9
Ejemplos de salida
10
Problema
Para el dato de entrada siguiente escriba un programa que halle la respuesta.
10000
5
1 3 2 7 5
La respuesta que debes entregar es:
2004
Solución
//
//
//
//
//
//
Olimpiada Boliviana De Informatica
Problema : Serie Curiosa
Autor
: Alberto Suxo
Copyright: Team SIM
Lenguaje : Pseudocodigo PSeInt
*******************************
Proceso SerieCuriosa
Definir n, d Como Entero;
Definir Nums Como Entero;
Alberto J. Suxo Riveros
14
ACM – ICPC Bolivia
Definir i, datoBase, incr Como Entero;
Dimension Nums[11];
Leer n;
Leer d;
Para i<-0 Hasta d-1 Hacer
Leer Nums[i];
FinPara
datoBase <- n % d;
incr <- n / d;
Si datoBase = 0 Entonces
datoBase <- d;
incr <- incr - 1;
FinSi
Escribir (Nums[datoBase-1] + incr);
FinProceso
Alberto J. Suxo Riveros
15