El tonel de amontillado P31675


Statement
 

pdf   zip

thehtml

Había yo soportado hasta donde me era posible las mil ofensas de que Fortunato me hacía objeto, pero cuando se atrevió a insultarme juré que me vengaría…Continuamos nuestro camino en busca del amontillado. Pasamos bajo una hilera de arcos muy bajos, descendimos, seguimos adelante y, luego de bajar otra vez, llegamos a una profunda cripta…Puse la última piedra en su sitio y la fijé con el mortero…¡Requiescat in pace!

Con la excusa de catar un tonel de amontillado, Montressor ha guiado al pobre Fortunato, borracho, a través de las catacumbas debajo del palacio de Montressor. Allí, en una cripta remota, Montressor ha emparedado a Fortunato en un nicho escondido. Ahora Montressor quiere retornar a la habitación en la que empezaron su ruta, pero ha olvidado el camino para llegar. Afortunadamente, tiene un mapa de las catacumbas que muestra las habitaciones y sus conexiones directas. (Tened en cuanta que algunos pasos son tan difíciles que puede ser posible pasar de una habitación u a otra v, pero no directamente de vuelta de v a u.) El mapa también muestra qué habitaciones tienen amontillado.

Montressor y Fortunato fueron desde una habitación inicial x a otra habitación y donde se encuentran ahora. Irónicamente, Montressor sabe que no hay ningún camino desde x a ninguna habitación con amontillado. También sabe que es posible llegar desde y de vuelta hasta x. Sin embargo, no es capaz de identificar cuál es x ni cuál es y en el mapa. Por favor, ayudadle calculando el número de combinaciones posibles para x e y que son consistentes con toda esta información.

Entrada

La entrada consiste en diversos casos, con el número de habitaciones n, un número c, y c ‍habitaciones diferentes con amontillado. Sigue un número m, y m pares diferentes u ⁠ ⁠ v (con uv) denotando que hay una conexión directa de u a v. Asumid 0 ≤ n ≤ 10000, 0 ≤ cn, y 0 ≤ m ≤ 10n. Las habitaciones se numeran entre 0 y n − 1.

Salida

Para cada caso, escribid su número de caso (en inglés, “Case”), seguido del número de combinaciones para x e y que son consistentes con la información que tiene Montressor.

Public test cases
  • Input

    5 1  2
    6    0 3  3 0  2 3  1 2  1 4  4 1
    8 0
    7    1 3  0 3  0 1  5 0  3 0  7 6  0 4
    

    Output

    Case #1: 2
    Case #2: 6
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++