猴子的争斗
Time limit: 1s Memory limit: 32768K Total Submit : 184 Accepted Submit : 75
【问题描述】
从前在一个森林里，有N只好斗的猴子。一开始，他们互不认识。互不认识的猴子间是无法避免争斗的，而且争斗只会发生在两只互不认识的猴子间。决斗结束后，这两只猴子和他们各自的朋友们通过这场决斗相互间都认识了，争斗便不会再发生在这一大群猴子中的任两只。由于争斗是比较激烈的，所以同一时间内不会有两场决斗一起发生。经过N-1次决斗后，这N只猴子间相互都认识了，现在问有多少种可能的决斗过程。例如N=3，有6种不同的过程：12->13，12->23，13->12，13->32，23->21， 23->31。
【要求】
【数据输入】文件里只有一个整数N(2≤N≤1000)。
【数据输出】输出一个整数，为可能的过程的总数除以10007的余数。
【样例输入】 4
【样例输出】 96
排序
Time limit: 10s Memory limit: 32768K Total Submit : 70 Accepted Submit : 2
【问题描述】
通常我们对一个长度为n(n≤24)的整数数列进行排序操作，其实就是讲他们按照从小到大的顺序重整。一般情况下我们可以比较任意两个数之间的大小并交换他们的位置，但这里我们限制只能数列的某一个前缀序列翻转，除此之外的任何操作都是不允许的。更精确地说，假设数列a1，a2，??，an，一个合法的操作是把数列变为ak，ak-1，??，a2, a1, ak+1, ak+2,??, an，其中1 【要求】 【数据输入】输入文件有两行：第一行是一个整数n，表示数列的长度。第二行有n个整数，表示待排序的数列，每个整数的绝对值不大于32767。 【数据输出】输出文件有一行是一个整数s，表示完成排序所需的最少步数。 【样例输入】 4 3 2 1 4 【样例输出】 1 提示：只需要一步就可以完成排序：3 2 1 4 1 2 3 4。 选址 Time limit: 10s Memory limit: 32768K Total Submit : 100 Accepted Submit : 13 【问题描述】 很久以前，在世界的某处有一个形状为凸多边形的小岛，岛上的居民们决定建一个祭坛，居民们认为祭坛的位置离岛的顶点处越远越好。你的任务是求凸多边形内一点，使其与各顶点的距离中最短的距离最远，点在边上也可以。这样的点可能有多个，你只需输出这些点与各顶点的最短距离。 【要求】 【数据输入】第一行是一个整数N(3≤N≤100)。 接下来N行按逆时针顺序给出每个顶点的坐标，每行包含2个实数，表示顶点的横坐标和纵坐标(坐标绝对值小于10000)。 【数据输出】输出一个实数，表示凸多边形内一点与各顶点的距离中最短的距离的最大值。 【样例输入】 3 0 2 9 0 7 7 【样例输出】 4.893 过河 Time limit: 1s Memory limit: 32768K Total Submit : 518 Accepted Submit : 65 【问题描述】 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，??，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 【要求】 【数据输入】输入的第一行有一个正整数L（1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【数据输出】输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。 【样例输入】 10 2 3 5 2 3 5 6 7 【样例输出】 2 数字游戏 Time limit: 1s Memory limit: 32768K Total Submit : 323 Accepted Submit : 89 【问题描述】 小W发明了一个游戏，他在黑板上写出了一行数字a1,a2,?.an，然后给你m个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦去的数字之和就是你所得到的分数。 小W和他的好朋友小Y玩了这个游戏，可是他发现，对于每个给出的an和bn序列，小Y的得分总是比他高，所以他就很不服气。于是他想让你帮他算算，对于每个an和bn序列，可以得到的最大得分是多少。这样他就知道有没有可能超过小Y的得分。 【要求】 【数据输入】 第一行，一个整数n（1<=n<=200），表示数字的个数。 第二行，一个整数m（1<=m<=n），表示回合数。 接下来一行有n个不超过10000的正整数，a1,a2?an，表示原始数字，最后一行有n个不超过500的正整数，b1,b2?.bn，表示每回合每个数字递减的值 【数据输出】一个整数，表示最大可能的得分 【样例输入】 3 3 10 20 30 4 5 6 【样例输出】 47