Time Limit:
Memory Limit:
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的到加上大小王的共张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：
第一行包含用空格隔开的个正整数，表示手牌的组数以及每组手牌的张数。
接下来组数据，每组数据行，每行一个非负整数对，表示一张牌，其中表示牌的数码，表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，表示数码，表示数码，表示数码；黑桃、红心、梅花、方片分别用来表示；小王的表示方法为，大王的表示方法为。
共行，每行一个整数，表示打光第组手牌的最少次数。
Time Limit:
Memory Limit:
Recently, a number of gold mines have been discovered in Zorroming State. To protect this treasure, we must transport this gold to the storehouses as quickly as possible. Suppose that the Zorroming State consists of N towns and there are M bidirectional roads among these towns. The gold mines are only discovered in parts of the towns, while the storehouses are also owned by parts of the towns. The storage of the gold mine and storehouse for each town is finite. The truck drivers in the Zorroming State are famous for their bad temper that they would not like to drive all the time and they need a bar and an inn available in the trip for a good rest. Therefore, your task is to minimize the maximum adjacent distance among all the possible transport routes on the condition that all the gold is safely transported to the storehouses.
The input contains several test cases. For each case, the first line is integer . The second line is integers associated with the storage of the gold mine in every towns .The third line is also integers associated with the storage of the storehouses in every towns .Next is integer .Then M lines follow. Each line is three integers , and , means that there is a road between and for distance of . means end of the input.
For each case, output the minimum of the maximum adjacent distance on the condition that all the gold has been transported to the storehouses or “No Solution”.
David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.
After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.
His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can’t share a lifter. Channels can intersect safely and no three villages are on the same line.
As King David’s prime scientist and programmer, you are asked to find out the best solution to build the channels.
There are several test cases. Each test case starts with a line containing a number , which is the number of villages. Each of the following lines contains three integers, , and . is the position of the village and is the altitude. The first village is the capital. A test case with ends the input, and should not be processed.
For each test case, output one line containing a decimal number, which is the minimum ratio of overall cost of the channels to the total length. This number should be rounded three digits after the decimal point.
年，在银河系的某星球上，军团和军团正在激烈地作战。在战斗的某一阶段，军团一共派遣了个巨型机器人进攻军团的阵地，其中第个巨型机器人的装甲值为。当一个巨型机器人的装甲值减少到或者以下时，这个巨型机器人就被摧毁了。军团有个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。军团看到自己的巨型机器人被军团一个一个消灭，他们急需下达更多的指令。为了这个目标，军团需要知道军团最少需要用多长时间才能将军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。
第一行，两个整数，、。
第二行，个整数，、 。
第三行，个整数，、 。
接下来的行，每行个整数，这些整数均为或者。这部分中的第行的第个整数为表示第个激光武器不可以攻击第个巨型机器人，为表示第个激光武器可以攻击第个巨型机器人。
一行，一个实数，表示军团要摧毁军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过即视为正确。
聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： 对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。 例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。
第一行包含两个整数和(,)，分别代表了野人居住点的数量和部落的数量。
接下来行，每行包含两个正整数，描述了一个居住点的坐标()
输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。
同一时刻有位车主带着他们的爱车来到了汽车维修中心。维修中心共有位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
第一行有两个，表示技术人员数与顾客数。 接下来行，每行个整数。第行第个数表示第位技术人
员维修第辆车需要用的时间。
最小平均等待时间，答案精确到小数点后位。
Zero and One are good friends who always have fun with each other.
This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give One an tree and every node in this tree has a value. Then, Zero will ask One a series of queries. Each query contains three parameters: , , which mean that he want to know the maximum value produced by each value on the path from node to node (include node , node ). Unfortunately, One has no idea in this question. So he need you to solve it.
There are several test cases and the cases end with . For each case:
The first line contains two integers and , which are the amount of tree’s nodes and queries, respectively.
The second line contains integers and is the value on the node.
The next lines contains two integers , which means there is an connection between and .
The next m lines contains three integers , which are the parameters of Zero’s query.
For each query, output the answer.
图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的），并且该节点的直接邻居也发生同样的变化。开始的时候，所有的指示灯都是熄灭的。
请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。
输入文件有多组数据。
输入第一行包含一个整数，表示树的节点数目。每个节点的编号从到。
输入接下来的行，每一行包含两个整数，，表示节点和之间有一条无向边。
当输入为时，表示输入结束。
对于每组数据，输出最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。
Time Limit:
Memory Limit:
《猪国杀》是一种多猪牌类回合制游戏，一共有三种角色：主猪，忠猪，反猪。
每局游戏主猪有且只有一只，忠猪和反猪可以有多只，每只猪扮演一种角色。
·主猪（MP）：自己存活的情况下消灭所有的反猪。
·忠猪（ZP）：不惜一切保护主猪，胜利条件与主猪相同。
·反猪（FP）：杀死主猪。
·游戏开始时候，每个玩家手里都会有4张牌，且体力上限和初始体力都是4。
·开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从1,2,3..n,1..的顺序）依次行动。
·每个玩家自己的回合可以分为2个阶段：
·摸牌阶段：
·从牌堆顶部摸两张牌，依次放到手牌的最右边。
·出牌阶段：
·你可以使用0张到任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。
·当然，要满足如下规则：
·1.如果没有猪哥连弩，每个出牌阶段只能使用一次“杀”来攻击。
·2.任何牌被使用后被弃置（武器是装备上）。
·被弃置的牌以后都不能再用，即与游戏无关。
·每张手牌用一个字母表示，字母代表牌的种类。
·基本牌：
『桃(P)』：
·在自己的回合内，如果自己的体力值不等于体力上限，那么使用一个桃可以为自己补充一点体力，否则不能使用桃。
·桃只能对自己使用。
·在自己的回合外，如果自己的血变为0或者更低，那么也可以使用。
『杀(K)』：
·在自己的回合内，对攻击范围内除自己以外的一名角色使用。
·如果没有被『闪』抵消，则造成1点伤害。无论有无武器，杀的攻击范围都是1。
『闪(D)』：
·当你受到杀的攻击时，可以弃置一张闪来抵消杀的效果。
·锦囊牌：
『决斗(F)』：
·出牌阶段，对除自己以外任意一名角色使用，由目标角色先开始，自己和目标角色轮流弃置一张杀，首先没有杀可弃的一方受到1点伤害，另一方视为此伤害的来源。
『南猪入侵(N)』：
·出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置一张杀，否则受到1点伤害。
『万箭齐发(W)』：
·和南猪入侵类似，不过要弃置的不是杀而是闪。
『无懈可击(J)』：
·在目标锦囊生效前抵消其效果。
·每次有一张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会。
·效果：
·用于决斗时，决斗无效并弃置。
·用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对一个角色产生效果）。
·用于无懈可击时，成为目标的无懈可击被无效。
·装备牌：
『猪哥连弩(Z)』：
·武器，攻击范围1，出牌阶段你可以使用任意张杀。
·同一时刻最多只能装一个武器。
·如果先前已经有了一把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器。
·伤害来源：
·杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪。
·决斗的伤害来源如上。
·距离：
·两只猪的距离定义为沿着逆时针方向间隔的猪数＋1。即初始时1和2的距离为1，但是2和1的距离就是n-1。
·注意一个角色的死亡会导致一些猪距离的改变；
·玩家死亡：
·如果该玩家的体力降到0或者更低，并且自己手中没有足够的桃使得自己的体力值回到1，那么就死亡了。
·死亡后所有的牌（装备区，手牌区）被弃置。
·奖励与惩罚：
·反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸三张牌。
·忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置。
·注意，一旦达成胜利条件，游戏立刻结束，因此即使会摸3张牌或者还有牌可以用也不用执行了。
·献殷勤：
·使用无懈可击挡下南猪入侵、万箭齐发、决斗。
·使用无懈可击抵消表敌意。
·表敌意：
·对某个角色使用杀、决斗。
·使用无懈可击抵消献殷勤。
·跳忠：
·即通过行动表示自己是忠猪。
·跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意。
·跳反：
·即通过行动表示自己是反猪。
·跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤。
·忠猪不会跳反，反猪也不会跳忠。
·不管是忠猪还是反猪，能够跳必然跳。
·共性：
·每个角色如果手里有桃且生命值未满，那么必然吃掉。
·有南猪入侵、万箭齐发、必然使用。
·有装备必然装上。
·受到杀时，有闪必然弃置。
·响应南猪入侵或者万箭齐发时候，有杀/闪必然弃置。
·不会对未表明身份的猪献殷勤（包括自己）。
·特性：
·主猪：
·主猪会认为没有跳身份，且用南猪入侵/万箭齐发对自己造成伤害的猪是类反猪（没伤害到不算，注意类反猪并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪。
·对于每种表敌意的方式，对逆时针方向能够执行到的第一只类反猪或者已跳反猪表；如果没有，那么就不表敌意。
·决斗时会不遗余力弃置杀。
·如果能对已经跳忠的猪或自己献殷勤，那么一定献。
·如果能够对已经跳反的猪表敌意，那么一定表。
·忠猪：
·对于每种表敌意的方式，对逆时针方向能够执行到的第一只已经跳反的猪表，如果没有，那么就不表敌意。
·决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀。
·如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献。
·反猪：
·对于每种表敌意的方式，如果有机会则对主猪表，否则，对逆时针方向能够执行到的第一只已经跳忠的猪表，如果没有，那么就不表敌意。
·决斗时会不遗余力弃置杀。
·如果有机会对已经跳反的猪献殷勤，那么一定献。
现在，我们已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏，你需要做的就是告诉小猪最后的结果。
限于只会用语言写，他请你用、或语言来帮他预测最后的结果。
输入文件第一行包含两个正整数()和()，分别代表玩家数和牌堆中牌的数量。数据保证牌的数量够用。
接下来行，每行个字符串，依次表示对第只猪的角色和初始张手牌描述。编号为的肯定是主猪。
再接下来一行，一共个字符串，按照从牌堆顶部到牌堆底部的顺序描述每张牌。
所有的相邻的两个字符串都严格用个空格隔开，行尾没有多余空格。
输出数据第一行包含一个字符串代表游戏结果。如果是主猪胜利，那么输出，否则输出。数据保证游戏总会结束。
接下来行，第行是对第只猪的手牌描述（注意只需要输出手牌），按照手牌从左往右的顺序输出，相邻两张牌用一个空格隔开，行末尾没有多余空格。如果这只猪已阵亡，那么只要输出即可。注意如果要输出手牌而没有手牌的话，那么只需输出一个空行。
现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对一个网格的地形：
左上角点为,右下角点为.有以下三种类型的道路
道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角的窝里，现在它们要跑到右下解的窝中去，狼王开始伏击些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.
第一行为.表示网格的大小，均小于等于.
接下来分三部分
第一部分共行，每行个数，表示横向道路的权值.
第二部分共行，每行个数，表示纵向道路的权值.
第三部分共行，每行个数，表示斜向道路的权值.
输入文件保证不超过
输出一个整数，表示参与伏击的狼的最小数量.