The cask of amontillado P31675


pdf   zip


The thousand injuries of Fortunato I had borne as I best could; but when he ventured upon insult, I vowed revenge…We continued our route in search of the amontillado. We passed through a range of low arches, descended, passed on, and descending again, arrived at a deep crypt…
I forced the last stone into its position; I plastered it up…In pace requiescat!

With the excuse of sampling a cask of amontillado, Montressor has guided poor drunken Fortunato through the catacombs under Montressor’s palace. There, in a very remote crypt, Montressor has immured Fortunato inside a hidden niche. Now Montressor wants to return to the chamber where they started their route, but he has forgotten the way to get there. Fortunatoly, Montressor has a map of the catacombs, which shows all the chambers and their direct connections. (Note that some steps are so difficult that it may be possible to pass from one chamber u to another v, but not directly back from v to u.) The map also shows which chambers contain amontillado.

Montressor and Fortunato went from a starting chamber x to another chamber y where they are now. Ironically, Montressor knows that there is no path from x to any chamber with amontillado. Montressor also knows that it is possible to go from y back to x. However, he cannot identify which is x nor which is y in the map. Please help him by computing the number of possible combinations for x and y that are consistent with all this information.


Input consists of several cases. Each one begins with the number of chambers n, a number c, and c different chambers that contain amontillado. Follows a number m, and m different pairs u   v (with uv) denoting that there is a direct connection from u to v. Assume 0 ≤ n ≤ 10000, 0 ≤ cn, and 0 ≤ m ≤ 10n. The chambers are numbered from 0 to n − 1.


For every case, print its number, followed by the number of combinations for x and y that are consistent with Montressor’s knowledge.

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


    Case #1: 2
    Case #2: 6
  • Information
    Salvador Roura
    Other languages
    Official solutions
    User solutions
    Sisè Concurs de Programació de la UPC - Final