题目：4.分玩具已知 n 位小朋友对 m 件玩具的喜好（n ≤ m），现要将 m 件玩具分给 n 位小朋友，每位小朋友只能分到 1 件玩具，每件玩具也最多只能分给 1 位小朋友，并且还要求每位小朋友都能分到自己喜欢的玩具。本题请你对任意 n 和 m 尝试列出所有满足要求的方案。时间限制：5000内存限制：65536输入输入第一行给出两个正整数 n 和 m（n ≤ m ≤ 8），即小朋友人数和玩具的数量。 随后 n 行，每行给出 m 个数字。其中第 i 行第 j 个数字为 1 表示第 i 位小朋友喜欢第 j 件玩具，为 0 则表示不喜欢。输出按升序列出所有满足要求的方案，格式为 (s1, … , sn)。其中 si 表示第 i 位小朋友分到了第 si 件玩具。 注：方案 (a1, … , an) < (b1, … , bn) 是指存在 1 ≤ k ≤ n，使得 ai = bi 对所有 1 ≤ i< k 成立，并且有 ak < bk。样例输入4 50 1 0 0 11 1 0 1 01 0 1 1 00 0 0 1 1样例输出(2, 1, 3, 4)(2, 1, 3, 5)(2, 1, 4, 5)(2, 4, 1, 5)(2, 4, 3, 5)(5, 1, 3, 4)(5, 2, 1, 4)(5, 2, 3, 4)

题目：3.增高垫网传最大号的增高垫有 16 厘米，可以一下把 1.64 米的男孩变成一米八的大汉，不少对自己身高缺乏自信的男生女生会悄悄买来穿，特别是大家站成一排拍照的时候。假设准备拍照的一排人中，只要有人看到身边紧挨着的人比自己高，就会忍不住穿增高垫，并且一定要比人家多穿一层。你的任务就是在看过这一排人的身高后，算出谁穿了最多层的增高垫。时间限制：1000内存限制：65536输入输入首先在第一行给出正整数 n（≤ 104），为一排人的个数。随后一行给出 n 个正整数，表示 n 个人的身高（厘米）。每个数值是不超过 300 的正整数，数字间以空格分隔。输出在一行中输出穿了最多层增高垫的人的位置和穿的层数（位序从左到右，从 1 开始）。如果有并列，按从左到右的顺序，每个人的信息占一行。样例输入10150 160 186 200 170 175 180 186 186 183样例输出1 35 3

题目：2.狼人杀简单版以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？本题是这个问题的升级版：已知 n 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？时间限制：1000内存限制：65536输入输入在第一行中给出一个正整数 n（5 ≤ n ≤ 100）。随后 n 行，第 i 行给出第 i 号玩家说的话（1 ≤ i ≤ n），即一个玩家编号，用正号表示好人，负号表示狼人。输出如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 A = { a[1], ..., a[M] } 和 B = { b[1], ..., b[M] }，若存在 0 ≤ k < M 使得 a[i]=b[i] （i ≤ k），且 a[k+1] < b[k+1]，则称序列 A 小于序列 B。若无解则输出 `No Solution`。样例输入样例#1：5-2+3-4+5+4样例#2：6+6+3+1-5-2+4样例#3：5-2-3-4-5-1样例输出样例#1：1 4样例#2：1 5样例#3：No Solution

题目：1.分组均衡性在上机实验课上，老师将所有学生排列为 n 排，每排坐 m 个学生。每个学生有左右两个邻座（除了这一排的左右两端）。每个人可以和自己的邻座互相帮助完成实验。除了每排左右两端的学生，中间的每个学生都可以同时与两个邻座分别协作。由于每个学生的个人能力不同，假设协作产生的小组能力值是两个协作学生的能力值之和，老师希望知道，自己给出的座位安排在多大程度上是“均衡”的 —— 所谓分组均衡性，是指所有可能组成的协作小组的能力值的最大值与最小值之差。给定一张座位安排表，请计算这个安排的分组均衡性。时间限制：1000内存限制：65536输入输入第一行给出 2 个正整数 n 和 m（2 ≤ n, m ≤ 100），依次为座位的排数和每排的人数。 随后 n 行，每行给出 m 个数字，代表对应座位上学生的能力值（为区间 [1, 100] 内的整数）。同行数字间以空格分隔。输出在一行中输出分组均衡性。样例输入3 510 80 30 95 6079 55 63 84 4198 23 72 85 58样例输出67提示样例解释：最强组合是第 3 排的 72+85=157；最弱组合是第 1 排的 10+80=90。因此两者之差为 67。

题目：5.拼大数如何随机生成一个有 n 位数的大数呢？一种方法是，找到 n 个小朋友，每人发一张卡片，卡片一面写着编号（这里假设小朋友们从 1 到 n 编号），另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排，要求一张挨着一张，按他们的编号升序排列，显示他们自己写的数字。但是，让十万个孩子都按指令行动，可太难了。结果是卡片乱七八糟满墙都是，有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8，我们应该在墙上看到 8，但是却看到了 23…… 你的任务就是把这些卡片整理好，得到我们真想要拼成的大数。时间限制：6000内存限制：65536输入输入第一行给出一个正个整数 n (≤ 105)，随后 n 行，每行按 n1 n2的格式给出一张卡片两面的数字。输出在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数，那么就很难说哪个数字是编号，哪个数字是小朋友自己写的，所以解可能是不唯一的。这时候需要输出能得到的最小的数字。样例输入127 118 93 12 124 610 05 12 56 81 47 29 3样例输出359114268072

题目：4.子串和子列子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt 是一个子串，而 pat 就是一个子列。现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。时间限制：1000内存限制：65536输入输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。输出在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。样例输入atpaaabpabttpcatpat样例输出pabt

题目：3.12 5.27 0.0007 9825.4413 10样例输出18 1 4 3 2提示样例解释： 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个，例如 5、4、3、2 就是另一套解。

题目：2.构造性证明关于数学定理证明，也有高下之分。最暴力的证明方法是“构造性证明”，即当需要证明某种解存在时，直接把解构造出来，而不是仅通过推理证明解之存在。下面有一个定理：设 ai（i=1, … , 5）均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l，使得 |ai / aj - ak / al| < 1/2。作为程序员，就请你编写程序构造出正确的下标，验证这个结论。时间限制：1000内存限制：65536输入输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出，我们令输入的数字在 [10-10, 1010] 区间内，且小数点后不超过 10 位小数。输出在一行中首先输出使得定理结论成立的下标有多少套，随后输出最小的一套下标。数字间以 1 个空格分隔，行首尾不得有多余空格。 注：所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4}，是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立，且 ik < jk。样例输入3.12 5.27 0.0007 9825.4413 10样例输出18 1 4 3 2提示样例解释： 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个，例如 5、4、3、2 就是另一套解。

题目：1.最近的斐波那契数斐波那契数列 Fn 的定义为：对 n ≥ 0 有 Fn+2 = Fn+1 + Fn，初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。时间限制：1000内存限制：65536输入输入在一行中给出一个正整数 N（≤ 108）。输出在一行输出与 N 最近的斐波那契数。如果解不唯一，输出最小的那个数。样例输入305样例输出233提示样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72，则应输出较小的那个解。

题目：三足鼎立 当三个国家中的任何两国实力之和都大于第三国的时候，这三个国家互相结盟就呈“三足鼎立”之势，这种状态是最稳定的。 现已知本国的实力值，又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟，以成三足鼎立。有多少种选择呢？ 时间限制：10000 内存限制：65536 输入 输入首先在第一行给出 2 个正整数 n（2 ≤ n ≤ 105）和 P（≤ 109），分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数，表示n 个其他国家的实力值。每个数值不超过 109，数字间以空格分隔。 输出 在一行中输出本国结盟选择的个数。 样例输入 7 30 42 16 2 51 92 27 35 样例输出 9 提示 样例解释： 能联合的另外 2 个国家的 9 种选择分别为： {16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。