PDF de programación - Problemas Resueltos

PROBLEMAS RESUELTOS

Jorge Terán Pomier
Docente de programación

[email protected]

Alberto Suxo Riveros
Docente de programación
[email protected]
[email protected]

La Paz – Bolivia, Noviembre 2007

PROBLEMAS RESUELTOS

ii

PROBLEMAS RESUELTOS

Indice

Varios

Impares o Pares .......................................................1
Analizando el problema ........................................2
Implementando una solución ................................3
Lotería de fin de semana ..........................................4
Analizando el problema ........................................5
Implementando una solución ................................6
Bubble Mapas...........................................................8
Analizando el problema ......................................10
Implementando una solución ..............................11
Solución 2. .........................................................15
Números Romanos.................................................20
Solución: ............................................................21
Cara o Cruz............................................................24
Solución .............................................................25

Cadenas

¿Fácil De Decir?.....................................................27
Solución .............................................................28

Despliegue

Instruens Fabulam..................................................34
Solución .............................................................36

Simulación

Colorville.................................................................41
Solución .............................................................43

Estructuras

Falling Leaves ........................................................47
Solución: ............................................................49

Math

Una Función Inductivamente-Definida.....................54
Solución .............................................................55
Raíz Digital Prima...................................................58
Solución .............................................................60
El Hotel con Habitaciones Infinitas..........................64
Solución .............................................................65
Regreso a la Física de Secundaria..........................67
Solución .............................................................67

i

PROBLEMAS RESUELTOS

¡Un Problema Fácil! ................................................69
Solución .............................................................70
Diagonales .............................................................72
Solución .............................................................73
Números Casi Primos.............................................77
Solución: ............................................................77

BackTracking

El Juego de Triángulos ...........................................81
Solución .............................................................82

Grafos

La Rana Saltadora..................................................87
Analizando el problema ......................................89
Implementando una solución ..............................90
Encontrando al Prof. Miguel ...................................95
Solución .............................................................97

ii

PROBLEMAS RESUELTOS

Impares o Pares

Tipos de archivos aceptados: odd.c, odd.cpp, odd.java

juego

Existen Muchas versiones de pares ó impares, un juego qué
muchos competidores realizan para decidir muchas cosas,
por ejemplo, quien resolverá este problema. En una
variación de este
los competidores comienzan
escogiendo ya sea pares ó impares. Después a la cuenta
de tres extiende una mano mostrando un número de dedos
que pueden ser de cero hasta cinco. Luego se suman la
cantidad escogida por los competidores. Si suma par la
persona que escogió par gana. Similarmente ocurre lo
mismo con la persona qué escoge impar, si suma impar
gana.

Juan y Miaría jugaron muchos juegos durante el día. En
cada juego Juan escogió pares (y en consecuencia Miaría
escogió impares). Durante los juegos se cada jugador anoto
en unas tarjetas el numero de dedos que mostró. Miaría
utilizo tarjetas azules, y Juan tarjetas rojas. El objetivo era el
de revisar los resultados posteriormente. Sin embargo al
final del día Juan hizo caer todas las tarjetas. Aún cuando
se podían separar por colores no podían ser colocadas en
orden original.

Dado un conjunto de números escritos en tarjetas rojas y
azules, usted debe escribir un programa para determinar el
mínimo de juegos que Miaría con certeza gano.

Input
La entrada consiste de varios casos de prueba. La primera
línea de la prueba consiste en un entero N que representa
el numero de juegos (1 N 100). La segunda línea es un
caso de prueba que contiene N enteros Xi, Indicando el
numero de dedos que mostró Miaría en cada uno de los
juegos (0 Xi 5, para 1 i N). La tercera línea contiene
N enteros Yi, el número de dedos que escogió Juan en cada
juego. (0 Yi 5, para 1 i N). El fin de archivo se indica
con N = 0.

La entrada se debe leer de standard input (teclado).

1

PROBLEMAS RESUELTOS

Output
Para cada caso de prueba su programa debe escribir en
una línea un numero de entero, indicando el mí mino
número de juegos que pudo haber ganado Miaría.

La salida debe ser standard output (pantalla).

Ejemplo de Entrada
3
1 0 4
3 1 2
9
0 2 2 4 2 1 2 0 4
1 2 3 4 5 0 1 2 3
0
Salida para el ejemplo de Entrada
0
3
Analizando el problema

Analicemos el primer ejemplo. Aquí Miaría escogió 1, 0,
4 y Juan 3, 1, 2. Analizando todas las posibilidades vemos
que estas son tres

Miaría
par
par
impar
impar

Juan
par
impar
par
impar

Suma
par
impar
impar
par

Veamos, todo número par puede escribirse como 2n y
todo numero impar como 2n + 1, de donde se puede
fácilmente deducir la tabla anterior.

Si analizamos cuantos impares escogió Miaría, se ve
que es solo el numero 1. La única posibilidad de ganar seria
cuando Juan escogió par o sea 2. En el caso de que Miaría
hubiese escogido par o sea 0 o 4 solo podría ganar cuando
Juan escogió 1.

2

PROBLEMAS RESUELTOS

Contando los casos tenemos:
Pares



Miaría
Juan

2
1

Impares

1
2

El mínimo número de juegos que Miaría podría ganar es

1 – 1.

Implementando una solución

La solución completa del problema es la siguiente:

import java.io.*;
import java.util.*;
public class Odds {

for (i = 0; i < n; i++) {

int Juan = 0, Maria = 0, x, n, i;
while ((n = in.nextInt()) > 0) {

/**
* J. Teran requieres jdk 1.5
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Juan = 0;
Maria = 0;
x = in.nextInt();
if ((x & 1) == 1)
Maria++;
}
x = in.nextInt();
if ((x & 1) == 0)
Juan++;
}
}
System.out.println(Juan Maria);
System.out.println(Maria - Juan);
}
}

if ( Juan > Maria )
else

for (i = 0; i < n; i++) {

3

PROBLEMAS RESUELTOS

Lotería de fin de semana

Tipos de archivos aceptados: lottery.c, lottery.cpp,

lottery.java
Algunas personas están contra
loterías por razones
morales, algunos gobiernos prohíben éste tipo de juegos,
pero con la aparición del Internet esta forma de juego
popular va prosperando, que comenzó en China y ayudo
financiar la "Gran Muralla".

Las probabilidades de ganar una lotería nacional se dan, y
por lo tanto sus compañeros de clase de colegio decidieron
organizar una pequeña lotería privada, con el sorteo cada
viernes. La lotería está basada en un estilo popular: un
estudiante que quiere apostar escoge C números distintos
de 1 a K y paga 1.00 Bs. (Las loterías tradicionales como la
lotería estadounidense utilizan C = 6 y K = 49).

El viernes durante el almuerzo C números (de 1 a K) son
extraídos. El estudiante cuya apuesta tiene el número más
grande de aciertos recibe la cantidad de las apuestas. Esta
cantidad es compartida en caso de empate y se acumulad a
la próxima semana si nadie adivina cualquiera de los
números extraídos.

Algunos de sus colegas no creen en las leyes de
probabilidad y desean que usted escriba un programa que
determine
los
números que menos salieron en sorteos anteriores, de
modo que ellos puedan apostar a aquellos números.

los números a escoger, considerando

Entrada
La entrada contiene varios casos de prueba. La primera
línea de un caso de prueba contiene tres números enteros
N, C y K que indica respectivamente el número de sorteos
que ya han pasado (1 N 10000), cuantos números
comprenden una apuesta (1 C 10) y el valor máximo de
los números que pueden ser escogidos en una apuesta (C <
K 100). Cada una de las N líneas siguientes contiene C
números enteros distintos Xi que indica los números
extraídos en cada sorteo anterior (1 Xi K; para1 i C).
Los valores finales de entrada se indica por N = C = K = 0.

4

PROBLEMAS RESUELTOS

La entrada se debe leer de standard input (teclado).

Salida
Para cada caso de prueba en la entrada su programa debe
escribir una línea de salida, conteniendo el juego de
números que han sido han salido la menor cantidad de
veces. Este juego debe ser impreso como una lista, en
orden creciente de números. Inserte un espacio en blanco
entre dos números consecutivos en la lista.

La salida debe ser standard output(pantalla).

Ejemplo de entrada
5 4 6
6 2 3 4
3 4 6 5
2 3 6 5
4 5 2 6
2 3 6 4
4 3 4
3 2 1
2 1 4
4 3 2
1 4 3
0