NOIP2016提高组复赛试题.(Day1+Day2.).doc

《NOIP2016提高组复赛试题.(Day1+Day2.).doc》由会员分享，可在线阅读，更多相关《NOIP2016提高组复赛试题.(Day1+Day2.).doc（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 第 22 届全国青少年信息学奥林匹克联赛CCF-NOIP-2016 提高组（复赛） 第一试竞赛时间：2016 年 11 月 19 日 8:30 12:00题目名称 玩具谜题 天天爱跑步 换教室 题目类型 传统型 传统型 传统型 目录 toyrunningclassroom可执行文件名 toyrunningclassroom输入文件名 toy.inrunning.inclassroom.in输出文件名 toy.outrunning.outclassroom.out每个测试点时限 1.0 秒 2.0 秒 1.0 秒 内存限制 512 MB512 MB512 MB测试点数目 202025每个测试点

2、分值 554提交源程序文件名对于 C+语言 toy.cpprunning.cppclassroom.cpp对于 C语言 toy.crunning.cclassroom.c对于 Pascal 语言 toy.pasrunning.pasclassroom.pas编译选项对于 C+语言 -lm-lm-lm对于 C语言 -lm-lm-lm对于 Pascal 语言 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。 3. C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须 是 0。

3、4. 全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存 4G，上述时限以此配置为准。 5. 只提供 Linux 格式附加样例文件。 6. 评测在 NOI Linux 下进行。 7. 编译时不打开任何优化选项。玩具谜题（toy)【问题描述】小南有一套可爱的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈， 它们有的面朝圈内，有的面朝圈外。如下图：这时 singer 告诉小南一个谜题：“眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩 具小人的左数第 2 个玩具小

4、人那里。”小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的 左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方 向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。小南一边艰难地辨认着玩具小人，一边数着：“singer 朝内，左数第 3 个是 archer。“archer 朝外，右数第 1 个是 thinker。“thinker 朝外，左数第 2 个是 writer。“所以眼镜藏在 writer 这里！”虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼 镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望

5、你写程序帮他解 决类似的谜题。这样的谜题具体可以描述为：有 n 个玩具小人围成一圈，己知它们的职业和朝向。现在第 1 个玩具小人告诉小南 一个包含 m 条指令的谜题，其中第 i 条指令形如“左数/右数第 si 个玩具小人”。你需要输 出依次数完这些指令后，到达的玩具小人的职业。【输入格式】从文件 toy.in 中读入数据。输入的第一行包含两个正整数 n,m ，表示玩具小人的个数和指令的条数。接下来 n 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小 人的朝向和职业。其中 0 表示朝向圈内， 1 表示朝向圈外。保证不会出现其他的数。字 符串长度不超过 10 且仅由小写字母构成，字

6、符串不为空，并且字符串两两不同。整数 和字符串之间用一个空格隔开。接下来 m 行，其中第 i 行包含两个整数 ai, si ，表示第 i 条指令。若 ai = 0 ，表示向左数 si 个人；若 ai = 1 ，表示向右数 si 个人。保证 ai 不会出现其他的数， 1 si n。【输出格式】输出到文件 toy.out 中。输出一个字符串，表示从第一个读入的小人开始，依次数 完 m 条指令后到达的小人的职业。【样例 1 输入】7 30 singer0 reader0 mengbier1 thinker1 archer0 writer1 mogician0 31 10 2【样例 1 输出】writ

7、er【样例 1 说明】这组数据就是【题目描述】中提到的例子。【样例 2 输入】10 101 c0 r0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【样例 2 输出】y【子任务】子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试 只解决一部分测试数据。每个测试点的数据规模及特点如下表：测试点 nm全朝内 全左数 si = 1职业长度为 11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16= 20= 103 17 18 19 20= 105= 105 其中一些简写的列意义如下： 全朝内：若为

8、“”， 表示该测试点保证所有的玩具小人都朝向圈内； 全左数：若为“”，表示该测试点保证所有的指令都向左数，即对任意的 1 i m， ai = 0 ； si = 1 ：若为“”，表示该测试点保证所有的指令都只数 1 个，即对任意的 1 i m， si = 1 ； 职业长度为 1：若为“”，表示该测试点保证所有玩具小人的职业一定是一个长度 为 1 的字符串。天天爱跑步（running)【问题描述】小 C 同学认为跑步非常有趣，于是决定制作一款叫做天天爱跑步的游戏。 天 天爱跑步是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。这个游戏的地图可以看作一棵包含 n 个结点和 n 1 条边的树，每条

9、边连接两个结 点，且任意两个结点存在一条路径互相可达。树上结点编号为从 1 到 n 的连续正整数。现在有 m 个玩家，第 i 个玩家的起点为 Si ，终点为 Ti 。每天打卡任务开始时，所 有玩家在第 0 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着 最 短 路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 （由于地图是 一棵树，所以每个人的路径是唯一的）小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 j 的 观 察员会选择在第 Wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家 在第 Wj 秒也正好到达了结点 j 。小 C 想知道每

10、个观察员会观察到多少人？注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。即对于把结点 j 作为终点的玩家：若他在第 Wj 秒前到达 终点，则在结点 j 的观察员不能观察到该玩家；若他正好在第 Wj 秒到达终点，则在结 点 j 的观察员可以观察到这个玩家。【输入格式】从文件 running.in 中读入数据。第一行有两个整数 n 和 m 。其中 n 代表树的结点数量，同时也是观察员的数量，m 代表玩家的数量。接下来 n 1 行每行两个整数 u 和 v ，表示结点 u 到结点 v 有一条边。接下来一行 n 个整数，其中第 j 个整数为 Wj ，表示

11、结点 j 出现观察员的时间。接下来 m 行，每行两个整数 Si和 Ti ，表示一个玩家的起点和终点。对于所有的数据，保证 1 Si , Ti n ， 0 Wj n 。【输出格式】输出到文件 running.out 中。输出 1 行 n 个整数，第 j 个整数表示结点 j 的观察员可以观察到多少人。【样例 1 输入】6 32 31 21 44 54 60 2 5 1 2 31 51 32 6【样例 1 输出】2 0 0 1 1 1【样例 1 说明】对于 1 号点， W1 = 0 ，故只有起点为 1 号点的玩家才会被观察到，所以玩家 1 和玩 家 2 被观察到，共 2 人被观察到。对于 2 号点，

12、没有玩家在第 2 秒时在此结点，共 0 人被观察到。对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。对于 4 号点，玩家 1 被观察到，共 1 人被观察到。对于 5 号点，玩家 1 被观察到，共 1 人被观察到。对于 6 号点，玩家 3 被观察到，共 1 人被观察到。【样例 2 输入】5 31 22 32 41 50 1 0 3 03 11 45 5【样例 2 输出】1 2 1 0 1【子任务】每个测试点的数据规模及特点如下表所示。提示：数据范围的个位上的数字可以帮 助判断是哪一种数据类型。测试点编号 nm约定 12= 991= 991所有人的起点等于自己的终点，即 Si=

13、 Ti34= 992= 992Wj= 05= 993= 993无 678= 99994= 99994树退化成一条链，其中 1 与 2 有边，2 与 3 有边，. . . ，n 1 与 n 有边 9101112= 99995= 99995所有的 Si= 113141516= 99996= 99996所有的 Ti= 1171819= 99997= 9999720= 299998= 299998无 【提示】如果你的程序需要用到较大的栈空间（这通常意味着需要较深层数的递归） ，请务 必仔细阅读选手目录下的文档 running/stack.pdf ，以了解在最终评测时栈空间的限制 与在当前工作环境下调整

14、栈空间限制的方法。换教室（classroom)【问题描述】对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的 课程。在可以选择的课程中，有 2n 节课程安排在 n 个时间段上。在第 i ( 1 i n )个 时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 ci上课，而另一节课程在教室 di 进行。在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 n 节安排 好的课程。如果学生想更换第 i 节课程的教室，则需要提出申请。若申请通过，学生就 可以在第 i 个时间段去教室 di 上课，否则仍然在教室 di 上课。由于更换教 室的需求太

15、多，申请不一定能获得通过。通过计算，牛牛发现申请更 换第 i 节课程的教室时，申请被通过的概率是一个己知的实数 ki ，并且对于不同课程 的申请，被通过的概率是互相独立的。学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而 不 能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更 换 教室的 m 门课程，也可以不用完这 m 个申请的机会，甚至可以一门课程都不申请。因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从 一间教室赶到另一间教室。牛牛所在的大学有 v

16、个教室，有 e 条道路。每条道路连接两间教室，并且是可 以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 i （ 1 i n 1 ）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体 力最少的路径前往下一节课的教室。现在牛牛想知道，申请哪几门课程可以使他因在 教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和 的期望值最小，请你帮他求出这个最小值。【输入格式】从文件 classroom.in 中读入数据。第一行四个整数 n, m, v, e 。 n 表示这个学期内的

17、时间段的数量； m 表示牛牛最多 可以申请更换多少节课程的教室； v 表示牛牛学校里教室的数量； e 表示牛牛的学校 里道路的数量。第二行 n 个正整数，第 i （ 1 i n ）个正整数表示 ci ，即第 i 个时间段牛牛被安 排上课的教室；保证 1 ci v 。第三行 n 个正整数，第 i （ 1 i n ）个正整数表示 di ，即第 i 个时间段另一间上同样课程的教室；保证 1 di v 。第四行 n 个实数，第 i （ 1 i n ）个实数表示 ki ，即牛牛申请在第 i 个时间段更 换教室获得通过的概率。保证 0 ki 1 。接下来 e 行，每行三个正整数 aj， bj， wj ，表

18、示有一条双向道路连接教室 aj, bj ，通过这条道路需要耗费的体力值是 wj ；保证 1 aj, bj v ， 1 wj 100 。保证 1 n 2000 ， 0 m 2000 ， 1 v 300 ， 0 e 90000 。保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。保证 输入的实数最多包含3 位小数。【输出格式】输出到文件 classroom.out 中。输出一行，包含一个实数，四舍五入精确到小数点后恰好 2 位，表示答案。你的输 出必须和标准输出完全一样才算正确。测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 410-3 。（如果你 不知道什么是浮点误差，

19、这段话可以理解为：对于大多数的算法，你可以正常地使用浮 点数类型而不用对它进行特殊的处理）【样例 1 输入】3 2 3 32 1 21 2 10.8 0.2 0.51 2 51 3 32 3 1【样例 1 输出】2.80【样例 1 说明】所有可行的申请方案和期望收益如下表：申请更换教室的 时间段申请通过的时间 段出现的概率耗费的体力值耗费的体力值的 期望无 无 1.088.010.841无 0.284.820.202无 0.886.430.543无 0.586.01、20.16410.64420.0401、2无 0.1684.481、30.4010.4430.141、3无 0.182.82、3

20、0.1420.1030.442、3无 0.485.2【样例 2】见选手目录下的 classroom/classroom2.in 与 classroom/classroom2.ans。【提示】1. 道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是同 一间教室。 2. 请注意区分 n, m, v, e 的意义， n 不是教室的数量， m 不是道路的数量。【子任务】测试点 nmv特殊性质 1特殊性质 21 1 1 300 2 0 20 3 1 100 4 2 2 300 5 0 20 6 1 100 7 3 2 8 0 300 9 1 20 10 2 100 11 10 10

21、 300 12 0 20 13 1 100 14 2 15 20 20 300 16 0 20 17 1 100 18 2 19 300 300 300 20 0 21 1 2022 2 23 1002425 2000 2000 300 特殊性质 1：图上任意两点 ai ， bi ， ai bi 间，存在一条耗费体力最少的路径只 包含一条道路。特殊性质 2：对于所有的 1 i n ， ki = 1 。第 22 届全国青少年信息学奥林匹克联赛CCF-NOIP-2016 提高组（复赛） 第二试竞赛时间：2016 年 11 月 20 日 8:30 12:00题目名称 组合数问题 蚯蚓 愤怒的小鸟 题

22、目类型 传统型 传统型 传统型 目录 problemearthwormangrybirds可执行文件名 problemearthwormangrybirds输入文件名 problem.inearthworm.inangrybirds.in输出文件名 problem.outearthworm.outangrybirds.out每个测试点时限 1.0 秒 1.0 秒 2.0 秒 内存限制 512 MB512 MB512 MB测试点数目 202020每个测试点分值 555提交源程序文件名对于 C+语言 problem.cppearthworm.cppangrybirds.cpp对于 C语言 prob

23、lem.cearthworm.cangrybirds.c对于 Pascal 语言 problem.pasearthworm.pasangrybirds.pas编译选项对于 C+语言 -lm-lm-lm对于 C语言 -lm-lm-lm对于 Pascal 语言 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。 3. C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须 是 0。 4. 全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 pr

24、ocessor， 2.8GHz，内存 4G，上述时限以此配置为准。 5. 只提供 Linux 格式附加样例文件。 6. 评测在 NOI Linux 下进行。 7. 编译时不打开任何优化选项。i组合数问题（problem)【问题描述】组合数表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从(1, 2, 3)三 个物品中选择两个物品可以有(1, 2),(1, 3),(2, 3)这三种选择方法。根据组合数的定义， 我们可以给出计算组合数的一般公式：其中 n! = 1 2 n 。小葱想知道如果给定 n, m 和 k ，对于所有的 0 i n, 0 j min (i, m) 有多少对(i,

25、j) 满足是 k 的倍数。【输入格式】从文件 problem.in 中读入数据。第一行有两个整数 t, k ，其中 t 代表该测试点总共有多少组测试数据，k 的意义见 【问题描述】 。接下来 t 行每行两个整数 n, m ，其中 n, m 的意义见【问题描述】 。【输出格式】输出到文件 problem.out 中。t 行，每行一个整数代表所有的0 i n, 0 j min (i, m) 中有多少对(i, j) 满足是 k 的倍数。【样例 1 输入】1 23 3【样例 1 输出】1【样例 1 说明】在所有可能的情况中，只有= 2 是 2 的倍数。【样例 2 输入】2 54 56 7【样例 2 输

26、出】07【子任务】测试点 nmkt1= 2= 12 3 3 = 3 104 3= 4= 14 7 7 = 5 104 5= 6= 16 10 10 = 7 104 7= 8= 18 20 100 = 9 104 9= 10= 110 25 2000 = 11 104 11= 12= 112 60 20 = 13 104 13= 14= 114 25 = 15 104 15= 16= 116 100 60 = 17 104 17= 18= 118 100 = 19 104 19= 20= 120 2000 2000 = 21 104蚯蚓（earthworm)【问题描述】本题中，我们将用符号 Lc

27、J 表示对 c 向下取整，例如： L3.0J = L3.1J = L3.9J = 3。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神 刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有 n 只蚯蚓（ n 为正整数） 。每只蚯蚓拥有长度，我们设第 i 只蚯蚓 的长度为 ai ( i = 1, 2, . . . , n )，并保证所有的长度都是非负整数（即：可能存在长度为 0 的 蚯蚓） 。每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个） 将其切成两半。神刀手切开蚯蚓的位置由常数 p （是满足 0 p 1 的有理数）决定，设这只蚯蚓长度为 x ，神刀手会

28、将其切成两只长度分别为 LpxJ 和 x LpxJ 的蚯蚓。特殊地，如 果这两个数的其中一个等于 0 ，则这个长度为 0 的蚯蚓也会被保留。此 外，除了刚刚产生 的两只新蚯蚓，其余蚯蚓的长度都会增加 q（是一个非负整常数） 。蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐 蛐 国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来.（m 为 非负整数）蛐蛐国王希望知道这 m 秒内的战况。具体来说，他希望知道： m 秒内，每一秒被切断的蚯蚓被切断前的长度（有 m 个数） ； m 秒后，所有蚯蚓的长度（有 n + m 个数） 。蛐蛐国王当然知道怎么做啦!

29、但是他想考考你.【输入格式】从文件 earthworm.in 中读入数据。第一行包含六个整数 n, m, q, u, v, t ，其中： n, m, q 的意义见【问题描述】 ； u, v, t 均 为 正整数；你需要自己计算 p = u/v （保证 0 u v ） ；t 是输出参数，其含义将会在【输出 格式】中解释。第二行包含 n 个非负整数，为 a1, a2, . . . , an ，即初始时 n 只蚯蚓的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。保证 1 n 105 ， 0 m 7 106 ， 0 u v 109 ， 0 q 200 ， 1 t 71 ，0 ai 108 。【输

30、出格式】输出到文件 earthworm.out第一行输出 个整数，按时间顺序，依次输出第 t 秒，第 2t 秒，第 3t 秒，.被切 断蚯蚓（在被切断前）的长度。第二行输出个整数，输出 m 秒后蚯蚓的长度：需要按从大到小的顺序，依 次输出排名第 t ，第 2t ，第 3t ，. . . . . . 的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出， 你也应输出一个空行。请阅读样例来更好地理解这个格式。【样例 1 输入】3 7 1 1 3 13 3 2【样例 1 输出】3 4 4 4 5 5 66 6 6 5 5 4 4 3 2 2【样例 1 说明】在神刀手到来

31、前：3 只蚯蚓的长度为 3,3,2。1 秒后：一只长度为 3 的蚯蚓被切成了两只长度分别为 1 和 2 的蚯蚓，其余蚯蚓的长度 增加了 1。最终 4 只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。2 秒后：一只长度为 4 的蚯蚓被切成了 1 和 3。5 只蚯蚓的长度分别为：2,3,(1,3),4。3 秒后：一只长度为 4 的蚯蚓被切断。6 只蚯蚓的长度分别为：3,4,2,4,(1,3)。4 秒后：一只长度为 4 的蚯蚓被切断。7 只蚯蚓的长度分别为：4,(1,3),3,5,2,4。5 秒后：一只长度为 5 的蚯蚓被切断。8 只蚯蚓的长度分别为：5,2,4,4,(1

32、,4),3,5。6 秒后：一只长度为 5 的蚯蚓被切断。9 只蚯蚓的长度分别为：(1,4),3,5,5,2,5,4,6。7 秒后：一只长度为 6 的蚯蚓被切断。10 只蚯蚓的长度分别为：2,5,4,6,6,3,6,5,(2,4)。所以，7 秒内被切断的蚯蚓的长度依次为 3,4,4,4,5,5,6。7 秒后，所有蚯蚓长度从大到小 排序为 6,6,6,5,5,4,4,3,2,2。【样例 2 输入】3 7 1 1 3 23 3 2【样例 2 输出】4 4 56 5 4 3 2【样例 2 说明】这个数据中只有 t = 2 与上个数据不同。只需在每行都改为每两个数输出一个数即可。虽然第一行最后有一个 6

33、 没有被输出，但是第二行仍然要重新从第二个数再开始输 出。【样例 3 输入】3 7 1 1 3 93 3 2【样例 3 输出】2【样例 3 说明】这个数据中只有 t = 9 与上个数据不同。注意第一行没有数要输出，但也要输出一个 空行。【子任务】测试点 1 3 满足 m = 0 。 测试点 4 7 满足 n, m 1, 000 。测试点 8 14 满足 q = 0 ，其中测试点 8 9 还满足 m 105 。测试点 15 18 满足 m 3 105 。测试点 19 20 没有特殊的约定，参见原始的数据范围。测试点 1 12， 15 16 还满足 v 2 ， 这意味着 u, v 的唯一可能的取值

34、是 u = 1, v = 2 ，即 p = 0.5 。这可能会对解决问题有特殊的帮助。 每个测试点的详细数据范围见下表。测试点nmtaivq1= 12= 1033= 105= 04= 15= 103= 06= 17= 103= 103 2008= 5 104= 5 104= 19= 105= 210= 2 106= 2111= 2.5 106= 26 10612= 3.5 106= 36 213= 5 106= 51 10714= 105= 7 106= 71 109= 015= 5 106= 116= 5 104= 1.5 106= 2 217= 105= 318= 3 105= 419=

35、3.5 106= 3620= 105= 7 106= 71 108 109 200愤怒的小鸟（angrybirds)【问题描述】Kiana 最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。有一架弹弓位于 (0, 0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟 们的飞行轨迹均为形如 y = ax2 + bx 的曲线，其中 a, b 是 Kiana 指定的参数，且必须满足 a 0。当小鸟落回地面（即 x 轴）时，它就会瞬间消失。在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的 坐标为 (xi, yi)。如果某只小鸟

36、的飞行轨迹经过了 (xi, yi) ，那么第 i 只小猪就会被消灭掉，同时小鸟将 会沿着原先的轨迹继续飞行；如果一只小鸟的飞行轨迹没有经过 (xi, yi) ，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。例如，若两只小猪分别位于 (1, 3) 和 (3, 3) ，Kiana 可以选择发射一只飞行轨迹为 y = x2 + 4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令， 使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。假设

37、这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射 多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。【输入格式】从文件 angrybirds.in 中读入数据。第一行包含一个正整数 T ，表示游戏的关卡总数。 下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整数 n, m ，分别表示 该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n 行中，第 i 行包含两 个正实数 xi, yi ，表示第 i 只小猪坐标为 (xi, yi) 。数据保证同一个关卡中不存在两只坐 标完全相同的小猪。如果 m = 0 ，表示 Kiana

38、输入了一个没有任何作用的指令。如果 m = 1 ，则这个关卡将会满足：至多用n/3 + 1只小鸟即可消灭所有小猪。如果 m = 2 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了 至少 Ln/3J 只小猪。保证 1 n 18 ， 0 m 2 ， 0 xi, yi 10 ，输入中的实数均保留到小数点后两 位。上文中，符号 c 和 LcJ 分别表示对 c 向上取整和向下取整，例如： 2.1 = 2.9 =3.0 = L3.0J = L3.1J = L3.9J = 3 。【输出格式】输出到文件 angrybirds.out 中。对每个关卡依次输出一行答案。输出的每一行包含一个正整数，

39、表示相应的关卡中，消灭所有小猪最少需要的小鸟数 量。【样例 1 输入】22 01.00 3.003.00 3.005 21.00 5.002.00 8.003.00 9.004.00 8.005.00 5.00【样例 1 输出】11【样例 1 说明】这组数据中一共有两个关卡。第一个关卡与【问题描述】中的情形相同，2 只小猪分别位于(1.00,3.00)和(3.00,3.00)， 只需发射一只飞行轨迹为 y = x2 + 4x 的小鸟即可消灭它们。第二个关卡中有 5 只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y = x2 + 6x 上，故 Kiana 只需要发射一只小鸟即可消灭所有小猪

40、。【样例 2 输入】32 01.41 2.001.73 3.003 01.11 1.412.34 1.792.98 1.495 02.72 2.722.72 3.143.14 2.723.14 3.145.00 5.00【样例 2 输出】223【样例 3 输入】110 07.16 6.282.02 0.388.33 7.787.68 2.097.46 7.865.77 7.448.24 6.724.42 5.115.42 7.798.15 4.99【样例 3 输出】6【子任务】数据的一些特殊规定如下表：测试点编号 nmT1 10 2 2 30 3 10 4 3 30 5 10 6 4 30 7 5 8 6 9 7 10 8 1011 9 12 10= 013= 114 12 = 2 3015= 016= 117 15= 2 1518= 019= 120 18= 2 5