Ir al contenido (saltar navegación)

Trampas en la competición

Tiempo máximo: 1,000-4,000 sMemoria máxima: 65536 KiB
Reglas de la competición

Me he apuntado a una competición de programación bastante divertida. En lugar de durar un único día, la competición abarca varias semanas con un concurso diario, de forma que la clasificación general se construye agregando las clasificaciones de cada uno de los días. Más que un concurso es una carrera de fondo, porque los concursos diarios son a horas distintas (¡incluso de madrugada!), por lo que no solo se pone a prueba la algoritmia sino también el aguante físico. Tanto es así que no se está obligado a participar todos los días; los días que no participas simplemente no puntúas.

El primer día todo fue bien, pero a partir del segundo día me dio la sensación de que había gente haciendo trampas. Lamentablemente, algunos participantes habían conseguido con antelación los problemas y los tenían preparados y resueltos antes de empezar, así que en cuanto comenzaba el concurso de ese día lo enviaban. Es una pena que haya gente así; a los que no tenemos acceso con antelación a los problemas nos desmotiva ver a gente resolviéndolos en unos pocos segundos. Tampoco alcanzo a entender qué satisfacción hay en el asunto, si no hay premios y únicamente se participa por la diversión… Además, no me quiero imaginar lo mal que deben sentirse los organizadores viendo que todo su esfuerzo montando el concurso queda empañado por unos cuantos tramposos. Espero que no les desmotive a ellos también y haya más ediciones porque, quitando esta pega, la competición, las reglas y los problemas que aparecen son muy divertidos.

Quiero demostrar que, efectivamente, esas trampas están teniendo lugar (al fin y al cabo los tramposos pueden defenderse diciendo que son tan brillantes que resuelven los problemas muy rápido). El único argumento que tengo es comprobar cómo evolucionan las posiciones en los distintos días; como la gente no participa todos los días y los tramposos no siempre consiguen los problemas con antelación, creo que seré capaz. Mi método para buscar las trampas parte de una serie de premisas que considero que se cumplen siempre y cuando todos seamos honestos:

  • El resultado de la competición es producto exclusivamente de la habilidad de cada participante y no influye la suerte ni el tipo concreto de algoritmo que pone a prueba cada problema.
  • Cada participante tiene un nivel de destreza que no cambia durante toda la competición.
  • Si un participante tiene un nivel de destreza mayor que otro, quedará por encima en la clasificación en todas las competiciones en las que ambos participen.
  • De la misma forma, si el nivel de destreza de dos personas es la misma, quedarán empatados siempre.

No tengo acceso a las clasificaciones completas de todos los días, pero sí conozco los resultados comparados de algunos participantes en distintos días. Con eso espero poder demostrar que las premisas anteriores no se cumplen y que, por tanto, alguno está haciendo trampas.

Entrada

La entrada está compuesta de distintos casos de prueba. La primera línea de cada caso tiene dos números: n (entre 1 y 100.000) indicando el número de participantes y c (hasta 300.000) con el número total de resultados comparados entre participantes.

A continuación aparecen c líneas con información extraída de las clasificaciones diarias con un formato fijo: dos números a y b (entre 1 y n) separados del símbolo <, = o > que indican que a fue peor, igual o mejor que b respectivamente en alguna de las competiciones diarias.

Salida

Por cada caso de prueba se escribirá una única línea. Si con los resultados de los que disponemos podemos asegurar que alguien ha hecho trampa, aparecerá TRAMPAS; si los resultados no lo demuestran (aunque quizá las haya…) se indicará DESCONFIADO.

Entrada de ejemplo

4 2
1 < 2
1 > 2
5 5
3 < 4
3 = 2
2 < 5
4 < 5
3 = 2

Salida de ejemplo

TRAMPAS
DESCONFIADO