Clasificando las Vacas


Submit solution

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

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

Cada una de las N vacas del Granjero Juan (1 \leq N \leq 1000) produce leche con una velocidad positiva diferente, y GJ quisiera ordenar sus vacas de acuerdo a estas velocidades de productora más rápida de leche a la menos rápida.

GJ ya ha comparado la velocidad de producción de leche para M (1 \leq M \leq 10 000) pares de vacas. Por favor ayúdelo a determinar el valor mínimo de C tal que el Granjero Juan será capaz de deducir el orden correcto de todas las N vacas usando solo C pares adicionales de comparaciones.

Entrada

• Línea 1: Dos enteros separados por espacio: N y M.

• Líneas 2…M+1: Dos enteros separados por espacio, respectivamente: X y Y. Ambos X y Y están en el rango 1...N y describen una comparación donde la vaca X fue clasificada mayor que la vaca Y.

Ejemplo de Entrada

5 5
2 1
1 5
2 3
1 4
3 4

Detalles de la Entrada

GJ está comparando 5 vacas y ya ha determinado que vaca 2 > vaca 1, vaca 1 > vaca 5, vaca 2 > vaca 3, vaca 1 > vaca 4, y vaca 3 > vaca 4 (donde la notación ‘>’ quiere decir “produce leche más rápidamente”).

Salida

• Línea 1: Un solo entero que es el valor mínimo de C.

Ejemplo de Salida

3

Detalles de la Salida

De la información en los 5 resultados de prueba, el Granjero Juan sabe que desde vaca 2 > vaca 1 > vaca 5 y vaca 2 > vaca 3 > vaca 4, vaca 2 tiene el rango más alto. Sin embargo, él necesita saber si vaca 1 > vaca 3 para determinar la vaca con el segundo rango más alto. También, él necesitará una pregunta más para determinar el orden entre vaca 4 y vaca 5. Después de eso, él necesita saber si vaca 5 > vaca 3 y si vaca 1 tiene rango más alto que vaca 3. Él tendrá que hacer tres preguntas en orden para estar seguro que él tiene las clasificaciones: “¿Es vaca 1 > vaca 3?, ¿Es vaca 4 < vaca 5?, ¿Es vaca 5 > vaca 3?”


Comments


  • 0
    Brayan080808  commented on Sept. 1, 2022, 7:14 p.m.

    Cómo puedo solucionar el error de segmentation fault?