Problema de la Olimpiada de Informatica

[rAjIv]

Encontre unos problemas de la olimpiada internacional de informatica, y encuentro confusa la solucion de este problema, espero que alguien me ayude presentando el programa completo .. el objetivo es hacer un programa en C ó C++ cumpliendo con las indicaciones que te presentan

INTRODUCCIÓN

En una tienda de cajas organizan un concurso entre sus clientes. El concurso consta en lo siguiente:
Se cuenta con varias cajas de diferentes tamaños. El ganador del concurso será quien, metiendo unas cajas en otras, logre meter el mayor número de cajas en una sola pila. Para poder meter una caja en otra, su tamaño debe de ser menor.

Así, una caja puede contener dentro de ella varias cajas, la tercera caja deberá ser más pequeña que la segunda, la cuarta más chica que la tercera, etc.

Las cajas son de forma cilíndrica, por lo que tienen cierto radio y cierta altura. Para que una caja pueda entrar en otra, debe ser más pequeña tanto en el radio como en la altura.

DESCRIPCION DEL PROBLEMA

Deberás realizar un programa que dada la lista de los tamaños de las cajas, dé el número máximo de cajas que se pueden juntar en una pila.

ENTRADA

Tu programa deberá leer del archivo de entrada INPUT.TXT , de la primera línea, el número N de cajas en la línea (1< ó = N < ó = 500). En las siguientes N líneas las dimensiones de cada una de las cajas, el radio R y la altura H, respectivamente (1< ó = N, R < ó = 1000).

SALIDA

Deberás escribir en el archivo de salida OUTPUT.TXT, en la primera línea el número C máximo de cajas, apilables en una sola.

EJEMPLO

INPUT.TXT
6
4 9
10 4
5 5
1 1
3 8
2 3

OUTPUT.TXT
5

[blackwind]

Una vez participe en un concurso de ese tipo.
Era de la ACM, algunos eran problemas realmente dificiles.

Recuerdo que de 5 problemas, resolvi 3, y el 4to, que segun yo lo hice bien, nunca me lo aceptaron. El caso base lo resolvia, y probe con otros casos, y tambien lo resolvia, y me lo rechazaron. Le pregunte a los jueces por que, pero nunca me dijeron... realmente me frusto eso, porque ya con eso pasaba a la siguiente ronda.

Si a alguien le gustaria ponerse a prueba, aqui hay una pagina con muchos problemas, algunos vienen con nivel de dificultad:
http://acm.uva.es/problemset/

Pero bueno, volviendo al tema, el problema de la caja es bastante sencilllo, solamente tienes que ordenar tu arreglo de tamaños e ir acomodando de mayor a menor...

saludos,

[Instru]

SI.. recuerdo esos problemas. Yo participe en la olimpiada mexicana de informatica que despues seguia la internacional.

Nunca llegue a la internacional, pero si tuve la oportunidad de tener esos problemas en mis manos.

El que mas se me dificulto fue el de la calculadora de polinomios que despues descubri que era pan comido usando el binomio de newton.

Aun asi seria interesant resolver un dia dentro del foro esos problemas.

Saludos

[_Lucifer_]

Aun asi seria interesant resolver un dia dentro del foro esos problemas.

Tomandote la palabra...creo que el problema esta mal planteado o yo no lo entendi bien, fijense esto:

Las cajas son de forma cilíndrica, por lo que tienen cierto radio y cierta altura. Para que una caja pueda entrar en otra, debe ser más pequeña tanto en el radio como en la altura.

Si simplemente las ordenamos de mayos a menor de acuerdo al radio quedaria:
10 4
5 5
4 9
3 8
2 3
1 1

De acuerdo al enunciado no puedo meter la caja de R=5 ni la de R=9 en la de R=10. En dicho caso quedaria:
4 9
3 8
2 3
1 1
Si simplemente es colocar una dentro de la ota sin importar la altura pues la primera solucion estaria perfecta.

Sospecho que posiblemente omiti algun detalle o me equivoque en mi solucion, si hay alguien que me pueda corregir se lo agradeceria mucho.

Saludos

[blackwind]

Que tal,

No omitiste nada, el problema esta bien planteado y tu solucion es la correcta. Uno de los detalles que tienen los problemas de ese tipo, es que no te dicen todos los detalles explicitamente como ese que tu mencionas.

Es para darle un poco de "sabor" jejeje

saludos,

[_Lucifer_]

Entonces lo que esta mal es la solucion que plantean alli, porque segun ellos eso da 5 y con lo que yo puse eso da 4 o 3 si no cuentas la primera caja.

Saludos

[blackwind]

no me habia fijado en eso jeje.
Es posible que rAjIv haya escrito mal ya sea el input o el output....

[_Lucifer_]

Por eso , yo pense que tal vez habia omitido alguna cosa o se me paso algo por alto. Pero Creo que mi solucion esta bien, asi que supongo que copio mal la solucion o tal vez copio mal alguna de las entradas.

Saludos