Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
47 - ACM ICPC Regional 2005, Hangzhou - 1006
Forwards

Time Limit: 5 Seconds      Memory Limit: 32768 KB

THE 30th ACM/ICPC ASIA REGIONAL 2005 HANGZHOU SITE

Onsite Contest Session

Problem F: Forwards

Modern applications are usually built upon a certain framework to handle a group of common tasks. Java web applications can utilize the Apache Struts framework to implement the controller logic. The controller receives user requests and dispatches them to appropriate actions. Once the action finishes handling the request it can choose to forward the request to either another action for further handling or to a server page to render the user interface.

For instance if the user hits the path "/submitOrder" with the necessary information, the controller will first locate the action configured to serve that path and forward the request to it. The action will determine the validity of the request, and choose within one of the three forwards "success", "failure" or "login". These forwards may map to different paths, for instance, "success" to "/processCreditCard", which is handled by another action to initiate the credit card transaction, and "login" to "/login.jsp" to require the user to log into the website before submitting the order.

Due to the time constraint of the contest, we are not planning to cope with any serious business logic. Instead we have created a random action that will send the request to one of configured forwards with equal probability. The request will be rendered once it reaches a server page. Given a set of action configuration and a request path, we need to know which server page we are most likely to reach.

Input Description

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

Each test case starts with an integer N (5 <= N < 40,000) and a request path. The following N lines contain the XML segments for the action configuration.

One or more elements will reside in an document, with each action containing one or more elements. The format of the input will accurately follow the samples. To make it simple, each path attribute will consist of lower case English letters only.

The number of actions in a test case will not exceed 200, nor will the forwards in an action exceed 200. A path is a server page if and only if it is not configured to any actions. It is guaranteed that multiple actions will never serve the same path, and that the request path will also be served by one of the actions. Each action will have at least one forward that is a server page.

Output Description

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each test case, print the sentence "Most likely to see P with the probability of Q%." on the first line, where P is the path of the server page that is most likely to be rendered, and Q is the probability in percentage format. Print the sentence "These page(s) are expected to go through M forwards. " on the second line, where M is the expected number of forwards it goes through in order to see the page.

If multiple pages with maximum P exist, choose the ones with minimum M. If there are still multiple pages satisfy the requirement, print them in lexicographical order, separated with a single space. P and M should be accurate up to eight decimal places.

Sample Input

2

6 a
<action-mappings>
  <action path="a">
    <forward path="b" />
    <forward path="c" />
  </action>
</action-mappings>

13 a
<action-mappings>
  <action path="a">
    <forward path="b" />
    <forward path="c" />
  </action>
  <action path="b">
    <forward path="c" />
    <forward path="d" />
  </action>
  <action path="d">
    <forward path="e" />
  </action>
</action-mappings>

Sample Output

Case 1:
Most likely to see b c with the probability of 50.00000000%.
These page(s) are expected to go through 1.00000000 forwards.

Case 2:
Most likely to see c with the probability of 75.00000000%.
These page(s) are expected to go through 1.33333333 forwards.

Submit    Status