万卷网

NOIP普及组

万卷网> 考级竞赛> 信息学奥赛> NOIP普及组

NOIP普及组

更新时间： 2023-08-26 20:36:18 试题数量： 535

我的练习

顺序练习

随机练习

章节练习

错题练习

题库预览

判断题输入的字符串只能由小写字母或大写字母组成。

简答题数字游戏【问题描述】小K同学向小P同学发送了一个长度为8的 01字符串来玩数字游戏，小P 同学想要知道字符串中究竟有多少个1。注意：01字符串为每一个字符是0或者1的字符串，如“101”(不含双引号)为一个长度为3的01字符串。【输入格式】输入文件名为number in。输入文件只有一行，一个长度为8的01字符串s。【输出格式】输出文件名为number.out。输出文件只有一行，包含一个整数，即01字符串中字符1 的个数。【输入输出样例1】【输入输出样例1说明】该01字符串中有2个字符1。【输入输出样例2】【输入输出样例2说明】该01字符串中有8个字符1。【数据规模与约定】对于20%的数据，保证输入的字符全部为0。对于100%的数据，输入只可能包含字符0和字符1,字符串长度固定为8。

简答题纪念品【问题描述】小伟突然获得一种超能力，他知道未来T天N种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。每天，小伟可以进行以下两种交易无限次：1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；2. 卖出持有的任意一个纪念品，以当日价格换回金币。每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。T天之后，小伟的超能力消失。因此他一定会在第T天卖出所有纪念品换回金币。小伟现在有M枚金币，他想要在超能力消失后拥有尽可能多的金币。【输入格式】输入文件名为souvenir . in。第一行包含三个正整数T,N,M,相邻两数之间以一个空格分开，分别代表未来天数 T,纪念品数量N,小伟现在拥有的金币数量M。接下来T行，每行包含N个正整数，相邻两数之间以一个空格分隔。第i行的N个正整数分别为Pi1,Pi2, …… ,Pin,其中Pi,j表示第i天第j种纪念品的价格。【输出格式】输出文件名为souvenir . out。输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。【输入输出样例1】【输入输出样例1说明】最佳策略是：第二天花光所有100枚金币买入5个纪念品1;第三天卖出5个纪念品1,获得金币125枚；第四天买入6个纪念品1,剩余5枚金币；第六天必须卖出所有纪念品换回300枚金币，第四天剩余5枚金币，共305枚金币。超能力消失后，小伟最多拥有305枚金币。【输入输出样例2】【输入输出样例2说明】最佳策略是：第一天花光所有金币买入10个纪念品1;第二天卖出全部纪念品1得到150枚金币并买入8个纪念品2和1个纪念品3,剩余1枚金币；第三天必须卖出所有纪念品换回216枚金币，第二天剩余1枚金币，共217枚金币。超能力消失后，小伟最多拥有217枚金币。【数据规模与约定】对于10%的数据，T=1。对于30%的数据，T≤4,N≤4,M≤100,所有价格10≤Pij≤100。另有15%的数据，T≤100,N=1。另有15%的数据，T=2,N≤100。对于100%的数据，T≤100,N≤100,M≤,所有价格1≤Pij≤10⁴,数据保证任意时刻，小明手上的金币数不可能超过10⁴。

简答题公交换乘【问题描述】著名旅游城市B市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：1.在搭乘一次地铁后可以获得一张优惠票，有效期为45分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于45分钟，即：tbus-tsubway≤452. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗?【输入格式】输入文件名为transfer . in。输入文件的第一行包含一个正整数n,代表乘车记录的数量。接下来的n行，每行包含3个整数，相邻两数之间以一个空格分隔。第i行的第1个整数代表第i条记录乘坐的交通工具，0代表地铁，1代表公交车；第2个整数代表第i条记录乘车的票价pricei;第三个整数代表第i条记录开始乘车的时间ti (距0时刻的分钟数)。我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。【输出格式】输出文件名为transfer . out。输出文件有一行，包含一个正整数，代表小轩出行的总花费【输入输出样例 1】【输入输出样例1说明】第一条记录，在第3分钟花费10元乘坐地铁。第二条记录，在第46分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。第三条记录，在第50分种花费12元乘坐地铁。第四条记录，在第96分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过45 分钟，所以优惠票已失效，花费3元乘坐公交车。第五条记录，在第110分钟花费5元乘坐地铁。第六条记录，在第135分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为6元，高于第五条记录中地铁的票价5元，所以不能使用优惠票，花费6元乘坐公交车。总共花费36元。【输入输出样例2】【输入输出样例2说明】第一条记录，在第1分钟花费5元乘坐地铁。第二条记录，在第16分钟花费20元乘坐地铁。第三条记录，在第23分钟花费7元乘坐地铁。第四条记录，在第31分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。第五条记录，在第38分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。第六条记录，在第68分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。总共花费32元。【数据规模与约定】

简答题加工零件【问题描述】凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有n位工人，工人们从1～n编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。如果x号工人想生产一个被加工到第L(L>1)阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要生产一个被加工到第L- 1阶段的零件(但x号工人自己无需生产第L - 1阶段的零件)。如果x号工人想生产一个被加工到第1阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要为x号工人提供一个原材料。轩轩是 1 号工人。现在给出q张工单，第i张工单表示编号为ai的工人想生产一个第Li阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来!【输入格式】输入文件名为work.in。第一行两个正整数n,m和q,分别表示工人的数目、传送带的数目和工单的数目。接下来m行，每行两个正整数u和v,表示编号为u和v的工人之间存在一条零件传输带。保证u≠v。接下来q行，每行两个正整数a和L,表示编号为a的工人想生产一个第L阶段的零件。【输出格式】输出文件名为work . out。共q行，每行一个字符串“Yes”或者“No”。如果按照第i张工单生产，需要编号为 1的轩轩提供原材料，则在第i行输出“Yes”;否则在第i行输出“No”。注意输出不含引号。【输入输出样例 1】【输入输出样例1说明】编号为1的工人想生产第1阶段的零件，需要编号为2的工人提供原材料。编号为2的工人想生产第1阶段的零件，需要编号为1和3的工人提供原材料。编号为3的工人想生产第1阶段的零件，需要编号为2的工人提供原材料。编号为1的工人想生产第2阶段的零件，需要编号为2的工人生产第1阶段的零件，需要编号为1和3的工人提供原材料。编号为2的工人想生产第2阶段的零件，需要编号为1和3的工人生产第1阶段的零件，他/她们都需要编号为2的工人提供原材料。编号为3的工人想生产第2阶段的零件，需要编号为2的工人生产第1阶段的零件，需要编号为1和3的工人提供原材料。【输入输出样例2】【输入输出样例2说明】编号为1的工人想生产第1阶段的零件，需要编号为2和5的工人提供原材料。编号为1的工人想生产第2阶段的零件，需要编号为2和5的工人生产第1阶段的零件，需要编号为1,3,4 的工人提供原材料。编号为1的工人想生产第3阶段的零件，需要编号为2和5的工人生产第2阶段的零件，需要编号为1,3,4的工人生产第1阶段的零件，需要编号为2,3,4,5 的工人提供原材料。编号为1的工人想生产第4阶段的零件，需要编号为2和5的工人生产第3阶段的零件，需要编号为1,3,4的工人生产第2阶段的零件，需要编号为2,3,4,5 的工人生产第1阶段的零件，需要全部工人提供原材料。编号为1的工人想生产第5阶段的零件，需要编号为2和5的工人生产第4阶段的零件，需要编号为1,3,4的工人生产第3阶段的零件，需要编号为2,3,4,5 的工人生产第2阶段的零件，需要全部工人生产第1阶段的零件，需要全部工人提供原材料。【数据规模与约定】共20个测试点。

简答题对称二叉树【问题描述】一棵有点权的有根树如果满足以下条件，则被轩轩称为对称二叉树：1. 二叉树；2. 将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。下图中节点内的数字为权值，节点外的 id表示节点编号。现在给出一棵二叉树，希望你找出它的一棵子树，该子树为对称二叉树，且节点数最多。请输出这棵子树的节点数。注意：只有树根的树也是对称二叉树。本题中约定，以节点 T 为子树根的一棵“子树”指的是：节点 T 和它的全部后代节点构成的二叉树。【输入格式】输入文件名为 tree.in。第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1~n，其中节点1 是树根。第二行 n 个正整数，用一个空格分隔，第 i 个正整数 vi 代表节点 i 的权值。接下来 n 行，每行两个正整数 li, ri，分别表示节点 i 的左右孩子的编号。如果不存在左 / 右孩子，则以 −1 表示。两个数之间用一个空格隔开。【输出格式】输出文件名为 tree.out。输出文件共一行，包含一个整数，表示给定的树的最大对称二叉子树的节点数。【输入输出样例 1】【输入输出样例 1 说明】最大的对称二叉子树为以节点 2 为树根的子树，节点数为 1。【输入输出样例 2】【输入输出样例 2 说明】最大的对称二叉子树为以节点 7 为树根的子树，节点数为 3。【数据规模与约定】共 25 个测试点。vi ≤ 1000。测试点 1~3，n ≤ 10，保证根结点的左子树的所有节点都没有右孩子，根结点的右子树的所有节点都没有左孩子。测试点 4~8，n ≤ 10。测试点 9~12，n ≤ 10^5，保证输入是一棵“满二叉树”。测试点 13~16，n ≤ 10^5，保证输入是一棵“完全二叉树”。测试点 17~20，n ≤ 10^5，保证输入的树的点权均为 1。测试点 21~25，n ≤ 10^6。本题约定：层次：节点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一节点的层次等于其父亲节点的层次加 1。树的深度：树中节点的最大层次称为树的深度。满二叉树：设二叉树的深度为 h，且二叉树有 2^h − 1 个节点，这就是满二叉树。完全二叉树：设二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

简答题标题统计【问题描述】凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。【输入格式】输入文件名为 title.in。输入文件只有一行，一个字符串 s。【输出格式】输出文件名为 title.out。输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。【输入输出样例 1】【输入输出样例 1 说明】标题中共有 3 个字符，这 3 个字符都是数字字符。【输入输出样例 2】【输入输出样例 2 说明】标题中共有 5 个字符，包括 1 个大写英文字母，1 个小写英文字母和 2 个数字字符，还有 1 个空格。由于空格不计入结果中，故标题的有效字符数为 4 个。【数据规模与约定】规定 |s| 表示字符串 s 的长度（即字符串中的字符和空格数）。对于 40% 的数据，1 ≤ |s| ≤ 5，保证输入为数字字符及行末换行符。对于 80% 的数据，1 ≤ |s| ≤ 5，输入只可能包含大、小写英文字母、数字字符及行末换行符。对于 100% 的数据，1 ≤ |s| ≤ 5，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。

简答题龙虎斗【问题描述】轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 n个兵营（自左至右编号 1 ~ n），相邻编号的兵营之间相隔 1 厘米，即棋盘为长度为n − 1 厘米的线段。i 号兵营里有 ci 位工兵。下面图 1 为 n = 6 的示例：轩轩在左侧，代表“龙”；凯凯在右侧，代表“虎”。他们以 m 号兵营作为分界，靠左的工兵属于龙势力，靠右的工兵属于虎势力，而第 m 号兵营中的工兵很纠结，他们不属于任何一方。一个兵营的气势为：该兵营中的工兵数 × 该兵营到 m 号兵营的距离；参与游戏一方的势力定义为：属于这一方所有兵营的气势之和。下面图 2 为 n = 6, m = 4 的示例，其中红色为龙方，黄色为虎方：游戏过程中，某一刻天降神兵，共有 s1 位工兵突然出现在了 p1 号兵营。作为轩轩和凯凯的朋友，你知道如果龙虎双方气势差距太悬殊，轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续，你需要选择一个兵营 p2，并将你手里的 s2 位工兵全部派往兵营 p2，使得双方气势差距尽可能小。注意：你手中的工兵落在哪个兵营，就和该兵营中其他工兵有相同的势力归属（如果落在 m 号兵营，则不属于任何势力）。【输入格式】输入文件名为 fight.in。输入文件的第一行包含一个正整数 n，代表兵营的数量。接下来的一行包含 n 个正整数，相邻两数之间以一个空格分隔，第 i 个正整数代表编号为 i 的兵营中起始时的工兵数量 ci。接下来的一行包含四个正整数，相邻两数间以一个空格分隔，分别代表 m, p1, s1, s2。【输出格式】输出文件名为 fight.out。输出文件有一行，包含一个正整数，即 p2，表示你选择的兵营编号。如果存在多个编号同时满足最优，取最小的编号。【输入输出样例 1】【输入输出样例 1 说明】见问题描述中的图 2。双方以 m = 4 号兵营分界，有 s1 = 5 位工兵突然出现在 p1 = 6 号兵营。龙方的气势为：2 × (4 − 1) + 3 × (4 − 2) + 2 × (4 − 3) = 14虎方的气势为：2 × (5 − 4) + (3 + 5) × (6 − 4) = 18当你将手中的 s2 = 2 位工兵派往 p2 = 2 号兵营时，龙方的气势变为：14 + 2 × (4 − 2) = 18此时双方气势相等。【输入输出样例 2】【输入输出样例 2 说明】双方以 m = 5 号兵营分界，有 s1 = 1 位工兵突然出现在 p1 = 4 号兵营。龙方的气势为：1 × (5 − 1) + 1 × (5 − 2) + 1 × (5 − 3) + (1 + 1) × (5 − 4) = 11虎方的气势为：16 × (6 − 5) = 16当你将手中的 s2 = 1 位工兵派往 p2 = 1 号兵营时，龙方的气势变为：11 + 1 × (5 − 1) = 15此时可以使双方气势的差距最小。【数据规模与约定】1 < m < n, 1 ≤ p1 ≤ n。对于 20% 的数据，n = 3, m = 2, ci = 1, s1, s2 ≤ 100。另有 20% 的数据，n ≤ 10, p1 = m, ci = 1, s1, s2 ≤ 100。对于 60% 的数据，n ≤ 100, ci = 1, s1, s2 ≤ 100。对于 80% 的数据，n ≤ 100, ci, s1, s2 ≤ 100。对于 100% 的数据，n ≤ 105, ci, s1, s2 ≤ 10^9。

简答题摆渡车【问题描述】有 n 名同学要乘坐摆渡车从人大附中前往人民大学，第 i 位同学在第 ti 分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费 m 分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？注意：摆渡车回到人大附中后可以即刻出发。【输入格式】输入文件名为 bus.in。第一行包含两个正整数 n，m，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。第二行包含 n 个正整数，相邻两数之间以一个空格分隔，第 i 个非负整数 ti 代表第 i 个同学到达车站的时刻。【输出格式】输出文件名为 bus.out。输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。【输入输出样例 1】【输入输出样例 1 说明】同学 1 和同学 4 在第 3 分钟开始等车，等待 0 分钟，在第 3 分钟乘坐摆渡车出发。摆渡车在第 4 分钟回到人大附中。同学 2 和同学 3 在第 4 分钟开始等车，等待 0 分钟，在第 4 分钟乘坐摆渡车出发。摆渡车在第 5 分钟回到人大附中。同学 5 在第 5 分钟开始等车，等待 0 分钟，在第 5 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 0。【输入输出样例 2】【输入输出样例 2 说明】同学 3 在第 1 分钟开始等车，等待 0 分钟，在第 1 分钟乘坐摆渡车出发。摆渡车在第 6 分钟回到人大附中。同学 4 和同学 5 在第 5 分钟开始等车，等待 1 分钟，在第 6 分钟乘坐摆渡车出发。摆渡车在第 11 分钟回到人大附中。同学 1 在第 11 分钟开始等车，等待 2 分钟；同学 2 在第 13 分钟开始等车，等待 0 分钟。他/她们在第 13 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 4。可以证明，没有总等待时间小于 4 的方案。【数据规模与约定】

简答题信息学NOIP普及组编程试题

简答题信息学NOIP普及组编程试题

简答题成绩【问题描述】牛牛最近学习了 C++入门课程，这门课程的总成绩计算方法是：总成绩 = 作业成绩 × 20% + 小测成绩 × 30% + 期末考试成绩 × 50%牛牛想知道，这门课程自己最终能得到多少分。【输入格式】输入文件名为 score.in。输入文件只有 1 行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是 100 分。【输出格式】输出文件名为 score.out。输出文件只有 1 行，包含一个整数，即牛牛这门课程的总成绩，满分也是 100 分。【输入输出样例 1】【输入输出样例 1 说明】牛牛的作业成绩是 100 分，小测成绩是 100 分，期末考试成绩是 80 分，总成绩是 100 × 20% + 100 × 30% + 80 × 50% = 20 + 30 + 40 = 90。【输入输出样例 2】【输入输出样例 2 说明】牛牛的作业成绩是 60 分，小测成绩是 90 分，期末考试成绩是 80 分，总成绩是60 × 20% + 90 × 30% + 80 × 50% = 12 + 27 + 40 = 79。【数据说明】对于 30% 的数据，A = B = 0。对于另外 30% 的数据，A = B = 100。对于 100% 的数据， 0 ≤ A、B、C ≤ 100 且 A、B、C 都是 10 的整数倍。

简答题图书管理员【问题描述】图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。【输入格式】输入文件名为 librarian.in。输入文件的第一行，包含两个正整数 n 和 q，以一个空格分开，分别代表图书馆里书的数量和读者的数量。接下来的 n 行，每行包含一个正整数，代表图书馆里某本书的图书编码。接下来的 q 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆里读者的需求码的长度，第二个正整数代表读者的需求码。【输出格式】输出文件名为 librarian.out。输出文件有 q 行，每行包含一个整数，如果存在第 i 个读者所需要的书，则在第 i行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出-1。【输入输出样例 1】【输入输出样例 1 说明】第一位读者需要的书有 2123、1123、23，其中 23 是最小的图书编码。第二位读者需要的书有 2123、1123，其中 1123 是最小的图书编码。对于第三位，第四位和第五位读者，没有书的图书编码以他们的需求码结尾，即没有他们需要的书，输出-1。【数据规模与约定】对于 20%的数据，1 ≤ n ≤ 2。另有 20%的数据，q = 1。另有 20%的数据，所有读者的需求码的长度均为 1。另有 20%的数据，所有的图书编码按从小到大的顺序给出。对于 100%的数据，1 ≤ n ≤ 1,000，1 ≤ q ≤ 1,000，所有的图书编码和需求码均不超过 10,000,000。

简答题棋盘【问题描述】有一个m × m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。另外，你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？【输入格式】输入文件名为 chess.in。数据的第一行包含两个正整数 m，n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。接下来的 n 行，每行三个正整数 x，y，c，分别表示坐标为（x，y）的格子有颜色 c。其中 c=1 代表黄色，c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标为（1, 1），右下角的坐标为（m, m）。棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（1，1）一定是有颜色的。【输出格式】输出文件名为 chess.out。输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。【输入输出样例 1】【输入输出样例 1 说明】从（1，1）开始，走到（1，2）不花费金币从（1，2）向下走到（2，2）花费 1 枚金币从（2，2）施展魔法，将（2，3）变为黄色，花费 2 枚金币从（2，2）走到（2，3）不花费金币从（2，3）走到（3，3）不花费金币从（3，3）走到（3，4）花费 1 枚金币从（3，4）走到（4，4）花费 1 枚金币从（4，4）施展魔法，将（4，5）变为黄色，花费 2 枚金币，从（4，4）走到（4，5）不花费金币从（4，5）走到（5，5）花费 1 枚金币共花费 8 枚金币。【输入输出样例 2】【输入输出样例 2 说明】从（1，1）走到（1，2），不花费金币从（1，2）走到（2，2），花费 1 金币施展魔法将（2，3）变为黄色，并从（2，2）走到（2，3）花费 2 金币从（2，3）走到（3，3）不花费金币从（3，3）只能施展魔法到达（3，2），（2，3），（3，4），（4，3）而从以上四点均无法到达（5，5），故无法到达终点，输出－1【数据规模与约定】对于 30%的数据，1 ≤ m ≤ 5， 1 ≤ n ≤ 10。对于 60%的数据，1 ≤ m ≤ 20， 1 ≤ n ≤ 200。对于 100%的数据，1 ≤ m ≤ 100， 1 ≤ n ≤ 1,000。

简答题跳房子【问题描述】跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。跳房子的游戏规则如下：在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人，如果他花 g 个金币改进他的机器人，那么他的机器人灵活性就能增加 g，但是需要注意的是，每次弹跳的距离至少为 1。具体而言，当g < d时，他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1, d-g+2，…，d+g-2，d+g-1，d+g；否则（当g ≥ d时），他的机器人每次可以选择向右弹跳的距离为 1，2，3，…，d+g-2，d+g-1，d+g。现在小 R 希望获得至少 k 分，请问他至少要花多少金币来改造他的机器人。【输入格式】输入文件名为 jump.in。第一行三个正整数 n，d，k，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数之间用一个空格隔开。接下来 n 行，每行两个正整数xi, si，分别表示起点到第i个格子的距离以及第i个格子的分数。两个数之间用一个空格隔开。保证xi按递增顺序输入。【输出格式】输出文件名为 jump.out。共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分，输出-1。【输入输出样例 1】【输入输出样例 1 说明】花费 2 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 2，3，5，3，4，3，先后到达的位置分别为 2，5，10，13，17，20，对应 1, 2, 3, 5, 6, 7 这 6 个格子。这些格子中的数字之和 15 即为小 R 获得的分数。【输入输出样例 2】【输入输出样例 2 说明】由于样例中 7 个格子组合的最大可能数字之和只有 18 ，无论如何都无法获得 20 分。【数据规模与约定】本题共 10 组测试数据，每组数据 10 分。对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤2000, 1 ≤ xi, k ≤ 10^9, |si| < 10^5。对于第 1，2 组测试数据，n ≤ 10；对于第 3，4，5 组测试数据，n ≤ 500对于第 6，7，8 组测试数据，d = 1