The Labyrinth of the Salvataur P64141


Statement
 

pdf   zip

thehtml

(You may consider jumping to the Input section.)

On a particularly hot day in the month of September of year of 20–, I received a letter from my old acquaintance Dr. —, Professor at the Monotechnical University. It was uncommon for him to resort to these means of communication, and the contents of the letter caused me even greater distress. After many years of suspicion fed by rumors and conversations he was not supposed to overhear, he claimed to have found proof of something of the utmost severity concerning our shared alma mater, and instated me to pay him a visit at his office as soon as possible so we could discuss the matter in private. The ominous feeling that the letter planted on me was nothing but multiplied when, guided by the janitor along the colored corridors of the department buildings, we opened the office only to find a toppled chair, drawers and cupboards open, books and papers scattered on the floor—and no sign of the Professor.

However, as soon as the janitor left to warn the corresponding authorities, I swiftly moved next to the desk and pressed the exact location my correspondent had confided to me in a previous encounter. An hidden drawer opened, and there I found a worn-out notebook with a leather cover and a red elastic band wrapped around it. I knew whoever had searched the office and was behind my colleague’s disappearance was certainly looking for this. A few hours later, in a shabby touristic apartment in a seaside neighborhood, I started reading the document, illuminated by candlelight and accompanied by the roar of waves in the sea and the shouts of shirtless drunkards in the street.

And then I found the proofs of the existence of the Salvataur, the monster the Professor has suspected lived in a labyrinth at the lowest levels of the university campus, and who fed on students that had failed to pass their degree’s first year. Among the multiple transcribed conversations, blurry photographs, and digressions from my confidant, one particular hand drawing caught my attention: painted in watercolor, the Salvataur stood haughty with its horns upright and a red glow in its eyes; blood dropping from its mouth, an obscure band’s name and a series of dates and locations readable on the black T-shirt in its hand.

However, I was extremely naive to believe my actions of the day had gone unnoticed. Shortly after I laid myself on bed to relieve the pain behind my eyes, the door opened violently. Following a brief fight in the dark, an impact on my head left me unconscious. When I regained awareness, I was in a poorly lit room from which multiple corridors spawned—a labyrinth. Aching and dizzy, I incorporated myself and approached the walls. I then half saw, half sensed with my fingertips, the etchings on the plaster. One reported “I hear the steps coming closer every minute”, whereas another student lamented “Now I can only beg the Salvataur to spare my life”, and a third one regretted “I wish I had asked to review that Algorithmics test’s grading”. The realization of my doom sank in: I fell to my knees, and started sobbing and hitting the writing with my fist, until pain and frustration made me collapse on the floor.

After a few minutes, I stood up and started to explore the labyrinth of the Salvataur: hopelessly, without the knowledge of which room that I entered would be my last…

Input

Input consists of several cases. Each case starts with the number of vertices 3 ≤ V ≤ 104 and edges 3 ≤ E ≤ 5V in the labyrinth’s graph, the number of vertices 3 ≤ R ≤ 1000 in the human’s route, and a real number, the sense of smell 0 ≤ S ≤ 1 of the Salvataur. Next come E pairs ui vi, one for each edge of the graph, which is undirected and connected. Finally come R vertices 0 ≤ ri < V describing the route of the human. Assume that the vertices are numbered from 0, that there are no repeated edges nor edges with ui = vi, that r0 = 0, and that for all 0 < i < R, either ri−1 = ri, or there is an edge between ri−1 and ri.

At time t = 0, the human is at vertex 0 and the Salvataur at V − 1. For t ≥ 1, they move in turns, starting with the human:

  • The human moves from ri−1 to ri (or stays at ri−1, if they are equal). If the Salvataur is at the destination vertex, the human gets caught (and presumably eaten).
  • The Salvataur then moves in the following way:
    • If it is in a neighboring vertex to where the human was (ri−1), it will have smelt him with probability S: in that case, it will move to ri−1.
    • Otherwise (i.e., if it was not in a neighboring vertex, or if it failed to smell the human), it will move uniformly at random to any of the neighbors of its current vertex. So, it never stays in the same location for two consecutive turns.
    In either case, if it enters the current vertex of the human (ri), it also captures him.

The input is such that the human has a non-zero probability of surviving after R−2 steps.

Output

For each case, print the probability that the Salvataur catches the human in the last round, given the information that it has not caught the human in any of its preceding moves. That probability must include the human moving to rR−1 and finding the Salvataur there, and also the Salvataur making its last move to rR−1. Print the probabilities rounded to a percentage with no decimal figures. The input cases have no precision issues.

Public test cases
  • Input

    3 3 6 1.0
    0 1 1 2 2 0
    0 1 2 0 1 2
    
    3 3 6 0.5
    0 1 1 2 2 0
    0 1 2 0 1 2
    
    3 3 6 0.0
    0 1 1 2 2 0
    0 1 2 0 1 2
    
    3 3 6 0.5
    0 1 1 2 2 0
    0 1 2 0 1 1
    
    3 3 6 0.5
    0 1 1 2 2 0
    0 1 2 0 1 0
    
    4 6 5 0.5
    0 1 0 2 0 3 1 2 1 3 2 3
    0 1 2 3 0
    
    4 6 5 0.0
    0 1 0 2 0 3 1 2 1 3 2 3
    0 1 2 3 0
    
    4 5 5 0.4
    0 1 0 2 0 3 1 2 2 3
    0 1 2 3 0
    
    4 5 5 0.0
    0 1 0 2 0 3 1 2 2 3
    0 1 2 3 0
    
    

    Output

    0%
    25%
    50%
    75%
    100%
    33%
    67%
    44%
    67%
    
  • Information
    Author
    Edgar Gonzalez
    Language
    English
    Official solutions
    C++
    User solutions
    C++