第十一届蓝桥杯大赛软件类决赛 Java 研究生组

- 日理万妓 2024-05-28 10:23 89阅读 0赞

#### 文章目录 ####

*  发现宝藏
 *  【考生须知】
 *  试题 A: 合数个数
 *  试题 B: 含 2 天数
 *  试题 C 阶乘约数
 *  试题 D: 本质上升序列
 *  试题 E: 迨尺天涯
 *  试题 F 循环小数
 *  试题 G: 蓝肽子序列
 *  试题 H 出租车
 *  试题 I: 答疑
 *  试题 J: 蓝跳跳

## 发现宝藏 ##

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【[宝藏入口][Link 1]】。

--------------------

第十一届蓝桥杯大赛软件类决赛  研究生 组

## 【考生须知】 ##

考试开始后, 选手首先下载题目, 并使用考场现场公布的解压密码解压试

考试时间为 4 小时。考试期间选手可汶览自己已经提交的答案, 被浏览的答案允许拷贝。时间截止后, 将无法继续提交或浏览答案。

对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。

试题包含 “结果填空” 和 “程序设计” 两种题型。

结果填空题: 要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可, 不要书写多余的内容。

程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。

注意: 在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的, 不能只对试卷中给定的数据有效。

所有源码必须在同一文件中。调试通过后，拷贝提交。

注意: 不要使用 package 语句。

注意: 选手代码的主类名必须为: Main, 否则会被判为无效代码。

注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。

--------------------

## 试题 A: 合数个数 ##

本题总分: 5 分

**【问题描述】**

一个数如果除了 1 和自己还有其他约数, 则称为一个合数。例如:  1 , 2 , 3 1,2,3 1,2,3不是合数, 4,6 是合数。

请问从 1 到 2020 一共有多少个合数。

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

--------------------

## 试题 B: 含 2 天数 ##

本题总分: 5 分

**【问题描述】**

小蓝特别喜欢 2 , 今年是公元 2020 年, 他特别高兴, 因为每天日历上都可以看到 2 。

如果日历中只显示年月日, 请问从公元 1900 年 1 月 1 日到公元 9999 年 12 月 31 日, 一共有多少天日历上包含 2 。即有多少天中年月日的数位中包含数字

2 。

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

--------------------

## 试题 C 阶乘约数 ##

本题总分: 10 分

**【问题描述】**

定义阶乘  n ! = 1 × 2 × 3 × ⋯ × n n!=1 \\times 2 \\times 3 \\times \\cdots \\times n n!=1×2×3×⋯×n 。

请问  100 ! （ 100 100!（ 100 100!（100 的阶乘）有多少个正约数。

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

--------------------

## 试题 D: 本质上升序列 ##

本题总分: 10 分

**【问题描述】**

小蓝特别喜欢单调递增的事物。

在一个字符串中, 如果取出若干个字符, 将这些字符按照在字符串中的顺序排列后是单调递增的, 则成为这个字符串中的一个单调递增子序列。

例如, 在字符串 lanqiao 中, 如果取出字符  n n n 和  q q q, 则  n q n q nq 组成一个单调递增子序列。类似的单调递增子序列还有  1 n q 1 \\mathrm\{nq\} 1nq 、 i、ano 等等。

小蓝发现, 有些子序列虽然位置不同, 但是字符序列是一样的, 例如取第二个字符和最后一个字符可以取到 ao, 取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串, 小蓝想知道, 本质不同的递增子序列有多少个?

例如, 对于字符串 lanqiao, 本质不同的递增子序列有 21 个。它们分别是  1 、 a 、 n 、 q 、 i 、 o 、 1 n 、 a n 、 1 q 、 a q 、 n q 、 a i 、 1 o 、 a o 、 n o 、 i o v 1 n q 、 1 、 a 、 n 、 q 、 i 、 o 、 1 n 、 a n 、 1 q 、 a q 、 n q 、 a i 、 1 o 、 a o 、 n o 、 i o v 1 n q 、 1、a、n、q、i、o、1n、an、1q、aq、nq、ai、1o、ao、no、iov1nq、 anq, Ino, ano, aio.

请问对于以下字符串 (共 200 个小写英文字母, 分四行显示)： (如果你把以下文字复制到文本文件中, 请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt, 内容与下面的文本相同)

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij gihhfgdemxvicfauachlifhafpdccfseflcdgjncadfclvfmad vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个?

**【答案提交】**

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

## 试题 E: 迨尺天涯 ##

本题总分: 15 分

**【问题描述】**

皮亚诺曲线是一条平面内的曲线。

下图给出了皮亚诺曲线的 1 阶情形, 它是从左下角出发, 经过一个  3 × 3 3 \\times 3 3×3 的方格中的每一个格子, 最终到达右上角的一条曲线。

![在这里插入图片描述][814d603ef4694428a3ee05a412bd080f.png]

设每个格子的边长为 1 , 在上图中, 有的相邻的方格 (四相邻) 在皮亚诺曲线中也是相邻的, 在皮亚诺曲线上的距离是 1, 有的相邻的方格在皮亚诺曲线中不相邻, 距离大于 1 。

例如, 正中间方格的上下两格都与它在皮亚诺曲线上相邻, 距离为 1 , 左右两格都与它在皮亚诺曲线上不相邻, 距离为 3 。

下图给出了皮亚诺曲线的 2 阶情形, 它是经过一个  3 2 × 3 2 3^2 \\times 3^2 32×32 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

![在这里插入图片描述][c52d498108194860b10233be18005cc9.png]

设每个格子的边长为 1 , 在上图中, 有的相邻的方格（四相邻）在皮亚诺曲线中也是相邻的, 在皮亚诺曲线上的距离是 1, 有的相邻的方格在皮亚诺曲线中不相邻, 距离大于 1 。

例如, 正中间方格的上下两格都与它在皮亚诺曲线上相邻, 距离为 1 , 左右两格都与它在皮亚诺曲线上不相邻, 距离为 3 。

下图给出了皮亚诺曲线的 2 阶情形, 它是经过一个  3 2 × 3 2 3^\{2\} \\times 3^\{2\} 32×32 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

下图给出了皮亚诺曲线的 3 阶情形, 它是经过一个  3 3 × 3 3 3^\{3\} \\times 3^\{3\} 33×33 的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

![在这里插入图片描述][0c14c702e600456c8d464ca005541de2.png]

皮亚诺曲线总是从左下角开始出发, 最终到达右上角。

小蓝对于相邻的方格在皮亚诺曲线上的相邻关系很好奇, 他想知道相邻的方格在曲线上的距离之和是多少。

例如, 对于 1 阶皮亚诺曲线, 距离和是 24 , 有 8 对相邻的方格距离为 1 , 2 对相邻的方格距离为 3,2 对相邻的方格距离为 5 。

再如, 对于 2 阶皮亚诺曲线, 距离和是 816 。

请求出对于 12 阶皮亚诺曲线, 距离和是多少。

提示: 答案不超过  1 0 18 10^\{18\} 1018 。

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

--------------------

## 试题 F 循环小数 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制: 512.0MB 本题总分: 15 分

**【问题描述】**

已知  S S S 是一个小于 1 的循环小数, 请计算与  S S S 相等的最简真分数是多少。

例如  0.3333 ⋯ 0.3333 \\cdots 0.3333⋯ 等于  1 3 , 0.1666 ⋯ \\frac\{1\}\{3\}, 0.1666 \\cdots 31,0.1666⋯ 等于  1 6 \\frac\{1\}\{6\} 61 。

**【输入格式】**

输入第一行包含两个整数  p p p 和  q q q, 表示  S S S 的循环节是小数点后第  p p p 位到第  q q q 位。

第二行包含一个  q q q 位数, 代表  S S S 的小数部分前  q q q 位。

**【输出格式】**

输出两个整数, 用一个空格分隔, 分别表示答案的分子和分母。

**【样例输入】**

1 6 \\begin\{array\}\{llll\}1 & 6\\end\{array\} 16

142857 \\begin\{array\}\{llll\}142857 \\end\{array\} 142857

**【样例输出】**

1 7 \\begin\{array\}\{llll\}1 &7\\end\{array\} 17

**【评测用例规模与约定】**

对于所有评测用例,  1 ≤ p ≤ q ≤ 10 1 \\leq p \\leq q \\leq 10 1≤p≤q≤10 。

--------------------

## 试题 G: 蓝肽子序列 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 20 分

**【问题描述】**

L \\mathrm\{L\} L 星球上的生物由蛋蓝质组成, 每一种㞼蓝质由一类称为蓝肽的物资首尼连接成一条长链后折叠而成。

生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列,想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。

具体的, 一个蓝肽可以使用 1 至 5 个英文字母母表示, 其中第一个字母大写,后面的字母小写。一个蛋蓝质的蓝肚序列可以用蓝肚的表示顺序拼接而成。

在一条蓝肽序列中, 如果选取其中的一些位置, 把这些位置的蓝朋取出,并按照它们在原序列中的位置摆放, 则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的, 中间可能间隔着一些未被取出的蓝肽。

如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等, 则称为一个公共蓝肚子序列。

给定两条蓝肽序列, 找出他们最长的那个公共蓝肚子序列的长度。

**【输入格式】**

输入两行, 每行包含一个字符串, 表示一个蓝肚序列。字符串中间没有空格等分隔字符。

**【输出格式】**

输出一个整数, 表示最长的那个公共蓝肚子序列的长度。

**【样例输入】**

L a n Q i a o B e i \\begin\{array\}\{llll\}LanQiaoBei\\end\{array\} LanQiaoBei

L a n T a i X i a o Q i a o \\begin\{array\}\{llll\}LanTaiXiaoQiao\\end\{array\} LanTaiXiaoQiao

**【样例输出】**

2 \\begin\{array\}\{llll\}2\\end\{array\} 2

**【样例说明】**

最长的公共蓝肽子序列为 LanQiao, 共两个蓝肚。

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的评测用例, 两个字符串的长度均不超过 20 。

对于  50 % 50 \\% 50% 的评测用例, 两个字符串的长度均不超过 100 。

对于所有评测用例, 两个字符串的长度均不超过 1000。

--------------------

## 试题 H 出租车 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 20 分

**【问题描述】**

小蓝在  L L L 市开出租车。

L L L 市的规划很规整, 所有的路都是正东西向或者正南北向的, 道路都可以看成直线段。东西向的道路互相平行, 南北向的道路互相平行, 任何一条东西向道路垂直于任何一条南北向道路。

从北到南一共有  n n n 条东西向道路, 依次标号为  H 1 , H 2 , ⋯   , H n H\_\{1\}, H\_\{2\}, \\cdots, H\_\{n\} H1,H2,⋯,Hn. 从西到东一共有  m m m 条南北向的道路, 依次标号为  S 1 , S 2 , ⋯   , S m S\_\{1\}, S\_\{2\}, \\cdots, S\_\{m\} S1,S2,⋯,Sm 。

每条道路都有足够长, 每一条东西向道路和每一条南北向道路都相交,  H i H\_\{i\} Hi与  S j S\_\{j\} Sj 的交叉路口记为  ( i , j ) (i, j) (i,j) 。

从  H 1 H\_\{1\} H1 和  S 1 S\_\{1\} S1 的交叉路口  ( 1 , 1 ) (1,1) (1,1) 开始, 向南遇到的路口与  ( 1 , 1 ) (1,1) (1,1) 的距离分别是  h 1 , h 2 , ⋯   , h n − 1 \\boldsymbol\{h\}\_\{1\}, \\boldsymbol\{h\}\_\{2\}, \\cdots, \\boldsymbol\{h\}\_\{n-1\} h1,h2,⋯,hn−1, 向东遇到路口与  ( 1 , 1 ) (1,1) (1,1) 的距离分别是  w 1 , w 2 , ⋯   , w m − 1 w\_\{1\}, w\_\{2\}, \\cdots, w\_\{m-1\} w1,w2,⋯,wm−1 。

道路的每个路口都有一个红绿灯。

时刻 0 的时候, 南北向绿奵亮, 东西向红灯亮, 南北向的绿奵会持续一段时间 (每个路口不同), 然后南北向变成红灯, 东西向变成绿灯, 持续一段时间后, 再变成南北向绿灯, 东西向红奵。

已知路口  ( i , j ) (i, j) (i,j) 的南北向绿奵每次持续的时间为  g i j g\_\{i j\} gij, 东西向的绿奵每次持续的时间为  r i j r\_\{i j\} rij, 红绿灯的变换时间忽略。

当一辆车走到路口时, 如果是绿灯, 可以直行、左转或右转。如果是红奵,可以右转, 不能直行或左转。如果到路口的时候刚好由红灯变为绿奵, 则视为看到绿灯, 如果刚好由绿奵变为红奵, 则视为看到红奵。

每段道路都是双向道路, 道路中间有隔离栏杆, 在道路中间不能掉头, 只能在红绿奵路口掉头。掉头时不管是红奵还是绿奵都可以直接掉头。掉头的时间可以忽略。

小蓝时刻 0 从家出发。今天, 他接到了  q q q 个频约的订单, 他打算按照订单的顺序依次完成这些订单, 就回家休息。中途小蓝不准备再拉其他乘客。

小蓝的家在两个路口的中点, 小蓝喜欢用  x 1 , y 1 , x 2 , y 2 x\_\{1\}, y\_\{1\}, x\_\{2\}, y\_\{2\} x1,y1,x2,y2 来表示自己家的位置, 即路口  ( x 1 , y 1 ) \\left(x\_\{1\}, y\_\{1\}\\right) (x1,y1) 到路口  ( x 2 , y 2 ) \\left(x\_\{2\}, y\_\{2\}\\right) (x2,y2) 之间的道路中点的右侧, 保证两个路口相邻 (中间没有其他路口)。请注意当两个路口交换位置时, 表达的是路的不同两边,路中间有栏杆, 因此这两个位置实际要走比较远才能到达。

小蓝的订单也是从某两个路口间的中点出发, 到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单, 而且一个时刻只能处理一个订单, 不能图省时间而同时接两位乘客, 也不能插队完成后面的订单。

小蓝只对  L L L 市比较熟, 因此他只会在给定的  n n n 条东西向道路和  m m m 条南北向道路上行驶, 而且不会驶出  H 1 , H n , S 1 , S m H\_\{1\}, H\_\{n\}, S\_\{1\}, S\_\{m\} H1,Hn,S1,Sm 这几条道路所确定的矩形区域（可以到边界)。

小蓝行车速度一直为 1 , 乘客上下车的时间忽略不计。

请问, 小蓝最早什么时候能完成所有订单回到家。

**【输入格式】**

输入第一行包含两个整数  n , m n, m n,m, 表示东西向道路的数量和南北向道路的数量。

第二行包含  n − 1 n-1 n−1 个整数  h 1 , h 2 , ⋯   , h n − 1 h\_\{1\}, h\_\{2\}, \\cdots, h\_\{n-1\} h1,h2,⋯,hn−1 。

第三行包含  m − 1 m-1 m−1 个整数  w 1 , w 2 , ⋯   , w m − 1 w\_\{1\}, w\_\{2\}, \\cdots, w\_\{m-1\} w1,w2,⋯,wm−1 。

接下来  n n n 行, 每行  m m m 个整数, 描述每个路口南北向绿灯的时间, 其中的第  i i i 行第  j j j 列表示  g i j g\_\{i j\} gij 。

接下来  n n n 行, 每行  m m m 个整数, 描述每个路口东西向绿灯的时间, 其中的第  i i i 行第  j j j 列表示  r i j r\_\{i j\} rij 。

接下来一行包含四个整数  x 1 , y 1 , x 2 , y 2 x\_\{1\}, y\_\{1\}, x\_\{2\}, y\_\{2\} x1,y1,x2,y2, 表示小蓝家的位置在路口  ( x 1 , y 1 ) \\left(x\_\{1\}, y\_\{1\}\\right) (x1,y1)到路口  ( x 2 , y 2 ) \\left(x\_\{2\}, y\_\{2\}\\right) (x2,y2) 之间的道路中点的右侧。

接下来一行包含一个整数  q q q, 表示订单数量。

接下来  q q q 行, 每行描述一个订单, 其中第  i i i 行包含八个整数  x i 1 , y i 1 , x i 2 , y i 2 x\_\{i 1\}, y\_\{i 1\}, x\_\{i 2\}, y\_\{i 2\} xi1,yi1,xi2,yi2,  x i 3 , y i 3 , x i 4 , y i 1 x\_\{i 3\}, y\_\{i 3\}, x\_\{i 4\}, y\_\{i 1\} xi3,yi3,xi4,yi1, 表示第  i i i 个汀单的起点为路口  ( x i 1 , y i 1 ) \\left(x\_\{i 1\}, y\_\{i 1\}\\right) (xi1,yi1) 到路口  ( x i 2 , y i 2 ) \\left(x\_\{i 2\}, y\_\{i 2\}\\right) (xi2,yi2) 之间的道路中点的右侧, 第  i i i 个订单的终点为路口  ( x i 3 , y i 3 ) \\left(x\_\{i 3\}, y\_\{i 3\}\\right) (xi3,yi3) 到路口  ( x i 4 , y i 4 ) \\left(x\_\{i 4\}, y\_\{i 4\}\\right) (xi4,yi4) 之间的道路中点的右侧。

**【输出格式】**

输出一个实数, 表示小蓝完成所有订单最后回到家的最早时刻。四舍五入保留一位小数。

**【样例输入】**

2 3 \\begin\{array\}\{llll\}2&3\\end\{array\} 23

200 \\begin\{array\}\{llll\}200\\end\{array\} 200

100 400 \\begin\{array\}\{llll\}100 &400 \\end\{array\} 100400

10 20 10 \\begin\{array\}\{llll\}10 & 20 & 10\\end\{array\} 102010

20 40 30 \\begin\{array\}\{llll\}20 & 40 & 30\\end\{array\} 204030

20 20 20 \\begin\{array\}\{llll\}20 & 20 & 20\\end\{array\} 202020

2 1 1 1 \\begin\{array\}\{llll\}2 & 1 & 1&1\\end\{array\} 2111

1 \\begin\{array\}\{llll\}1\\end\{array\} 1

2 2 1 2 1 2 1 3 \\begin\{array\}\{llll\}2& 2 & 1& 2 & 1& 2 & 1&3\\end\{array\} 22121213

**【样例输出】**

1620.0 \\begin\{array\}\{llll\}1620.0\\end\{array\} 1620.0

**【样例说明】**

小蓝有一个订单, 他的行车路线如下图所示。其中  H \\mathrm\{H\} H 表示他家的位置,  S \\mathrm\{S\} S表示订单的起点,  T \\mathrm\{T\} T 表示订单的终点。小明在最后回家时要在直行的红绿灯路口等绿奵, 等待时间为 20 。

![在这里插入图片描述][caa61fdb404c4bb8beed7b411ea08da8.png]

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的评测用例,  1 ≤ n , m ≤ 5 , 1 ≤ q ≤ 10 1 \\leq n, m \\leq 5,1 \\leq q \\leq 10 1≤n,m≤5,1≤q≤10 。

对于  50 % 50 \\% 50% 的评测用例,  1 ≤ n , m ≤ 30 , 1 ≤ q ≤ 30 1 \\leq n, m \\leq 30,1 \\leq q \\leq 30 1≤n,m≤30,1≤q≤30 。

对于所有评测用例,  1 ≤ n , m ≤ 100 , 1 ≤ q ≤ 30 , 1 ≤ h 1 < h 2 < ⋯ < h n − 1 ≤ 1 \\leq n, m \\leq 100,1 \\leq q \\leq 30,1 \\leq h\_\{1\}<h\_\{2\}<\\cdots<h\_\{n-1\} \\leq 1≤n,m≤100,1≤q≤30,1≤h1<h2<⋯<hn−1≤  100000 , 1 ≤ w 1 < w 2 < ⋯ < w m − 1 ≤ 100000 , 1 ≤ g i j ≤ 1000 , 1 ≤ r i j ≤ 1000 100000,1 \\leq w\_\{1\}<w\_\{2\}<\\cdots<w\_\{m-1\} \\leq 100000,1 \\leq g\_\{i j\} \\leq 1000,1 \\leq r\_\{i j\} \\leq 1000 100000,1≤w1<w2<⋯<wm−1≤100000,1≤gij≤1000,1≤rij≤1000, 给定的路口一定合法。

--------------------

## 试题 I: 答疑 ##

时间限制:  3.0 s 3.0 \\mathrm\{~s\} 3.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 25 分

**【问题描述】**

有  n n n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师可以安排答疑的顺序, 同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下:

1.  首先进入办公室, 编号为  i i i 的同学需要  s i s\_\{i\} si 毫秒的时间。
2.  然后同学问问题老师解答, 编号为  i i i 的同学需要  a i a\_\{i\} ai 毫秒的时间.
3.  答疑完成后, 同学很高兴, 会在课程群里面发一条消息, 需要的时间可以忽略。
4.  最后同学收拾东西离开办公室, 需要  e i e\_\{i\} ei 毫秒的时间。一般需要 10 秒、 20 秒或 30 秒, 即  e i e\_\{i\} ei 取值为 10000,20000 或 30000 。

一位同学离开办公室后, 紧接着下一位同学就可以进入办公室了。

答疑从 0 时刻开始。老师想合理的安排答疑的顺序, 使得同学们在课程群里面发消息的时刻之和最小。

**【输入格式】**

输入第一行包含一个整数  n n n, 表示同学的数量。

接下来  n n n 行, 描述每位同学的时间。其中第  i i i 行包含三个整数  s i , a i , e i s\_\{i\}, a\_\{i\}, e\_\{i\} si,ai,ei, 意义如上所述。

**【输出格式】**

输出一个整数, 表示同学们在课程群里面发消息的时刻之和最小是多少。

**【样例输入】**

3 \\begin\{array\}\{llll\}3\\end\{array\} 3

10000 10000 10000 \\begin\{array\}\{llll\}10000&10000&10000\\end\{array\} 100001000010000

20000 50000 20000 \\begin\{array\}\{llll\}20000&50000&20000\\end\{array\} 200005000020000

30000 20000 30000 \\begin\{array\}\{llll\}30000&20000&30000\\end\{array\} 300002000030000

**【样例输出】**

280000 \\begin\{array\}\{llll\}280000\\end\{array\} 280000

**【样例说明】**

按照  1 , 3 , 2 1,3,2 1,3,2 的顺序答疑, 发消息的时间分别是 20000 , 80000 , 180000 20000,80000,180000 20000,80000,180000 。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例，  1 ≤ n ≤ 20 1 \\leq n \\leq 20 1≤n≤20 。

对于  60 % 60 \\% 60% 的评测用例,  1 ≤ n ≤ 200 1 \\leq n \\leq 200 1≤n≤200 。

对于所有评测用例,  1 ≤ n ≤ 1000 , 1 ≤ s i ≤ 60000 , 1 ≤ a i ≤ 1000000 1 \\leq n \\leq 1000,1 \\leq s\_\{i\} \\leq 60000,1 \\leq a\_\{i\} \\leq 1000000 1≤n≤1000,1≤si≤60000,1≤ai≤1000000,  e i ∈ \{ 10000 , 20000 , 30000 \} e\_\{i\} \\in\\\{10000,20000,30000\\\} ei∈\{ 10000,20000,30000\}, 即  e i e\_\{i\} ei 一定是 10000、20000、30000 之一。

--------------------

## 试题 J: 蓝跳跳 ##

时间限制:  10.0 s 10.0 \\mathrm\{~s\} 10.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 25 分

**【问题措述】**

小蓝制作了一个机器人, 取名为蓝跳跳, 因为这个机器人走路的时候基本靠跳跃。

蓝跳跳可以跳着走, 也可以掉头。蓝跳跳每步跳的距离都必须是整数, 每步可以跳不超过  k k k 的长度。由于蓝跳跳的平衡性设计得不太好, 如果连续两次都是跳跃, 而且两次跳跃的距离都至少是  p p p, 则蓝跳跳会掠倒, 这是小蓝不愿意看到的。

小蓝接到一个特别的任务, 要在一个长为  L L L 舞台上展示蓝跳跳。小蓝要控制蓝跳跳从舞台的左边走到右边, 然后掉头, 然后从右边走到左边, 然后掉头,然后再从左边走到右边, 然后掉头, 再从右边走到左边, 然后掉头, 如此往复。

为了让观者不至于太无趣, 小蓝决定让蓝跳跳每次用不同的方式来走。小蓝将蓝跳跳每一步跳的距离记录下来, 按顺序排成一列, 显然这一列数每个都

不超过  k k k 且和是  L 。 L\_\{\\text \{。 \}\} L。 这样走一趟就会出来一列数。如果两列数的长度不同, 或者两列数中存在一个位置数值不同, 就认为是不同的方案。

请问蓝跳跳在不接倒的前提下, 有多少种不同的方案从舞台一边走到另一边。

**【输入格式】**

输入一行包含三个整数  k , p , L k, p, L k,p,L 。

**【输出格式】**

输出一个整数, 表示答案。答案可能很大, 请输出答案除以 20201114 的余数。

**【样例输入】**

3 2 5 \\begin\{array\}\{llll\}3&2&5\\end\{array\} 325

**【样例输出】**

9 \\begin\{array\}\{llll\}9\\end\{array\} 9

**【样例说明】**

蓝跳跳有以下 9 种跳法:

1.   1 + 1 + 1 + 1 + 1 1+1+1+1+1 1\+1\+1\+1\+1
2.   1 + 1 + 1 + 2 1+1+1+2 1\+1\+1\+2
3.   1 + 1 + 2 + 1 1+1+2+1 1\+1\+2\+1
4.   1 + 2 + 1 + 1 1+2+1+1 1\+2\+1\+1
5.   2 + 1 + 1 + 1 2+1+1+1 2\+1\+1\+1
6.   2 + 1 + 2 2+1+2 2\+1\+2
7.   1 + 1 + 3 1+1+3 1\+1\+3
8.   1 + 3 + 1 1+3+1 1\+3\+1
9.   3 + 1 + 1 3+1+1 3\+1\+1

**【样例输入】**

5 3 10 \\begin\{array\}\{llll\}5 & 3 & 10\\end\{array\} 5310

**【样例输出】**

397 \\begin\{array\}\{llll\}397\\end\{array\} 397

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例,  1 ≤ p ≤ k ≤ 50 , 1 ≤ L ≤ 1000 1 \\leq p \\leq k \\leq 50,1 \\leq L \\leq 1000 1≤p≤k≤50,1≤L≤1000 。

对于  60 % 60 \\% 60% 的评测用例,  1 ≤ p ≤ k ≤ 50 , 1 ≤ L ≤ 1 0 9 1 \\leq p \\leq k \\leq 50,1 \\leq L \\leq 10^\{9\} 1≤p≤k≤50,1≤L≤109 。

对于  80 % 80 \\% 80% 的评测用例,  1 ≤ p ≤ k ≤ 200 , 1 ≤ L ≤ 1 0 18 1 \\leq p \\leq k \\leq 200,1 \\leq L \\leq 10^\{18\} 1≤p≤k≤200,1≤L≤1018 。

对于所有评测用例,  1 ≤ p ≤ k ≤ 1000 , 1 ≤ L ≤ 1 0 18 1 \\leq p \\leq k \\leq 1000,1 \\leq L \\leq 10^\{18\} 1≤p≤k≤1000,1≤L≤1018 。

[Link 1]: https://www.captainbed.cn/dl
[814d603ef4694428a3ee05a412bd080f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/f97a3940314b4aa48e0d9300841f33c0.png
[c52d498108194860b10233be18005cc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/895f3668a81441a4bbcde01de8571c06.png
[0c14c702e600456c8d464ca005541de2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/ba62be5c74194bf7ab88bc32556aa6f0.png
[caa61fdb404c4bb8beed7b411ea08da8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/50395a7c2e3146e39a20db9899938ffe.png