组合数表示的是从 个物品中选出 个物品的方案数。举个例子，从 三个物品中选择两个物品可以有 ，， 这三种选择方法。

根据组合数的定义，我们可以给出计算组合数的一般公式：

其中 。

小葱想知道如果给定 ， 和 ，对于所有的 ， 有多少对 满足是 的倍数。

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 节课程安排在 个时间段上。在第 （）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 上课，而另一节课程在教室 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 节安排好的课程。如果学生想更换第i节课程的教室，则需要提出申请。若申请通过，学生就可以在第 个时间段去教室 上课，否则仍然在教室 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 节课程的教室时，申请被通过的概率是一个已知的实数 ，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请白己最希望更换教室的 门课程，也可以不用完这 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课问时间从一间教室赶到另一间教室。

牛牛所在的大学有 个教室，有 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 （）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 个结点和 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 到 的连续正整数。

现在有 个玩家，第 个玩家的起点为 ，终点为 。每天打卡任务开始时，所有玩家在第 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 的观察员会选择在第 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 秒也理到达了结点 。小 C 想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 作为终点的玩家：若他在第 秒前到达终点，则在结点 的观察员不能观察到该玩家；若他正好在第 秒到达终点，则在结点 的观察员可以观察到这个玩家。

小南有一套可爱的玩具小人，它们各有不同的职业。

有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。

这时 singer 告诉小南一个谜题：「眼镜藏在我左数第 个玩具小人的右数第 个玩具小人的左数第 个玩具小人那里。」

小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。

小南一边艰难地辨认着玩具小人，一边数着：

singer 朝内，左数第 个是 archer。 archer 朝外，右数第 个是 thinker。 thinker 朝外，左数第 个是 writer。

所以眼镜藏在 writer 这里！

虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：

有 个玩具小人围成一圈，已知它们的职业和朝向。现在第 个玩具小人告诉小南一个包含 条指令的谜题。其中第 条指令形如「左数/右数第 个玩具小人」。你需要输出依次数完这些指令后，到达的玩具小人的职业。

第二次 NOIP。 倒数第二次 NOIP。

H 国有 个城市，这 个城市用 条双向道路相互连通构成一棵树， 号城市是首都，也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意，不同的军队可以同时移动。

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 行 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。

由于第 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 到 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 的海拔高度为 ，城市 和城市 之间的距离 恰好是这两个城市海拔高度之差的绝对值，即 。

旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 作为起点，一直向东行驶，并且最多行驶 公里就结束旅行。小 A 和小 B 的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 公里，他们就会结束旅行。

在启程之前，小 A 想知道两个问题：

1. 对于一个给定的 ，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 ，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2. 对任意给定的 和出发城市 ，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

1. 在一个 棋盘上有 个格子，其中有且只有一个格子是空白的，其余 个格子上每个格子上有一个棋子，每个棋子的大小都是 的；
2. 有些棋子是固定的，有些棋子则是可以移动的；
3. 任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘，游戏可以玩 次，当然，每次棋盘上固定的格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 次玩的时候，空白的格子在第 行第 列，指定的可移动棋子的初始位置为第 行第 列，目标位置为第 行第 列。

假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。

有 个小朋友坐成一圈，每人有 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 。求使所有人获得均等糖果的最小代价。