Tarjetas.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB

Los azucareros del centro poseen N tarjetas rectangulares. Las tarjetas están dispuestas en fila una al lado de la otra y numeradas según el orden con números del 1 al N. La tarjeta con el número i tiene las dimensiones a_i y b_i en sus lados. Podemos colocar una tarjeta encima de la anterior de la fila si se puede colocar de forma que tenga lados paralelos a la anterior (posiblemente podamos hacer una rotación) y no se salga de las dimensiones de la anterior. Por ejemplo, una tarjeta de 3x4 puede colocarse sobre una de 4x5 ó 4x3, pero no sobre una de 3x3.

Escriba un programa que encuentre el número de tarjetas de la secuencia más larga de tarjetas colocadas consecutivamente, de forma que cada tarjeta de esa secuencia (excepto la primera) pueda colocarse encima de la tarjeta anterior.

Entrada

En la primera línea de la entrada estándar, introduzca un único número entero N: el número de tarjetas. En la segunda línea, introduzca N pares de números enteros a_i y b_i, correspondientes a los tamaños de las tarjetas ordenadas sucesivamente. Todos los números de la entrada están separados por espacio.

Salida

En la salida estándar, el programa debe mostrar un número entero igual al número buscado.

Restricciones

  • 1 < N < 100 000.
  • tamaño de cada tarjeta \leq 1 000 000.

Ejemplo de Entrada

6  
3 4 5 3 3 3 2 3 3 2 7 7

Ejemplo de Salida

4

Explicación

En el orden en que están dispuestas en la fila, tienen los tamaños 3x4, 5x3, 3x3, 2x3, 3x2 y 7x7 respectivamente. La secuencia deseada más larga de tarjetas colocados consecutivamente según la condición del problema es la secuencia de los 4 tarjetas de tamaño: 5x3, 3x3, 2x3, 3x2 y por lo tanto su programa para esta prueba debe dar como resultado 4.


Comments


  • -1
    Jose_Ernesto  commented on Dec. 23, 2023, 2:47 a.m.

    porque la secuencia mas larga empieza en la targeta 5x3


  • -1
    Julio_15  commented on Dec. 22, 2023, 11:20 p.m.

    Porque en el ej: 3x4 no se incluye en la secuencia??