第2天试题.docVIP

Frogger l】 青蛙Freddy正坐在湖中间的一块石头上，突然他看见青蛙Fiona正坐在另一块石头上。 Freddy要去拜访Fiona，但湖水很脏，他准备跳过去拜访Fiona，而不是游过去。然而Freddy不可能一跳就跳到Fiona所在的石头上。Freddy要通过一系列的跳跃，先跳到其他石头上，然后再从其他石头上跳到Fiona那里。 Freddy所在的石头， Fiona所在的石头和其他的石头都在湖中。为了实现一系列的跳跃，一只青蛙的跳跃范围显然至少是跳跃序列中的最远的一次跳跃。 青蛙所在两块石头之间的距离（Frog Distance，被称为最短距离）被定义为在这两块石头之间所有可能的路径中最大边长的最小值。给出Freddy所在的石头，Fiona所在的石头和湖中其他的石头的坐标，请计算Freddy至Fiona的所有路径中最大边长的最小值。 输入：测试用例用一空行标志结束，以0表示输入结束。输入：输入包括一个或多个测试用例。每个测试用例第1行给出湖中的石头总数n(2≤n≤200)。后面的n行每行给出两个整数xi，yi (0≤xi，yi≤1000)，表示石头i的坐标。石头1是Freddy所在的石头，石头2是Fiona所在的石头，其余n-2块石头空着。每个 输出：对每个测试用例，输出一行“Scenario #x”和一行“Frog Distance = y”，x是测试用例编号，（起始为1），y是一个实数，保留小数3位。每个测试用例后加一行。 试题来源：Ulm Local 1997 在线测试：POJ2253，ZOJ 1942，UVA 534 Arbitrage 】 套汇是利用货币交换比率的差异将一个单位的货币转换为多于一个单位的相同的货币。例如，假设1美元买0.5英镑，1英镑买10.0法国法郎，1个法国法郎买0.21美元。这样，通过货币的兑换，1个聪明的商人可以从开始的1美元，买到0.5*10.0*0.21=1.05美元，获利5%。 请你写一个程序，由货币兑换比率表为输入，确定套汇是否可行。 输入：输入包括一个或多个测试用例。在每个测试用例第一行是一个整数n（1≤n≤30），表示不同的货币数目。在后面的n行中，每行给出了一种货币的种类。在最后的m行中，每行给出源货币名ci，一个实数rij表示从ci到cj的兑换比率，目标货币名cj。没有出现在列表中的兑换是不能进行交换的。 输出：对于每个测试用例，输出一行说明套汇是可行的或者是不可行的，格式分别为“Case case: Yes”，或者Case case: No。 注： 试题来源：Ulm Local 1996 在线测试：POJ 2240，ZOJ 1092，UVA 436 Toll】 水手辛巴德（Sindbad）把66只银汤匙出售给了撒马尔罕（Samarkand）的苏丹（Sultan）。出售相当容易，但运货十分复杂。这些物品要在陆路上转运，通过若干个城镇和乡村。而每个城镇和乡村都要收取过关费。没有交费不准离开。一个村庄的过关费是1个单位的货物，而一座城镇的过关费是每20件单位的货物收取1个单位的货物。例如，你带了70个单位的货物进入一个城镇，则你必须缴纳4个单位的货物。城镇和村庄位于无法通行山岩，沼泽和河流之间，所以你根本无法避免（如图）。 预测在每个村庄或城镇收取的费用很简单，但要找到最佳路线（最便宜的路线）则是一个真正的挑战。最佳路线取决于运送货物的单位数量。货物的单位数量在20以内，村庄和城镇收取的费用是相同的。但是对于单位数量较大的货物，就要避免通过城镇，可以通过比较多的村庄，如下图所示。 请编写一个程序来解决辛巴德的问题。给出要运送到某个城镇或村庄的货物的单位数量和一张路线地图，程序必须确定通过最廉价的旅程在开始的时候需要带的货物的单位数量的总数。 输入：输入包含若干个测试用例。每个测试用例由两部分组成：路线地图，然后是有关运送货物的细节。 路线地图的第一行给出一个整数n，表示在地图中路线的数量(0≤n)。后面的n行每行有两个字母，表示一条路的两个端点。大写字母表示城镇，小写字母表示村庄，两个方向中的任何一个方向都可以行走。在路线地图后给出一行，有关运送货物的细节，这一行有3个整数：整数p ( 0 p≤1000) 要运送到目的地的货物的单位数量，一个表示开始位置的字母，一个表示要送达的目的地位置的字母。要求通过这样的路线地图使得这样的货物数量可以被送达。 在最后一个测试用例后，给出一行，包含一个数字-1。 输出：对每个测试用例输出一行，给出测试用例编号和在出发的时候要带的货物的单位数量。 试题来源：ACM World Finals - Beverly Hills - 2002/2003 在线测试：UVA 2730 Minimum