NOIP2023年提高组复赛试题(Day1+Day2).docx

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

1、NOIP2023 提 高 组 复 赛 试 题(Day1+Day2)第22 届全国青少年信息学奥林匹克联赛CCF-NO IP-2 016提高组复赛 第一试竞赛时间： 2023 年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测试点数目20

2、2025每个测试点分值554提交源程序文件名对于C+ 语言对于C 语言对于Pascal 语言编译选项toy.cpp toy.c toy.pasrunning.cpp running.c running.pasclassroom.cpp classroom.c classroom.pas对于C+ 对于C对于Pascal语言语言语言-lm-lm-lm-lm-lm-lm留意事项：1. 文件名程序名和输入输出文件名必需使用英文小写。2. 除非特别说明，结果比较方式均为无视行末空格及文末回车的全文比较。3. C/C+中函数 main 的返回值类型必需是 int ，程序正常完毕时的返回值必需 是0。4.

3、全国统一评测时承受的机器配置为： CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存4G，上述时限以此配置为准。5. 只供给Linux 格式附加样例文件。6. 评测在NOI Linux 下进展。7. 编译时不翻开任何优化选项。第一试玩具迷题toy第22 届全国青少年信息学奥林匹克联赛提高组复赛玩具谜题toy)【问题描述】小南有一套得意的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南觉察玩具小人们围成了一个圈， 它们有的面朝圈内，有的面朝圈外。如以以下图：这时singer告知小南一个谜题：“眼镜藏在我左数第3 个玩具小人

4、的右数第1 个玩具小人的左数第2 个玩具小人那里。”小南觉察，这个谜题中玩具小人的朝向格外关键，由于朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方 向；而面对圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。小南一边困难地识别着玩具小人，一边数着：“singer朝内，左数第3 个是archer。“archer朝外，右数第1 个是thinker。“thinker朝外，左数第2 个是writer。“所以眼镜藏在writer这里！”虽然成功找回了眼镜，但小南并没有放心。假设下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜

5、了。所以小南期望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：有n 个玩具小人围成一圈， 己知它们的职业和朝向 。现在第1 个玩具小人告知小南一个包含m 条指令的谜题，其中第 i 条指令形如“左数/右数第si 个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。第 2 页页共 12【输入格式】从文件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 输出】writer【样例

7、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【子任务】子任务会给出局部测试数据的特点 。假设你在解决题目中遇到了困难，可以尝试只解决一局部测试数据。每个测试点的数据规模及特点如下表：测试点1234567891011121314151617181920nm全朝内全左数s = 1i职业长度为1= 20= 103= 105= 105其中一些简写的列意义如下：l 全朝内：假设为“”， 表示该测试点保证全部的玩具小人都朝向圈内；l 全左数：假

8、设为“”，表示该测试点保证全部的指令都向左数，即对任意的1 i m，ai = 0 ；l si = 1 ：假设为“”，表示该测试点保证全部的指令都只数 1 个，即对任意的 1 i m，si = 1 ；l 职业长度为 1：假设为“”，表示该测试点保证全部玩具小人的职业确定是一个长度为1 的字符串。第一试每天爱跑步running第22 届全国青少年信息学奥林匹克联赛提高组复赛每天爱跑步running)【问题描述】小C 同学认为跑步格外好玩，于是打算制作一款叫做每天爱跑步的玩耍 。每天爱跑步是一个养成类玩耍，需要玩家每天按时上线，完成打卡任务。这个玩耍的地图可以看作一棵包含n 个结点和n 1 条边的树

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

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

11、整数Si 和T，表示一个玩家的起点和终点。对于全部的数据，保证1 S , Ti， 0 W n 。ii nj【输出格式】输出到文件running.out 中。输出1 行n 个整数，第j 个整数表示结点j 的观看员可以观看到多少人。【样例 1 输入】6 32 3第一试每天爱跑步running第22 届全国青少年信息学奥林匹克联赛提高组复赛1 21 44 54 60 2 5 1 2 31 51 32 6【样例 1 输出】2 0 0 1 1 1第7 页共12 页【样例 1 说明】对于1 号点，W1= 0 ，故只有起点为1 号点的玩家才会被观看到，所以玩家1 和玩家2 被观看到，共2 人被观看到。对于

12、2 号点，没有玩家在第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【子任务】每个测试点的数据规模及特点如下表所示 。提示：数据范围的个位上的数字可以帮助推断是哪一种数据类型。测试点编号1234567891011121314151617181920nm商定全

13、部人的起点等于自己的终点，= 991= 991即S = Tii= 992= 993= 992= 993W = 0j无= 99994= 99994树退化成一条链，其中1 与2 有边，2 与3 有边，. . ，n 1 与n 有边= 99995= 99995全部的 S = 1i= 99996= 99996全部的 T = 1i= 99997= 99997无= 299998= 299998【提示】假设你的程序需要用到较大的栈空间这通常意味着需要较深层数的递归，请务 必认真阅读选手名目下的文档 running/stack.pdf ，以了解在最终评测时栈空间的限制与在当前工作环境下调整栈空间限制的方法。第一

14、试第22 届全国青少年信息学奥林匹克联赛提高组复赛换教室classroom换教室classroom)【问题描述】对于刚上大学的牛牛来说，他面临的第一个问题是如何依据实际状况申请适宜的 课程。在可以选择的课程中，有 2n 节课程安排在 n 个时间段上。在第 i ( 1 i n )个时间段上，两节内容一样的课程同时在不同的地点进展，其中，牛牛预先被安排在教室ici 上课，而另一节课程在教室 d进展。在不提交任何申请的状况下，学生们需要按时间段的挨次依次完成全部的 n 节安排好的课程。假设学生想更换第 i 节课程的教室，则需要提出申请。假设申请通过，学i生就可以在第 i 个时间段去教室 d上课，否则

15、照旧在教室 di 上课。由于更换教 室的需求太多，申请不愿定能获得通过。通过计算，牛牛觉察申请i更换第 i 节课程的教室时，申请被通过的概率是一个己知的实数 k ，并且对于不同课程的申请，被通过的概率是相互独立的。学校规定，全部的申请只能在学期开头前一次性提交，并且每个人只能选择至多m节课程进展申请。这意味着牛牛必需一次性打算是否申请更换每节课的教室，而 不能依据某些课程的申请结果来打算其他课程是否申请；牛牛可以申请自己最期望更换教室的m 门课程，也可以不用完这m 个申请的时机，甚至可以一门课程都不申请。由于不同的课程可能会被安排在不同的教室进展，所以牛牛需要利用课间时间从一间教室赶到另一间教

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

17、个学期内的时间段的数量； m 表示牛牛最多可以申请更换多少节课程的教室； v 表示牛牛学校里教室的数量； e 表示牛牛的学校里道路的数量。其次行n 个正整数，第i1 i n 个正整数表示ci，即第i 个时间段牛牛被安 排上课的教室；保证1 ci v 。第三行n 个正整数，第 i 1 i n 个正整数表示 di ，即第i 个时间段另一间上同样课程的教室；保证1 di v 。第9 页共12 页第一试第22 届全国青少年信息学奥林匹克联赛提高组复赛换教室classroom第四行n 个实数，第i1 i n 个实数表示k，即牛牛申请在第i 个时间段更 换i教室获得通过的概率。保证0 ki 1 。接下来e

18、 行，每行三个正整数aj，bj，wj，表示有一条双向道路连接教室aj , bj，通过这条道路需要消耗的体力值是wj ；保证1 aj, bj v ，1 wj 100 。保证1 n 2023 ，0 m 2023 ，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 说明】全部可行的申请方案和期望收益如下表：第10 页共12 页第22 届全国青少年信息学奥林匹克联赛提高组复赛第一试换教室classroom无0.2820.20无0.8830.54无0.581、20.16410.64420.040无0.1681、30.40申请更换教室的 申请通过的时间时间段无消灭的概率消耗的体力值 消耗的体力值的期望8.01段无11.

20、00.8844.826.436.01、24.481、313无2、323无0.40.10.10.10.10.40.444840482.82、35.2【样例 2】见选手名目下的classroom/classroom2.in 与classroom/classroom2.ans。【提示】1. 道路中可能会有 多条双向道路连接一样的两间教室 。也有可能有道路两端连接的是同一间教室。2. 请留意区分n, m, v, e 的意义，n 不是教室的数量，m 不是道路的数量。第1页共12 页第22 届全国青少年信息学奥林匹克联赛提高组复赛第一试换教室classroom【子任务】32 1 1004 2 3009 1

21、0 1 2010 2 10011 10 30012 0 2013 20 114 215 2016 017 300 1第12 页共12 页测试点12n 1m 1 0v 300 20特别性质1特别性质25678 3 0 1 2 0 20 100 300 100 300 20 100 300 2022232425 2023 2 100 2023 300特别性质1：图上任意两点a，iiiba bi 间，存在一条消耗体力最少的路径只18 219 30020 021 1包含一条道路。特别性质2：对于全部的1 i n ，ki = 1 。第22 届全国青少年信息学奥林匹克联赛CCF-NOIP-2023提高组复

22、赛其次试竞赛时间： 2023 年11 月20日 8:30 12:00题目名称组合数问题蚯蚓生气的小鸟题目类型传统型传统型传统型名目problemearthwormangrybirds可执行文件名problemearthwormangrybirds输入文件名problem.inearthworm.inangrybirds.in输出文件名problem.outearthworm.outangrybirds.out每个测试点时限1.0 秒1.0 秒2.0 秒内存限制512 MB512 MB512 MB测试点数目202020每个测试点分值555提交源程序文件名对于C+ 语言对于C 语言对于Pascal

23、 语言编译选项problem.cpp problem.c problem.pasearthworm.cpp earthworm.c earthworm.pasangrybirds.cpp angrybirds.c angrybirds.pas对于C+ 对于C对于Pascal语言语言语言-lm-lm-lm-lm-lm-lm留意事项：1. 文件名程序名和输入输出文件名必需使用英文小写。2. 除非特别说明，结果比较方式均为无视行末空格及文末回车的全文比较。3. C/C+中函数 main 的返回值类型必需是 int，程序正常完毕时的返回值必需 是0。4. 全国统一评测时承受的机器配置为： CPU AM

24、D Athlon(tm) II x2 240 processor， 2.8GHz，内存4G，上述时限以此配置为准。5. 只供给Linux 格式附加样例文件。6. 评测在NOI Linux 下进展。7. 编译时不翻开任何优化选项。组合数问题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

25、(i, m) 有多少对(i, j)满足是k 的倍数。i【输入格式】从文件problem.in 中读入数据。第【输出格式】一来有两t 行，每行一个整数代表全部的 0 i n, 0 j min (i, m) 中有多少对(i, j) 满足是下行 输出到文件problem.out 中。t个k 的倍数。整每行数【样例 1 输入】行t1 2个两,3 3整k数【样例 1 输出】，1n其,中m【样例 1 说明】t在，全部可能的状况中，只有= 2 是 2 的倍数。 代其表中该测n试, 点 总m第22 届全国青少年信息学奥林匹克联赛提高组复赛其次试 组合数问题problem【样例 2 输入】2 54 56 7【样

26、例 2 输出】07【子任务】测试点nmkt1 3 3= 2= 12= 3 1043 7 7= 4= 14= 5 1045 10 10= 6= 16= 7 1047 20 100= 8= 18= 9 1049 25 2023= 10= 110= 11 10411 60 20= 12= 112= 13 1041314 100 25= 14= 15= 1 10415 60= 16= 116= 17 1041718 2023 100= 18= 19= 1 10419 2023= 20= 120= 21 104第 3 页页共 11第22 届全国青少年信息学奥林匹克联赛提高组复赛其次试蚯蚓earthwor

27、m蚯蚓 e a r t h w o r m)【问题描述】此题中，我们将用符号LcJ 表示对c 向下取整，例如：L3.0J =L3.1J =L3.9J = 3。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没方法，蛐蛐国王只好去请神 刀手来帮他们消灭蚯蚓。蛐每一秒，神刀手会在全部的蚯蚓中，准确地找到最长的那一只如有多个则任选一个 蛐将其切成两半。神刀手切开蚯蚓的位置由常数 p 是满足0 p 1 的有理数打算，设这只蚯蚓长度为x ，神刀手会将其切成两只长度分别为 LpxJ 和x LpxJ 的蚯蚓。特别地，如国果这两个数的其中一个等于0 ，则这个长度为0 的蚯蚓也会被保存。此 外，除了刚刚产生的里

28、两现只 蛐蛐国王知道这样不是长期之计，由于蚯蚓不仅会越来越多，还会越来越长。蛐蛐在国共王打算求助于一位有着洪荒之力的惊奇人物，但是救兵还需要 m 秒才能到来 . m 为蚯非有负整数蛐蛐国王期望知道这m 秒内的战况。蚓 具体来说，他期望知道：l，nml其 m只余 秒蛐蛐国王固然知道怎么做啦!但是他想考考你.蚯 内秒蚓 ，后【的 输每，入格式】长 一所n度 秒有从文件earthworm.in 中读入数据。都 被蚯 为会 蚓切 正增 的断第 4 页共 11页第22 届全国青少年信息学奥林匹克联赛提高组复赛其次试蚯蚓earthworm第一行包含六个整数n, m, q, u, v, t ，其中：n, m

29、, q 的意义见【问题描述】；u, v, t 均 为正第 5 页页共 11整 其次行包含n 个非负整数，为a , a12数, . . . , an，即初始时n 只蚯蚓的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。你； 保证1 n 105，0 m 7 106，0 u v 109，0 q 200 ，1 t 71 ，需0 ai 108 。要自己【输出格式】计p第一行输出个整数，按时间挨次，依次输出第t 秒，第2t 秒，第3t 秒，被切算 输出到文件earthworm.out=断蚯蚓在被切断前的长度。u/v 保证0u；t 是输出参数，其含义将会在【输出格式】中解释。其次行输出个整数，输出 m秒

30、后蚯蚓的长度：需要按从大到小的挨次，依次输出排名第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 说明】在神刀手到来前：3 只蚯蚓的长度为3,3,2。1 秒后：一只长度为 3 的蚯蚓被切成了两只长度分别为 1 和 2 的蚯蚓，其余蚯蚓的长度增加了 1。最终 4 只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。2

31、 秒后：一只长度为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,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 秒内

32、被切断的蚯蚓的长度依次为 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第22 届全国青少年信息学奥林匹克联赛提高组复赛其次试蚯蚓earthworm【样例 2 输出】4 4 56 5 4 3 2【样例 2 说明】这个数据中只有t = 2 与上个数据不同。只需在每行都改为每两个数输出一个数即可。虽然第一行最终有一个6 没有被输出，但是其次行照旧要重从其次个数再开头输出。【样例 3 输入】3 7 1 1 3 93 3 2【样例 3 输出】2【样例 3 说明】这个数据中只有t = 9 与上个数

33、据不同。留意第一行没有数要输出，但也要输出一个空行。【子任务】l 测试点1 3 满足m = 0 。l 测试点4 7 满足n, m 1, 000 。l 测试点8 14 满足q = 0 ，其中测试点8 9 还满足m 105 。l 测试点15 18 满足m 3 105 。l 测试点19 20没有特别的商定，参见原始的数据范围。第 6 页页共 11l 测试点1 12 ，15 16还满足 v 2 ，这意味着 u, v 的唯一可能的取值是 u =1, v = 2 ，即p = 0.5 。这可能会对解决问题有特别的帮助。每个测试点的具体数据范围见下表。测试点nmtaivq= 0 2 200= 0 109 2

34、200 1091= 12= 103= 03= 1054= 1= 15= 103= 1036= 1 1067= 1038= 5 104= 5 1049= 105= 210= 2 106= 21111213= 105= 2.5 106= 3.5 106= 5 106= 26= 36= 51 10714= 7 106= 7115= 5 104= 5 106= 116= 1.5 106= 217= 105= 3 10818= 105= 3 105= 419= 3.5 106= 3620= 7 106= 71其次试生气的小鸟angrybirds第22 届全国青少年信息学奥林匹克联赛提高组复赛生气的小鸟

35、a n g r y b ir d s)【问题描述】Kiana 最近沉迷于一款惊奇的玩耍无法自拔。简洁来说，这款玩耍是在一个平面上进展的。有一架弹弓位于(0, 0) 处，每次Kiana 可以用它向第一象限放射一只红色的小鸟，第 8 页页共 11小鸟们的飞行轨迹均为形如y = ax2 须满足a 0。+ bx 的曲线，其中a, b 是Kiana 指定的参数，且必当小鸟落回地面即x 轴时，它就会瞬间消逝。在玩耍的某个关卡里，平面的第一象限中有n 只绿色的小猪，其中第 i 只小猪所在的坐标为(xi, yi)。假设某只小鸟的飞行轨迹经过了(xi, yi) ，那么第i 只小猪就会被消灭掉，同时小鸟将会沿着原

36、先的轨迹连续飞行；假设一只小鸟的飞行轨迹没有经过(xi, yi) ，那么这只小鸟飞行的全过程就不会对第i 只小猪产生任何影响。例如，假设两只小猪分别位于(1, 3) 和(3, 3) ，Kiana 可以选择放射一只飞行轨迹为y =x2 + 4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。而这个玩耍的目的，就是通过放射小鸟消灭全部的小猪。这款惊奇玩耍的每个关卡对Kiana 来说都很难，所以 Kiana 还输入了一些惊奇的指令，使得自己能更轻松地完成这个玩耍。这些指令将在【输入格式】中详述。假设这款玩耍一共有T 个关卡，现在Kiana 想知道，对于每一个关卡，至少需要放射多少只小鸟才能消灭全部的小

37、猪。由于她不会算，所以期望由你告知她。【输入格式】从文件angrybirds.in 中读入数据。第一行包含一个正整数T ，表示玩耍的关卡总数。下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整数 n, m ，分别表示该关卡中的小猪数量和 Kiana 输入的惊奇指令类型。接下来的 n 行中，第i 行包含两个正实数xi, yi ，表示第i 只小猪坐标为(xi, yi) 。数据保证同一个关卡中不存在两只坐标完全一样的小猪。假设 m = 0 ，表示Kiana 输入了一个没有任何作用的指令。假设 m = 1 ，则这个关卡将会满足：至多用n/3 +1只小鸟即可消灭全部小猪。假设 m = 2 ，

38、则这个关卡将会满足：确定存在一种最优解，其中有一只小鸟消灭了至少 Ln/3J 只小猪。保证1 n 18 ，0 m 2 ，0 xi,yi 10 ，输入中的实数均保存到小数点后两位。其次试生气的小鸟angrybirds第22 届全国青少年信息学奥林匹克联赛提高组复赛上文中，符号c 和LcJ 分别表示对c 向上取整和向下取整，例如：2.1 = 2.9 =3.0 = L3.0J = L3.1J = L3.9J = 3 。【输出格式】输出到文件 angrybirds.out 中。对每个关卡依次输出一行答案。输出的每一行包含一个正整数，表示相应的关卡中，消灭全部小猪最少需要的小鸟数量。【样例 1 输入】22 01.00 3.003.00 3.005 21.00 5.002.00 8.003.00 9.004.