（2021.8.15 更新）洛谷主题库试题提供以及反馈帖

工单反馈版

chen_zhe @ 2020-01-19 19:25:41

洛谷鼓励各位用户将大型比赛的试题或者洛谷上缺乏的模板题，在确认没有版权问题的情况下，提供给洛谷。但是因为此类贴子日益增多，严重影响了讨论版面，而且部分用户所提供的试题并不符合规定，故做出以下说明：

所谓的大型比赛，指的是国家或者地区级别的比赛（例如 USACO，POI，Baltic OI 等），或者大型的网络公开赛（例如 Codeplus 等），但是不包含例如校内的网络模拟赛之类的试题。
请注意，JOI 有关竞赛（包括 JOI open）原则上是不接受用户投题的。对于其它大型竞赛题目，如果测试点过多且单个测试点时间过长也有被拒绝的可能。如果您希望搬运这类比赛题，请提前咨询管理员。另外 USACO 的铜组也不接受用户投题。
对于模板题，其在现在的 OI 中，必须存在一定的实际意义，不能是非常生僻的，全网可能没有一个算法竞赛题涉及到相关知识点的算法或者数据结构。洛谷现决定根据 OI-Wiki 判断一个模板是否有存在的必要，即必须在 OI-Wiki 中有一个专门的页面。对于以前不符合此项要求的模板题，取消模板标签。同时，建议在造模板题之前先与管理员私信沟通好洛谷是否接受该模板。
贡献大型比赛的试题必须确保没有版权争议。为防止出现版权问题导致的不必要纠纷，供题时必须标注题目来源，搬运题目必须标注原题链接。若需搬运来自其他 Online Judge 的翻译题，必须确保没有任何版权问题的情况下，按照洛谷主题库题目规范所要求的格式以及对方 Online Judge 的版权要求进行搬运。若贡献明显有版权问题的题目，视情节严重程度处以警告/禁言/棕名/封号的惩罚。另外，对于比赛赛题，请一次性提交一场比赛中所有的题目。只有在题库中相应比赛的题目出现缺漏的时候才允许零散提交。特殊地，对于 COCI 题目，如果题库中只缺失 AB 两题，从现在起不再接受补充，但是对于整套提供的题目，仍然接受前两题。
贡献的题目需严格遵守洛谷主题库题目规范，请在贡献之前对照规范逐字逐句检查。特别地，所提供的试题中，若需要 spj，则相对较易的部分必须自行完成。若实在有困难才可以征集。具体尺度由管理进行评判。
在本讨论中，允许用户提供试题，要求用户至少达到绿勾级别。
贡献题目禁止单独开帖，请在此讨论下回复，若恶意浪费管理员时间，视情节严重程度处以警告/禁言/封号的惩罚。
原则上不收距今超过 20 年（含）的题目，如果题目具有特殊价值，可以联系管理员添加单题（而不是整套提供）

同时，对于已在洛谷主题库中但不符合洛谷主题目题目规范的题目，我们鼓励用户进行更正，但也至少要达到绿勾级别。要求更正后的题面严格遵守规范，同样回复在本讨论下，为了方便管理员，请将题面使用代码框```括起来。

若有发现难度标签明显有问题（即对于普及-以及以下的题目相差两个档次，或者对于提高-以及以上难度相差一个档次），欢迎大家提供建议。请在本楼回复题号和应当修正的难度。

为了提高管理员的审核效率，本贴禁止任何无意义回复，所有无意义回复均会被删除，行为恶劣者将会禁言，但是可以询问说明中的问题。若为修复题目问题，建议带上链接以增加效率。

请不要@管理员，会有管理员不定期来本帖处理。

by syksykCCC @ 2020-02-03 10:03:34

类型：试题提供

题目：[PA2014]Bohater

by u2004 @ 2020-02-03 10:19:25

类型：题面修改

题目：P1281 书的复制

题目：P2393 yyy loves Maths II

题目：P1803 凌乱的yyy / 线段覆盖

题目：P2370 yyy2015c01的U盘

题目：P2372 yyy2015c01挑战算周长

题目：P2396 yyy loves Maths VII

题目：P1855 榨取kkksc03

题目：P2650 弹幕考察

题目：P2651 添加括号III

题目：P2652 同花顺

by u2004 @ 2020-02-03 10:19:59

### 题目背景
大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出 $0$  $0$ 。

不过，已经修改数据，保证每个人都有活可干。

### 题目描述
现在要把 $m$ 本有顺序的书分给 $k$ 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

### 输入格式
第一行两个整数 $m$ ， $k$ ；（$k \le m \le 500$）

第二行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 本书的页数。

### 输出格式
共 $k$ 行，每行两个整数，第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。 $k$ 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

题目背景

大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出 0 0 。

不过，已经修改数据，保证每个人都有活可干。

题目描述

现在要把 m 本有顺序的书分给 k 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

输入格式

第一行两个整数 m ， k ；（k \le m \le 500）

第二行 m 个整数，第 i 个整数表示第 i 本书的页数。

输出格式

共 k 行，每行两个整数，第 i 行表示第 i 个人抄写的书的起始编号和终止编号。 k 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

by u2004 @ 2020-02-03 10:22:43

### 题目背景
上次蒟蒻 $\text{redbag}$ 可把 $\text{yyy}$ 气坏了， $\text{yyy}$ 说他只是小学生，蒟蒻 $\text{redbag}$ 这次不坑他了。

题目描述
 $\text{redbag}$ 给了 $\text{yyy}$ 很多个数，要 $\text{yyy}$ 计算这些数的和。必须要快， $\text{redbag}$ 只给了 $\text{yyy}$ $1$ 秒的时间！！！

### 输入格式

一行，很多个数。

### 输出格式

一行,一个实数(四舍五入精确到 $5$ 位小数)，表示这些数的和。

### 说明/提示

对于 $100\%$ 的数据,所有数 $ \le 233333333 $，保证在小数点后最多有 $6$ 位数,最多共有 $50000$ 个数。

题目背景

上次蒟蒻 \text{redbag} 可把 \text{yyy} 气坏了， \text{yyy} 说他只是小学生，蒟蒻 \text{redbag} 这次不坑他了。

题目描述

### 输入格式一行，很多个数。 ### 输出格式一行,一个实数(四舍五入精确到 $5$ 位小数)，表示这些数的和。 ### 说明/提示对于 $100\%$ 的数据,所有数 $ \le 233333333 $，保证在小数点后最多有 $6$ 位数,最多共有 $50000$ 个数。

by u2004 @ 2020-02-03 10:23:14

### 题目背景
快 $\text{noip}$ 了， $\text{yyy}$ 很紧张！

### 题目描述
现在各大 $\text{oj}$ 上有 $n$ 个比赛，每个比赛的开始、结束的时间点是知道的。

 $\text{yyy}$ 认为，参加越多的比赛， $\text{noip}$ 就能考的越好（假的）

所以，他想知道他最多能参加几个比赛。

由于 $\text{yyy}$ 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。

### 输入格式
第一行是一个整数 $n$  ，接下来n行每行是 $2$ 个整数 $a_{i}$ , $b_{i}$ ( $a_{i}<b_{i}$ )，表示比赛开始、结束的时间。

### 输出格式
一个整数最多参加的比赛数目。

### 说明/提示
对于 $20\%$ 的数据， $n \le 10$ ；

对于 $50\%$ 的数据， $n \le 1000$ ；

对于 $70\%$ 的数据， $n \le 10^{5}$ ；

对于 $100\%$ 的数据， $n \le 10^{6}$ ， $0 \le a_{i} < b_{i} \le 1000000$ 。

题目背景

快 \text{noip} 了， \text{yyy} 很紧张！

题目描述

现在各大 \text{oj} 上有 n 个比赛，每个比赛的开始、结束的时间点是知道的。

所以，他想知道他最多能参加几个比赛。由于 $\text{yyy}$ 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。 ### 输入格式第一行是一个整数 $n$ ，接下来n行每行是 $2$ 个整数 $a_{i}$ , $b_{i}$ ( $a_{i}<b_{i}$ )，表示比赛开始、结束的时间。 ### 输出格式一个整数最多参加的比赛数目。 ### 说明/提示对于 $20\%$ 的数据， $n \le 10$ ；对于 $50\%$ 的数据， $n \le 1000$ ；对于 $70\%$ 的数据， $n \le 10^{5}$ ；对于 $100\%$ 的数据， $n \le 10^{6}$ ， $0 \le a_{i} < b_{i} \le 1000000$ 。

by u2004 @ 2020-02-03 10:23:50

### 题目背景
在 $2020$ 年的某一天，我们的 $\text{yyy2015c01}$ 买了个高端$\text{U}$盘。

### 题目描述
你找 $\text{yyy2015c01}$ 借到了这个高端的$\text{U}$盘，拷贝一些重要资料，但是你发现这个$\text{U}$盘有一些问题：

1：这个$\text{U}$盘的传输接口很小，只能传输大小不超过 $L$ 的文件。

2：这个$\text{U}$盘容量很小，一共只能装不超过 $S$ 的文件。

但是你要备份的资料却有很多，你只能备份其中的一部分。

为了选择要备份哪些文件，你给所有文件设置了一个价值 $V_{i}$ ，你希望备份的文件总价值不小于 $p$。

但是很快你发现这是不可能的，因为 $\text{yyy2015c01}$ 的传输接口太小了，你只有花钱买一个更大的接口（更大的接口意味着可以传输更大的文件，但是购买它会花费更多的钱）。

注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在$\text{U}$盘中）,

你放在$\text{U}$盘中文件的总大小不能超过$\text{U}$盘容量。

现在问题来了：你想知道，在满足$\text{U}$盘中文件价值之和 不小于 $p$ 时，最小需要多大的接口。

### 输入格式

第 $1$ 行，三个正整数 $n$ , $p$, $S$ 分别表示文件总数，希望最小价值 $p$ ，硬盘大小。

接下来 $n$ 行

每行两个正整数 $W_{i}$ , $V_{i}$ 表示 第 $i$ 个文件的大小，和价值。

### 输出格式

一共 $1$ 行，输出一个正整数表示最小需要的接口大小。

如果无解输出 ```No Solution!``` 不含引号。

### 说明/提示

数据范围：

$1 ≤ n, Wi, S ≤ 1 000$

$1 ≤ Vi ≤ 1 000 000$

$1 ≤ p ≤ 1 000 000 000$

数据较小，请勿乱搞。

样例解释 $1$ ： (买一个大小为 $2$ 接口，把物品 $1$ 、$2$ 放进$\text{U}$盘)

样例解释 $2$ ：(买一个大小为 $500$ 的接口)

样例解释 $3$ ：（本来可以买大小为 $2$ 的接口，可是$\text{U}$盘容量放不下足够的文件）

如果数据出现疏漏，请联系出题人 [@ a710128](https://www.luogu.com.cn/user/2573)

向本题主人公 $\text{yyy2015c01}$ 同学致敬！

题目背景

在 2020 年的某一天，我们的 \text{yyy2015c01} 买了个高端\text{U}盘。

题目描述

你找 \text{yyy2015c01} 借到了这个高端的\text{U}盘，拷贝一些重要资料，但是你发现这个\text{U}盘有一些问题：

1：这个\text{U}盘的传输接口很小，只能传输大小不超过 L 的文件。

2：这个\text{U}盘容量很小，一共只能装不超过 S 的文件。

但是你要备份的资料却有很多，你只能备份其中的一部分。

为了选择要备份哪些文件，你给所有文件设置了一个价值 V_{i} ，你希望备份的文件总价值不小于 p。

但是很快你发现这是不可能的，因为 \text{yyy2015c01} 的传输接口太小了，你只有花钱买一个更大的接口（更大的接口意味着可以传输更大的文件，但是购买它会花费更多的钱）。

注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在\text{U}盘中）,

你放在\text{U}盘中文件的总大小不能超过\text{U}盘容量。

现在问题来了：你想知道，在满足\text{U}盘中文件价值之和不小于 p 时，最小需要多大的接口。

输入格式

第 1 行，三个正整数 n , p, S 分别表示文件总数，希望最小价值 p ，硬盘大小。

接下来 n 行

每行两个正整数 W_{i} , V_{i} 表示第 i 个文件的大小，和价值。

输出格式

一共 1 行，输出一个正整数表示最小需要的接口大小。

如果无解输出 No Solution! 不含引号。

说明/提示

数据范围：

1 ≤ n, Wi, S ≤ 1 000

1 ≤ Vi ≤ 1 000 000

1 ≤ p ≤ 1 000 000 000

数据较小，请勿乱搞。

样例解释 1 ： (买一个大小为 2 接口，把物品 1 、2 放进\text{U}盘)

样例解释 2 ：(买一个大小为 500 的接口)

样例解释 3 ：（本来可以买大小为 2 的接口，可是\text{U}盘容量放不下足够的文件）

如果数据出现疏漏，请联系出题人 @ a710128

向本题主人公 \text{yyy2015c01} 同学致敬！

by u2004 @ 2020-02-03 10:25:39

### 题目背景
 $\text{yyy2015c01}$ 快速的解决了问题，受到邻居们的赞许，高兴的回到家，把糖给了妈妈，吃了香喷喷的午饭，又睡了一个甜甜的午觉，感觉人生真美好。下午爸爸回到家，听说了 $\text{yyy2015c01}$ 帮老师及邻居们解决了难题，准备带她去游乐场玩她平日最喜欢玩的跳舞机作为奖励， $\text{yyy2015c01}$ 听了，兴奋的一蹦三尺高。

### 题目描述
游乐场里人头攒动，每台跳舞机前都围满了人，怎么办呢？人这么多，想玩上估计要等好久了， $\text{yyy2015c01}$ 左顾右盼，突然发现一台跳舞机前面没人， “哈哈，被我发现一台没人的，赶快去……”，结果到了面前才发现这台新机器的玩法与众不同，脚下的格子随机位置显示出很多的 "$\text{X}$" ，踩到一个格子，就要根据规则先算出它对应的周长，然后把正确周长输入机器，最后的胜利者还可以获得游乐城的免费游戏券一张， $\text{yyy2015c01}$ 心动了，小朋友们，你们可以帮助 $\text{yyy2015c01}$ 顺利拿到游戏券么？游戏规则如下：

新跳舞机踏板上有许多要分析的目标，由脚踩确定一个目标。目标边界的周长是一个有用的测量参数。编程任务：确定选中目标的周长。新跳舞机的踏板是一个矩形的网格，里面点 "$\text{.}$" ，表示空的地方；有大写字母 "$\text{X}$" ，表示目标的一部分。简单网格如下图所示：

**图片缺失**

方格中的一个 $\text{X}$ 是指一个完整的网格方形区域，包括其边界和目标本身。网格中心的 $\text{X}$ 与其边界上 $8$ 个方向的 $\text{X}$ 都是相邻的。任何两个相邻的 $\text{X}$ ，其网格方形区域在边界或拐角处是重叠的，所以它们的网格方形区域是相邻的。一个目标是由一系列相邻 $\text{X}$ 的网格方形区域连接起来构成的。在网格 $1$ 中，一个目标填充了全部网格；在网格 $2$ 中有两个目标，其中一个目标只占左下角的一个网格方形区域，其余的 $\text{X}$ 属于另一个目标。

 $\text{yyy2015c01}$ 总是能踩到一个 $\text{X}$ ，以选中包含该 $\text{X}$  的目标，记录脚踩时的坐标。行列号是从左上角开始，从 $1$ 开始编号的。一个有用的统计参数是目标的周长。 假定每个 $\text{X}$ 的每条边上有一个方形的单元。

目标中不会包含任何完全封闭的孔。

### 输入格式
共 $M+1$ 行，第一行为四个正整数 $M,N,X,Y$（中间用空格隔开），表示网格的大小为 $M$ 行，$N$ 列，且踩中网格的第 $X$ 行第 $Y$ 列方格。后面就是 $M$ 行，由字符 "$\text{.}$" 和 "$\text{X}$" 构成。

### 输出格式
共一行，表示选中目标的周长。

### 说明/提示
$M$（$1 \le M \le 20$）, $N$（$1 \le N \le 20$）, $X$（$1 \le X \le M$）,$Y$ （$1 \le Y \le N$）

题目背景

### 题目描述游乐场里人头攒动，每台跳舞机前都围满了人，怎么办呢？人这么多，想玩上估计要等好久了， $\text{yyy2015c01}$ 左顾右盼，突然发现一台跳舞机前面没人， “哈哈，被我发现一台没人的，赶快去……”，结果到了面前才发现这台新机器的玩法与众不同，脚下的格子随机位置显示出很多的 "$\text{X}$" ，踩到一个格子，就要根据规则先算出它对应的周长，然后把正确周长输入机器，最后的胜利者还可以获得游乐城的免费游戏券一张， $\text{yyy2015c01}$ 心动了，小朋友们，你们可以帮助 $\text{yyy2015c01}$ 顺利拿到游戏券么？游戏规则如下：新跳舞机踏板上有许多要分析的目标，由脚踩确定一个目标。目标边界的周长是一个有用的测量参数。编程任务：确定选中目标的周长。新跳舞机的踏板是一个矩形的网格，里面点 "$\text{.}$" ，表示空的地方；有大写字母 "$\text{X}$" ，表示目标的一部分。简单网格如下图所示： **图片缺失** 方格中的一个 $\text{X}$ 是指一个完整的网格方形区域，包括其边界和目标本身。网格中心的 $\text{X}$ 与其边界上 $8$ 个方向的 $\text{X}$ 都是相邻的。任何两个相邻的 $\text{X}$ ，其网格方形区域在边界或拐角处是重叠的，所以它们的网格方形区域是相邻的。一个目标是由一系列相邻 $\text{X}$ 的网格方形区域连接起来构成的。在网格 $1$ 中，一个目标填充了全部网格；在网格 $2$ 中有两个目标，其中一个目标只占左下角的一个网格方形区域，其余的 $\text{X}$ 属于另一个目标。 $\text{yyy2015c01}$ 总是能踩到一个 $\text{X}$ ，以选中包含该 $\text{X}$ 的目标，记录脚踩时的坐标。行列号是从左上角开始，从 $1$ 开始编号的。一个有用的统计参数是目标的周长。假定每个 $\text{X}$ 的每条边上有一个方形的单元。目标中不会包含任何完全封闭的孔。 ### 输入格式共 $M+1$ 行，第一行为四个正整数 $M,N,X,Y$（中间用空格隔开），表示网格的大小为 $M$ 行，$N$ 列，且踩中网格的第 $X$ 行第 $Y$ 列方格。后面就是 $M$ 行，由字符 "$\text{.}$" 和 "$\text{X}$" 构成。 ### 输出格式共一行，表示选中目标的周长。 ### 说明/提示 $M$（$1 \le M \le 20$）, $N$（$1 \le N \le 20$）, $X$（$1 \le X \le M$）,$Y$ （$1 \le Y \le N$）

by u2004 @ 2020-02-03 10:26:13

### 题目背景
 $\text{yyy}$ 对某些数字有着情有独钟的喜爱,他叫他们为幸运数字;然而他作死太多,所以把自己讨厌的数字成为"厄运数字"

### 题目描述
一群同学在和 $\text{yyy}$ 玩一个游戏

每次,他们会给 $\text{yyy}$  $n$ 张卡片,卡片上有数字,所有的数字都是"幸运数字",我们认为第i张卡片上数字是 $a_{i}$。

每次 $\text{yyy}$ 可以选择向前走 $a_{i}$ 步并且丢掉第 $i$ 张卡片

当他手上没有卡片的时候他就赢了

但是呢,大家对"厄运数字"的位置布置下了陷阱,如果 $\text{yyy}$ 停在这个格子上,那么他就输了

(注意:即使到了终点,但是这个位置是厄运数字,那么也输了)

现在,有些同学开始问:

 $\text{yyy}$ 有多大的概率会赢呢?

大家觉得这是个好问题

有人立即让 $\text{yyy}$ 写个程序

"电脑运行速度很快！ $24$ 的阶乘也不过就 $620448401733239439360000$ , $\text{yyy}$ 你快写个程序来算一算"

 $\text{yyy}$ 表示很无语,他表示他不想算概率,最多算算赢的方案数,而且是 $\mod 1,000,000,007$ 以后的值

大家都不会写程序,只好妥协

但是这时候 $\text{yyy}$ 为难了, $24!$ 太大了,要跑好长时间.

他时间严重不够!需要你的帮助!

由于 $\text{yyy}$ 人格分裂，某个数字可能既属于幸运数字又属于厄运数字。

### 输入格式
第一行 $n$ 

下面一行 $n$ 张卡片

第三行 $m$ 表示 $\text{yyy}$ 的厄运数字个数(最多 $2$ 个)

最后一行是 $m$ 个厄运数字

### 输出格式
方案数$\mod 1,000,000,007$

题目背景

### 题目描述一群同学在和 $\text{yyy}$ 玩一个游戏每次,他们会给 $\text{yyy}$ $n$ 张卡片,卡片上有数字,所有的数字都是"幸运数字",我们认为第i张卡片上数字是 $a_{i}$。每次 $\text{yyy}$ 可以选择向前走 $a_{i}$ 步并且丢掉第 $i$ 张卡片当他手上没有卡片的时候他就赢了但是呢,大家对"厄运数字"的位置布置下了陷阱,如果 $\text{yyy}$ 停在这个格子上,那么他就输了 (注意:即使到了终点,但是这个位置是厄运数字,那么也输了) 现在,有些同学开始问: $\text{yyy}$ 有多大的概率会赢呢? 大家觉得这是个好问题有人立即让 $\text{yyy}$ 写个程序 "电脑运行速度很快！ $24$ 的阶乘也不过就 $620448401733239439360000$ , $\text{yyy}$ 你快写个程序来算一算" $\text{yyy}$ 表示很无语,他表示他不想算概率,最多算算赢的方案数,而且是 $\mod 1,000,000,007$ 以后的值大家都不会写程序,只好妥协但是这时候 $\text{yyy}$ 为难了, $24!$ 太大了,要跑好长时间. 他时间严重不够!需要你的帮助! 由于 $\text{yyy}$ 人格分裂，某个数字可能既属于幸运数字又属于厄运数字。 ### 输入格式第一行 $n

下面一行 n 张卡片

第三行 m 表示 \text{yyy} 的厄运数字个数(最多 2 个)

最后一行是 m 个厄运数字

输出格式

方案数\mod 1,000,000,007

by u2004 @ 2020-02-03 10:26:33

### 题目描述
洛谷2的团队功能是其他任何 $\text{oj}$ 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 $\text{oj}$ 并高效率的完成训练计划。

为什么说是搭建 $\text{oj}$ 呢？为什么高效呢？

![](https://cdn.luogu.com.cn/upload/pic/1236.png)

因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！

你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！

你可以创建比赛！既可以是 $\text{oi}$ 赛制还可以是 $\text{acm}$ 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“$\text{x}$校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。

![](https://cdn.luogu.com.cn/upload/pic/1237.png)

值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。

洛谷的运营组决定，如果一名 $\text{oier}$ 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 $20$ 个或以上的成员，上传 $10$ 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 $\text{kkksc03}$ 的一些时间的同时消耗掉 $\text{kkksc03}$ 的一些金钱以满足自己的一个愿望。

 $\text{kkksc03}$ 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？

### 输入格式
第一行, $n,M,T$，表示一共有 $n$($n \le 100$) 个愿望， $\text{kkksc03}$ 的手上还剩 $M$($M \le 200$)元，他的暑假有 $T(T \le 200)$ 分钟时间。

第 $2$~$n+1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。

### 输出格式
一行，一个数，表示 $\text{kkksc03}$最多可以实现愿望的个数。

### 说明/提示
提示 第 $1$ , $2$ , $3$ , $6$ 个

题目描述

洛谷2的团队功能是其他任何 \text{oj} 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 \text{oj} 并高效率的完成训练计划。

为什么说是搭建 \text{oj} 呢？为什么高效呢？

因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！

你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！

你可以创建比赛！既可以是 \text{oi} 赛制还可以是 \text{acm} 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“\text{x}校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。

值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。

洛谷的运营组决定，如果一名 \text{oier} 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 20 个或以上的成员，上传 10 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 \text{kkksc03} 的一些时间的同时消耗掉 \text{kkksc03} 的一些金钱以满足自己的一个愿望。

### 输入格式第一行, $n,M,T$，表示一共有 $n$($n \le 100$) 个愿望， $\text{kkksc03}$ 的手上还剩 $M$($M \le 200$)元，他的暑假有 $T(T \le 200)$ 分钟时间。第 $2$~$n+1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。 ### 输出格式一行，一个数，表示 $\text{kkksc03}$最多可以实现愿望的个数。 ### 说明/提示提示第 $1$ , $2$ , $3$ , $6$ 个

by u2004 @ 2020-02-03 10:27:04

### 题目背景

$\text{zeromaker}$ 是个手残，但是他喜欢玩东方$\text{project}$ ，$\text{ex}$什么的最喜欢了。

### 题目描述
$\text{zeromaker}$ 对弹幕的视野控制有着深刻的研究。 每个弹幕在一段特定的时间内会出现在 $\text{zeromaker}$ 的视野内，除此之外的时间都在 $\text{zeromaker}$ 看不到的地方。在 $\text{zeromaker}$ 看来，视野内的弹幕数量越多，图就越难，因为这意味着 ￥@%。 现在，$\text{zeromaker}$ 想要评测这张图的难度，他已经知道了每个弹幕会在什么时候出现在视野内，他想知道，在一段时间内，总共有多少个弹幕出现在他的视野内过。

### 输入格式
第一行有两个整数 $n$ ， $m$ ,表示一共有 $n$ 个弹幕，而 $\text{zeromaker}$ 有 $m$ 个问题。

接下来 $n$ 行，每行两个数 $a$ ， $b$ ，表示这个弹幕a秒时出现在 $\text{zeromaker}$ 的视野内，出现了 $b$ 秒。 接下来 $m$ 行，每行两个整数 $x$ ， $y$ ，表示从 $x$ 秒开始，经过 $y$ 秒，其中有多少个弹幕出现过。

注意：查询区间为**左闭右闭**，弹幕出现区间为**左开右开**。

### 输出格式
$m$ 行，即对于 $\text{zeromaker}$ 提出的每个问题的答案。

### 说明/提示
【数据范围】

$30\%$ 的数据： $1 \le n,m \le 1000$。

$100\%$ 的数据： $1 \le n,m \le 100000$ ，$1 \le x,y,a,b \le \text{maxlongint}$。

题目背景

### 题目描述 $\text{zeromaker}$ 对弹幕的视野控制有着深刻的研究。每个弹幕在一段特定的时间内会出现在 $\text{zeromaker}$ 的视野内，除此之外的时间都在 $\text{zeromaker}$ 看不到的地方。在 $\text{zeromaker}$ 看来，视野内的弹幕数量越多，图就越难，因为这意味着￥@%。现在，$\text{zeromaker}$ 想要评测这张图的难度，他已经知道了每个弹幕会在什么时候出现在视野内，他想知道，在一段时间内，总共有多少个弹幕出现在他的视野内过。 ### 输入格式第一行有两个整数 $n$ ， $m$ ,表示一共有 $n$ 个弹幕，而 $\text{zeromaker}$ 有 $m$ 个问题。接下来 $n$ 行，每行两个数 $a$ ， $b$ ，表示这个弹幕a秒时出现在 $\text{zeromaker}$ 的视野内，出现了 $b$ 秒。接下来 $m$ 行，每行两个整数 $x$ ， $y$ ，表示从 $x$ 秒开始，经过 $y$ 秒，其中有多少个弹幕出现过。注意：查询区间为**左闭右闭**，弹幕出现区间为**左开右开**。 ### 输出格式 $m$ 行，即对于 $\text{zeromaker}$ 提出的每个问题的答案。 ### 说明/提示【数据范围】 $30\%$ 的数据： $1 \le n,m \le 1000$。 $100\%$ 的数据： $1 \le n,m \le 100000$ ，$1 \le x,y,a,b \le \text{maxlongint}$。