Time Limit:
Memory Limit:
每年春季，在某岛屿上都会举行游行活动。
在这个岛屿上有个城市，条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市出发，经过若干个城市，到城市结束，需要特别注意的是，每个英雄的巡游的可以和相同，但是必须至少途径2个城市。
每次游行你的花费将由部分构成：
你有无数个的英雄。你要合理安排游行方案，使得费用最小。
由于每年，值都是不一样的。所以你要回答个询问，每个询问都是，当为当前输入数值的时候的答案。
第一行正整数 。
接下来的行，每行，表示有一条从到，边权为的有向道路。保证不会有自环，但不保证没有重边。
接下来行，每行一个，表示询问当每次费用为时的最小答案。
行，每行代表一个询问的答案。
最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含个十字路口和条街道，只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。每天从寝室出发 跑到学校，保证寝室编号为，学校编号为。 的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。 除了练空手道，其他时间都花在了学习和找上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
第一行：两个数。表示十字路口数和街道数。
接下来行，每行个数，表示路口和路口之间有条长度为的街道（单向）。
两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长度。
上的时间又过了若干世纪……
现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，那里简直就是另外一个世界。善于分析与构造的上的人们总是不明白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。
偶然地，一个魔法使（）来到了，在临走的时候留下了一个神奇的盒子，叫做星器（）。
虽然不知道这个盒子是做什么的，但是经过了大量的实验和计算后，人们已经清楚它的一些事实：
当星器为左图的状态时，通过操纵第一行的第和个区域中的“星”（加粗的数字对应的区域），变为右图所示的状态，同时，将产生单位的魔力（因为这两个区域之间恰好隔了个区域）。
在经过了进一步的研究之后，人们知道了这个星器最初的状态（）以及最终被他们得到时的状态（）。
你希望知道，星器最多帮助它的拥有者提供了多少的魔力。即：经过一系列上述操作由初态（）变为终态（），至多产生多少魔力。
需要注意的是，显然操作过程中每个区域内“星”的数量不能是负的，即：如果那个区域已经没有“星”了，当然就不能继续操作了。
第一行包含两个正整数、表示星器的大小。
接下来的行，每行包含个自然数：，描绘了初态（）。
在一个空行后的行，每行包含个自然数：，描绘了终态（）。
输出一个正整数，表示至多产生的魔力。
Time Limit:
Memory Limit:
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为。
现在有一种卡牌游戏，每张卡牌上有三个属性值：。把卡牌分为两类，分别有张。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
比如一张类卡牌属性值分别是，一张类卡牌属性值分别为。那么这两张牌是可以配对的，因为只有和一组属性互质。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。
数据第一行两个数，，空格分割。
接下来行，每行个数，依次表示每张类卡牌的项属性值。
接下来行，每行个数，依次表示每张类卡牌的项属性值。
输出一个整数：最多能够匹配的数目。
给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大，输出最大的总价值。
数据范围：，且保证每颗宝石的重量可以表示为的形式（其中）
输入文件中包含多组数据。每组数据的格式如下：第一行是两个正整数和，，分别表示宝石的数目和最多能带走的宝石重量。接下来的行，每行有两个正整数和，，分别表示第i颗宝石的重量和价值，且保证能写成的形式。同一行的两个正整数之间用空格隔开。最后一组数据的后面有两个，表示文件的结束。这两个并不代表一组数据，你不需对这组数据输出结果。并且输入文件中数据的组数不超过。
对于输入的每组数据，输出一个整数，表示小P最多能带走的宝石的总价值。每个结果整数单独占一行，且保证不会超过。
有 种数字，第 种数字是 、有 个，权值是 。
若两个数字 满足， 是 的倍数，且 是一个质数，那么这两个数字可以配对，并获得 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 的前提下，求最多进行多少次配对。
第一行一个整数 。
第二行 个整数 。
第三行 个整数。
第四行 个整数 。
一行一个数，最多进行多少次配对
The country Treeland consists of n cities, some pairs of them are connected with unidirectional roads. Overall there are roads in the country. We know that if we don’t take the direction of the roads into consideration, we can get from any city to any other one.
The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city a is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city a to any other city. For that some roads may have to be inversed.
Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.
The first input line contains integer — the number of cities in Treeland. Next lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers — the numbers of cities, connected by that road. The road is oriented from city to city . You can consider cities in Treeland indexed from to .
In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.
Time Limit:
Memory Limit:
喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。 在森林里有个巫妖，每个巫妖释放之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道，若从时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？
输入文件第一行包含三个整数，分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来行，每行包含四个整数，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。 再接下来行，每行两个整数，分别代表了每个小精灵的坐标。 再接下来K行，每行三个整数，分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过，半径和施法间隔不超过。
输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出。
Princess Twilight went to Celestia and Luna’s old castle to research the chest from the Elements of Harmony.
A sequence of positive integers is harmony if and only if for every two elements of the sequence their greatest common divisor equals . According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:
You are given sequence , help Princess Twilight to find the key.
The first line contains an integer — the number of elements of the sequences and . The next line contains integers .
Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.