Uama2009a

Sexto Concurso Local de Programación ACM ICPC
Universidad Autónoma Metropolitana
Examen eliminatorio, 1 a 6 de octubre de 2009
Instrucciones: Abajo encontrarás los enunciados de cinco problemas. Cada problema tiene un valor entre 20 y
60 puntos, los cuales se obtendrán de las salidas que entregue tu programa para cada una de 10 entradas distintas.
Todos los programas se evaluarán en Linux. Que tuprograma funcione con el ejemplo no quiere decir que
funcionará siempre.
Para cada problema que resuelvas deberás enviar por correo electrónico el código fuente de un programa a la
dirección uam09acm@gmail.com indicando claramente tu nombre completo. De preferencia envía todos tus
códigos en un correo. El nombre de los archivos que envíes debe ser de la forma xxx.zzz, donde xxx es el
nombre delproblema y zzz es la extensión, según el lenguaje que hayas usado. Si así lo deseas, puedes resolver
cada problema en un lenguaje distinto. Tu programa deberá leer e imprimir exactamente los datos que se indican
(ni más ni menos) usando la entrada y la salida estándar. En particular, tu programa no deberá borrar la pantalla,
escribir ningún tipo de letrero adicional, usar la biblioteca conio, etc.Quienes programen en C deberán usar gcc,
quienes programen en C++ deberán usar g++ y quienes programen en Java deberán usar gcj como sigue:
gcc nombre_del_fuente.c -o nombre_del_ejecutable -lm
g++ nombre_del_fuente.cpp -o nombre_del_ejecutable -lm
gcj nombre_del_fuente.java -o nombre_del_ejecutable
Deberás enviar tus códigos fuente a más tardar el 6 de octubre de 2009 a las 22:00.
Problema 1:Secuencia creciente máxima (20 puntos)
Código fuente: scm.c, scm.cpp, scm.java
Sea n un entero positivo y sea a1, a2, ..., an una secuencia de n enteros positivos. Sean h y k dos enteros con 1 ≤ h
≤ k ≤ n. Decimos que ah, ah+1, ..., ak es una secuencia creciente si ah < ah+1 < ... < ak y decimos que es máxima si
no es parte de otra secuencia creciente más larga. Por ejemplo, si n = 7 y a = (3, 1, 4,1, 5, 9, 2) entonces (1, 5) es
una secuencia creciente, pero no es máxima porque es parte de (1, 5, 9). Escribe un programa que encuentre la
longitud s de la secuencia creciente máxima más larga de todas y la posición p donde inicia.
Entrada: Un número entero n con 1 ≤ n ≤ 1000 seguido de n números enteros a1, a2, ..., an separados por
espacios y en el intervalo de 1 a 1,000,000.
Salida: Un númeroentero s y un número entero p.
Evaluación: 1 punto por el valor correcto de s y 1 punto si p es correcto.
Ejemplo de entrada
7
3 1 4 1 5 9 2

Ejemplo de salida
3 4

Problema 2: Área de la intersección de dos rectángulos (30 puntos)
Código fuente: air.c, air.cpp, air.java
Considere que tiene dos rectángulos con lados paralelos a los ejes de coordenadas: uno con vértices opuestos (u,
v) y (x, z) yel otro con vértices opuestos (p, q) y (r, s). Escribe un programa que calcule el área a de la

intersección de esos dos rectángulos. Por ejemplo, si un rectángulo tiene vértices opuestos (3, 1) y (1, 4) y el otro
tiene vértices opuestos (2, 7) y (1, 2) entonces su intersección tiene área a = 2.
Entrada: Ocho números enteros u, v, x, z, p, q, r y s separados por espacios y todos ellos en elintervalo de 0 a
1,000,000.
Salida: Un número entero a.
Evaluación: 3 puntos por el valor correcto de a.
Ejemplo de entrada
3 1 1 4 2 7 1 2

Ejemplo de salida
2

Problema 3: Boletos por besos (40 puntos)
Código fuente: bpb.c, bpb.cpp, bpb.java
Para ir hacia su escuela, Juan aborda un camión. Cuando Juan sube al camión y deposita las monedas
en la alcancía, el conductor le da un boleto con un número deserie consecutivo, el cual generalmente
llega a la basura. Sin embargo, un día el se entera de algo interesante. Si la suma de los dígitos de
dicho boleto es 21, él lo puede cambiar con quien quiera por un beso. Juan quiere conseguir muchos
besos de la persona que está enamorado y ella ha aceptado dárselos a cambio de dichos boletos, pero
no es tan fácil conseguirlos. Juan ha decidido que si el...