SP3254 GUARD - Guard

蓝水保安公司专为客户的贵重物品提供安保服务。客户期望保安能够简单地转头就看见所有重要的物品，并且希望保安尽量靠近那些特别有价值的物品。上图展示了一个样例布局（暂时忽略三个黑色点）。各个位置被标记并赋予了价值。例如，在坐标 (0,8) 的 A 点，放置了一个价值为 4 的物品。像 G 这样处于价值为 0 的位置则没有任何贵重物品。直线表示走廊，出于简化考虑，走廊被建模为宽度为 0 的线段。位于数条走廊交点的保安可以看守交叉点上每个走廊上的物品。 如果蓝水被要求派遣 3 名保安，他们可能会选择在图中小黑点所示的位置驻守。其中一个保安位于标注为 (15.5, 6) 的地方。为便于模型计算，蓝水使用物品的价值乘以最近能够看见该物品的保安与其之间的距离，来表示物品的风险。即使有保安靠近某个拐角处的物品，但只要看不见，该保安就无法降低该物品的风险。 在图中，各物品的风险计算为：A: 4×5=20，C: 4×2.5=10，D: 2×0=0，等等。最大的风险发生在 H: 50×7.5=375 和 I: 50×7.5=375，因此最大风险为 375。对于这样的布局，无论 3 名保安怎么分配，最大风险都不可能低于 375。因此，这种布置方法实现了最大风险最小化。蓝水希望能够告知请求某一数量保安的客户，在特定布局下，这种最小化的最大风险是多大。

输入包含一到十六组数据，最后以一行仅有 0 结束。每行数据由空格分隔的若干标记组成。 每组数据的第一行包含三个整数 $p$、$c$ 和 $g$，分别表示标记点的数量、走廊的数量和需要布置的保安数。限制条件为 $1 < p < 12$，$0 < c < 12$，$0 < g < 5$。 接下来有 $p$ 组信息，每组由一个大写字母和三个非负整数 $L$、$x$、$y$、$v$ 组成，表示标签为 $L$ 的点 $(x, y)$ 位置上有一个价值为 $v$ 的物品。如果 $p$ 不超过 6，这些信息将在一行中给出；如果 $p$ 超过 6，从第七组开始的信息将换行。标签为从 A 开始的连续字母。所有数字都小于 1000，每个地点的坐标都是唯一的。$v$ 为 0 表示该位置没有有价值的物品。具有价值的地点的数量至少与保安的数量一样多。 每组数据最后一行有 $c$ 个字符串，每个字符串代表一条走廊。走廊字符串中的字母依次表示走廊上经过的点，包括走廊的起终点、与其他走廊的交点以及所有有价值物品的位置。数据集提供的所有点都位于至少一条走廊上。

每组数据输出一行。如果提供的保安数量不足以看守所有贵重物品，输出“too few guards”。否则，输出一个无符号数 $r$，保留两位小数。$r$ 是在所有可能的 $g$ 名保安布置方案中，对有价值物品的最大风险的最小值。 第一个示例数据集对应插图中的示例，接下来的三个示例只更改了保安的人数。

- $1 < p < 12$ - $0 < c < 12$ - $0 < g < 5$ **本翻译由 AI 自动生成**