随机程序

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file backtoKR.in Output file backtoKR.out

【题目描述】

你一定听说过Kernighan和Ritchie,他们是《C程序设计语言》的作者。当在C语言中编程时,我们使用不同的控制语句和循环。例如,if-then-else(原文如此——译者注),for,do-while等等。考虑如下伪代码:


   //execution starts here
   do {
      U;
      V;
   } while(condition);
   W;

在上述代码中,每个分支都有一定的执行条件。这一代码可以用流程图表示如下:


对每个节点,令其转到任意后继的概率相等。因此,在上面的代码中,U执行的期望次数是2.在这个问题中,给出这样的一个流程图,请你找出每个节点的期望执行次数。

【输入格式】

输入包含至多100组数据。

每组数据的第1行是一个正整数n(1<=n<=100)。n是流程图中的节点个数。节点被从1到n编号,并且总是从1开始执行。

下面有若干行,每行2个正整数:start和end,意味着执行完start后可以转到end。以2个0结束。

下面一行有一个正整数q(1<=q<=100),描述询问个数。

接下来的q行,每行一个正整数x,意味着询问节点x的期望执行次数。

输入文件以n=0结束。

【输出格式】

对第i组数据:

先输出一行"Case #i:"。

接下来输出q行,每行1个实数,表示该查询对应的期望次数。保留三位小数。某个节点有可能被永远执行(例如,一个无穷的for循环)。对于这种情况,输出"infinity"。

具体格式见样例。

【样例输入】

3

1 2

2 3

2 1

0 0

3

1

2

3

3

1 2

2 3

3 1

0 0

3

3

2

1

0

【样例输出】

Case #1:

2.000

2.000

1.000

Case #2:

infinity

infinity

infinity

【提示】

使用计算机中的“保留3位小数”指令。假设你的计算机能正确进行舍入。

【来源】

UVa10828 Back to Kernighan-Ritchie

刘汝佳,《算法竞赛入门经典训练指南》表2-12

Problem setter: Mohammad Sajjad Hossain

Special Thanks: Shahriar Manzoor