本文章记录了各种原创题（2021 级信息社团成员原创）。

A

题目描述

A 国有一条道路，长度为 $n$ 千米。道路可以看作一个数轴。现道路起点（原点，位置 $0$ ）有一粮仓，所贮粮食为 $m$ 千克；有一骆驼，可以运送粮食，最大载重为 $w$ 千克。现欲尽可能多地将粮食运送到道路终点（位置 $n$ ）。

在道路的整千米（整点）位置可以建立中转站，用于存放粮食，最多存放 $m$ 千克。你可以建立任意多中转站。骆驼可以前进，也可以后退；可以将任意多粮食（不能超过当前运载粮食数）放到中转站或终点，也可以在起点或中转站拿上任意多（同上）粮食。每行走一千米（不管前进还是后退），骆驼就要吃掉一千克粮食。也就是说，如果骆驼运送的粮食消耗尽了，那么骆驼就不能再行动了。

道路地形复杂。给定 $q$ 个闭区间，在区间内的整点不能建立中转站。现在，你肩负起运送粮食的重任。你需要求出最多可以运多少粮食到终点。

输入输出格式

输入的第一行为四个正整数，分别为 $n$ ， $m$ ， $w$ ， $q$ 。

接下来共 $q$ 行，每行两个数字 $l$ ， $r$ ，为题目描述所述区间 $[l,r]$ 。

输出一行一个正整数，为题目所求。

数据范围与来源

$n,m,w\le10^{10}$ ， $q\le10^5$ ，可用于建立中转站的整点不超过 $\sqrt{n}$ 。所有数均为正整数。

来自 zzy 的数学题改编。

B

题目描述

你住在 B 国的首都。B 国共 $n$ 个城市，编号为 $1\sim n$ ，其中 $1$ 号城市是首都。 $n-1$ 个双向道路将所有城市连通。有一天，你想开车周游 B 国。你想见见新鲜的城市，所以你希望到达距离首都尽量远的城市。两个城市间的距离被定义为两点间的最短路。

车的油箱容量为 $w$ 升，刚开始是满的。道路的长度不一，每在道路上行驶一千米，就要消耗一升汽油。刚开始，你携带的钱包里共 $m$ 元钱。每个城市都有一个加油站，在第 $i$ 个城市可以花费 $a_i$ 元钱加 $b_i$ 升汽油，可以选择加一次汽油（要求你当前钱数大于等于 $a_i$ ），也可以不加。加汽油后，将从你的钱包中扣除 $a_i$ 元钱。如果你加汽油后超过油箱容量，那么多出的汽油会被舍弃。如果你的油箱空了，那么你就不能再行动了。

在任意一个城市，你都可以选择任意一个与这个城市直接相连的城市作为下一个目的地。当你到达一个城市时，不管你是否到访过，你都获得一次加汽油的机会。

现在，需要让你求出可以到达的距离首都最远的城市。

输入输出格式

输入的第一行为三个正整数，分别为 $n$ ， $m$ ， $w$ 。

接下来共 $n-1$ 行，每行两个数字 $a_i$ ， $b_i$ ，为题目所述。

输出一行一个正整数，为所求城市与首都的距离。

数据范围与来源

$n\le50$ ， $m,w,a_i,b_i\le10^{3}$ 。所有数均为正整数。

来自 zzy。

C

C 国经常下雪。在 C 国，你拥有一片 $n\times n$ 的土地（可看作网格），其中有三个住所，每个住所占有一个 $1\times1$ 的方格。住所之间有地下通道相连。每个住所有四个门，分别为东门，西门，北门。南门。

现在你的土地上堆满了雪（住所所在方格没有雪），第 $i$ 行第 $j$ 列（记作 $(i,j)$ ）雪的深度为 $a_{i,j}$ 。现在，你希望将你的土地上的雪清理干净。

你的身高为 $d$ 。你可以从任意一个住所出发开始清理土地。如果你站在一个空地（满足 $a_{i,j}=0$ 即为空地，包括住所）上，那么你接下来可以向四个方向任意移动一格；如果你站在有雪的方格上（ $a_{i,j}>0$ ），那么你必须将此处的雪铲到四个方向的相邻的任意一格，才能进行下一步的移动操作。具体地，如果你将 $(a,b)$ 处的雪铲到 $(p,q)$ 格上，那么将 $a_{p,q}$ 加上 $a_{a,b}$ ，然后将 $a_{a,b}$ 置为 $0$ 。