第十一届蓝桥杯大赛软件类决赛 Java B 组

川长思鸟来 2024-05-28 10:23 78阅读 0赞

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

*  发现宝藏
 *  【考生须知】
 *  试题 A: 美丽的 2
 *  试题 B: 扩散
 *  试题 C: 阶乘约数
 *  试题 D: 本质上升序列
 *  试题 E 玩具蛇
 *  试题 F 蓝肽子序列
 *  试题 G 皮亚诺曲线距离
 *  试题 H: 画廊
 *  试题 I: 补给
 *  试题 J 质数行者

## 发现宝藏 ##

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

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

第十一届蓝桥杯大赛软件类决赛  Java B 组

## 【考生须知】 ##

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

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

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

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

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

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

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

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

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

注意: 不要使用 package 语句。

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

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

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

## 试题 A: 美丽的 2 ##

本题总分: 5 分

**【问题描述】**

小蓝特别喜欢 2 , 今年是公元 2020 年, 他特别高兴。

他很好奇, 在公元 1 年到公元 2020 年 (包含) 中, 有多少个年份的数位中包含数字 2 ?

**【答案提交】**

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

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

## 试题 B: 扩散 ##

本题总分: 5 分

**【问题描述】**

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图, 每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点:  ( 0 , 0 ) , ( 2020 , 11 ) , ( 11 , 14 ) , ( 2000 , 2000 ) (0,0),(2020,11),(11,14),(2000,2000) (0,0),(2020,11),(11,14),(2000,2000) 。只有这几个格子上有黑色, 其它位置都是白色的。

每过一分钟, 黑色就会扩散一点。具体的, 如果一个格子里面是黑色, 它就会扩散到上、下、左、右四个相邻的格子中, 使得这四个格子也变成黑色 (如果原来就是黑色, 则还是黑色)。

请问, 经过 2020 分钟后，画布上有多少个格子是黑色的。

**【答案提交】**

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

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

## 试题 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 分

**【问题描述】**

小蓝有一条玩具蛇, 一共有 16 节, 上面标着数字 1 至 16 。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。

小蓝还有一个  4 × 4 4 \\times 4 4×4 的方格盒子, 用于存放玩具蛇, 盒子的方格上依次标着字母 A 到 P 共 16 个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现, 有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:

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

请帮小蓝计算一下, 总共有多少种不同的方案。如果两个方案中, 存在玩具蛇的某一节放在了盒子的不同格子里, 则认为是不同的方案。

**【答案提交】**

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

## 试题 F 蓝肽子序列 ##

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

**【问题描述】**

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。

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

## 试题 G 皮亚诺曲线距离 ##

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

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

**【问题描述】**

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

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

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

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

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

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

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

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

我们将这些格子放到坐标系中, 对于  k k k 阶皮亚诺曲线, 左下角的坐标是  ( 0 , 0 ) (0,0) (0,0), 右上角坐标是  ( 3 k − 1 , 3 k − 1 ) \\left(3^k-1,3^k-1\\right) (3k−1,3k−1), 右下角坐标是  ( 3 k − 1 , 0 ) \\left(3^k-1,0\\right) (3k−1,0), 左上角坐标是  ( 0 , 3 k − 1 ) \\left(0,3^k-1\\right) (0,3k−1) 。

给定  k k k 阶皮亚诺曲线上的两个点的坐标, 请问这两个点之间, 如果沿着皮亚诺曲线走, 距离是到少?

**【输入格式】**

输入的第一行包含一个正整数  k k k, 皮亚诺曲线的阶数。  
第二行包含两个整数  x 1 , y 1 x\_1, y\_1 x1,y1, 表示第一个点的坐标。  
第三行包含两个整数  x 2 , y 2 x\_2, y\_2 x2,y2, 表示第二个点的坐标。

**【输出格式】**

输出一个整数, 表示给定的两个点之间的距离。

**【样例输入】**

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

0 0 \\begin\{array\}\{llll\}0&0\\end\{array\} 00

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

**【样例输出】**

8 \\begin\{array\}\{llll\}8\\end\{array\} 8

**【样例输入】**

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

0 2 \\begin\{array\}\{llll\}0&2\\end\{array\} 02

0 3 \\begin\{array\}\{llll\}0&3\\end\{array\} 03

**【样例输出】**

13 \\begin\{array\}\{llll\}13\\end\{array\} 13

【评测用例规模与约定】  
对于  30 % 30 \\% 30% 的评测用例，  0 ≤ k ≤ 10 0 \\leq k \\leq 10 0≤k≤10 。  
对于  50 % 50 \\% 50% 的评测用例，  0 ≤ k ≤ 20 0 \\leq k \\leq 20 0≤k≤20 。  
对于所有评测用例,  0 ≤ k ≤ 100 , 0 ≤ x 1 , y 1 , x 2 , y 2 < 3 k , x 1 , y 1 , x 2 , y 2 ≤ 1 0 18 0 \\leq k \\leq 100,0 \\leq x\_1, y\_1, x\_2, y\_2<3^k, x\_1, y\_1, x\_2, y\_2 \\leq 10^\{18\} 0≤k≤100,0≤x1,y1,x2,y2<3k,x1,y1,x2,y2≤1018 。数据保证答案不超过  1 0 18 10^\{18\} 1018 。

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

## 试题 H: 画廊 ##

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

**【问题描述】**

小蓝办了一个画展, 在一个画廊左右两边陈列了他自己的作品。为了使画展更有意思, 小蓝没有等距陈列自己的作品, 而是按照更有艺术感的方式陈列。在画廊的左边陈列了  L L L 幅作品, 在画廊的右边陈列了  R R R 幅作品, 左边的作品距离画廊的起点依次为  u 1 , u 2 , ⋯   , u L u\_\{1\}, u\_\{2\}, \\cdots, u\_\{L\} u1,u2,⋯,uL, 右边的作品距离画廊起点依次为  v 1 , v 2 , ⋯ v\_\{1\}, v\_\{2\}, \\cdots v1,v2,⋯,  v R ∘ v\_\{R\} \\circ vR∘

每周, 小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的,但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。

小蓝从画廊的起点的正中央（左右两边的中点）出发, 整理好每一幅画,最终到达画廊的终点的正中央。已知画廊的宽为  w 。 w\_\{\\text \{。 \}\} w。

请问小蓝最少带着工具走多长的距离?

**【输入格式】**

输入的第一行包含四个整数  L , R , d , w L, R, d, w L,R,d,w, 表示画廊左边和右边的作品数量,以及画廊的长度和宽度。

第二行包含  L L L 个正整数  u 1 , u 2 , ⋯   , u L u\_\{1\}, u\_\{2\}, \\cdots, u\_\{L\} u1,u2,⋯,uL, 表示画廊左边的作品的位置。

第三行包含  R R R 个正整数  v 1 , v 2 , ⋯   , v R v\_\{1\}, v\_\{2\}, \\cdots, v\_\{R\} v1,v2,⋯,vR, 表示画廊右边的作品的位置。

**【输出格式】**

输出一个实数, 四舍五入保留两位小数, 表示小蓝最少带着工具走的距离。

**【样例输入】**

3 3 10 2 \\begin\{array\}\{llll\}3&3&10&2\\end\{array\} 33102

1 3 8 \\begin\{array\}\{llll\}1&3&8\\end\{array\} 138

2 4 6 \\begin\{array\}\{llll\}2&4&6\\end\{array\} 246

**【样例输出】**

14.71 \\begin\{array\}\{llll\}14.71\\end\{array\} 14.71

**【样例说明】**

小蓝从起点开始, 首先到达左边第一幅作品 (走动距离  2 \\sqrt\{2\} 2 ), 然后到达左边第二幅作品 (走动距离 2), 然后到达右边第一幅作品 (走动距离  5 \\sqrt\{5\} 5 ), 然后到达右边第二幅和第三幅作品 (走动距离 2 和 2), 然后到达左边第三幅作品 (走动距离  2 2 2 \\sqrt\{2\} 22 ), 最后到达画廊终点 (走动距离  5 \\sqrt\{5\} 5 )。

总共距离为  2 + 2 + 5 + 2 + 2 + 2 2 + 5 ≈ 14.71 \\sqrt\{2\}+2+\\sqrt\{5\}+2+2+2 \\sqrt\{2\}+\\sqrt\{5\} \\approx 14.71 2\+2\+5\+2\+2\+22\+5≈14.71 。

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

对于  40 % 40 \\% 40% 的评测用例,  1 ≤ L , R ≤ 10 , 1 ≤ d ≤ 100 , 1 ≤ w ≤ 100 1 \\leq L, R \\leq 10,1 \\leq d \\leq 100,1 \\leq w \\leq 100 1≤L,R≤10,1≤d≤100,1≤w≤100 。

对于  70 % 70 \\% 70% 的评测用例，  1 ≤ L , R ≤ 100 , 1 ≤ d ≤ 1000 , 1 ≤ w ≤ 1000 1 \\leq L, R \\leq 100,1 \\leq d \\leq 1000,1 \\leq w \\leq 1000 1≤L,R≤100,1≤d≤1000,1≤w≤1000 。

对于所有评测用例,  1 ≤ L , R ≤ 500 , 1 ≤ d ≤ 100000 , 1 ≤ w ≤ 100000 1 \\leq L, R \\leq 500,1 \\leq d \\leq 100000,1 \\leq w \\leq 100000 1≤L,R≤500,1≤d≤100000,1≤w≤100000,  0 ≤ u 1 < u 2 < ⋯ < u L ≤ d , 0 ≤ v 1 < v 2 < ⋯ < v R ≤ d 。 0 \\leq u\_\{1\}<u\_\{2\}<\\cdots<u\_\{L\} \\leq d, 0 \\leq v\_\{1\}<v\_\{2\}<\\cdots<v\_\{R\} \\leq d 。 0≤u1<u2<⋯<uL≤d,0≤v1<v2<⋯<vR≤d。

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

## 试题 I: 补给 ##

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

**【问题描述】**

小蓝是一个直升飞机驾驶员, 他负责给山区的  n n n 个村庄运送物资。每个月,他都要到每个村庄至少一次, 可以多于一次, 将村座需要的物资运送过去。每个村庄都正好有一个直升机场, 每两个村庄之间的路程都正好是村庄之间的直线距离。

由于直升机的油箱大小有限, 小蓝单次飞行的距离不能超过  D D D 。每个直升机场都有加油站, 可以给直升机加满油。

每个月, 小蓝都是从总部出发, 给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。

总部位于编号为 1 的村庄。

请问, 要完成一个月的任务, 小蓝至少要飞行多长距离?

**【输入格式】**

输入的第一行包含两个整数  n , D n, D n,D, 分别表示村庄的数量和单次飞行的距离。

接下来  n n n 行描述村庄的位置, 其中第  i i i 行两个整数  x i , y i x\_\{i\}, y\_\{i\} xi,yi, 表示编号为  i i i 的村庄的坐标。村庄  i i i 和村庄  j j j 之间的距离为  ( x i − x j ) 2 + ( y i − y j ) 2 \\sqrt\{\\left(x\_\{i\}-x\_\{j\}\\right)^\{2\}+\\left(y\_\{i\}-y\_\{j\}\\right)^\{2\}\} (xi−xj)2\+(yi−yj)2 。

**【输出格式】**

输出一行, 包含一个实数, 四舍五入保留正好 2 位小数, 表示答案。

**【样例输入】**

4 10 \\begin\{array\}\{llll\}4&10\\end\{array\} 410

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

5 5 \\begin\{array\}\{llll\}5&5\\end\{array\} 55

1 5 \\begin\{array\}\{llll\}1&5\\end\{array\} 15

**【样例输出】**

16.00 \\begin\{array\}\{llll\}16.00\\end\{array\} 16.00

**【样例说明】**

四个村座形成一个正方形的形状。

**【样例输入】**

4 6 \\begin\{array\}\{llll\}4&6\\end\{array\} 46

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

4 5 \\begin\{array\}\{llll\}4&5\\end\{array\} 45

8 5 \\begin\{array\}\{llll\}8&5\\end\{array\} 85

1 11 \\begin\{array\}\{llll\}1&11\\end\{array\} 111

**【样例输出】**

28.00 \\begin\{array\}\{llll\}28.00\\end\{array\} 28.00

**【样例说明】**

补给顺序为  1 → 2 → 3 → 4 → 3 → 2 → 1 1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4 \\rightarrow 3 \\rightarrow 2 \\rightarrow 1 1→2→3→4→3→2→1 。

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

对于所有评测用例,  1 ≤ n ≤ 20 , 1 ≤ x i , y i ≤ 1 0 4 , 1 ≤ D ≤ 1 0 5 1 \\leq n \\leq 20,1 \\leq x\_\{i\}, y\_\{i\} \\leq 10^\{4\}, 1 \\leq D \\leq 10^\{5\} 1≤n≤20,1≤xi,yi≤104,1≤D≤105 。

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

## 试题 J 质数行者 ##

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

**【问题描述】**

小蓝在玩一个叫质数行者的游戏。

游戏在一个  n × m × w n \\times m \\times w n×m×w 的立体方格图上进行, 从北到南依次标号为第 1 行到第  n n n 行, 从西到东依次标号为第 1 列到第  m m m 列, 从下到上依次标号为第 1 层到第  w w w 层。

小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第  n n n 行第  m m m 列第  w w w层。每一步, 他可以向东走质数格、向南走质数格或者向上走质数格。每走到一个位置, 小蓝的角色要稍作停留。

在游戏中有两个陷阱, 分别为第  r 1 r\_\{1\} r1 行第  c 1 c\_\{1\} c1 列第  h 1 h\_\{1\} h1 层和第  r 2 r\_\{2\} r2 行第  c 2 c\_\{2\} c2 列第  h 2 h\_\{2\} h2 层。这两个陷阱的位置可以跨过，但不能停留。也就是说，小蓝不能控制角色某一步正好走到陷阱上，但是某一步中间跨过了陷阴是允许的。

小蓝最近比较清闲, 因此他想用不同的走法来完成这个游戏。所谓两个走法不同，是指小蓝稍作停留的位置集合不同。

请帮小蓝计算一下, 他总共有多少种不同的走法。

提示: 请注意内存限制, 如果你的程序运行时超过内存限制将不得分。

**【输入格式】**

输入第一行包含两个整数  n , m , w n, m, w n,m,w, 表示方格图的大小。

第二行包含 6 个整数,  r 1 , c 1 , h 1 , r 2 , c 2 , h 2 r\_\{1\}, c\_\{1\}, h\_\{1\}, r\_\{2\}, c\_\{2\}, h\_\{2\} r1,c1,h1,r2,c2,h2, 表示陷阱的位置。

**【输出格式】**

输出一行, 包含一个整数, 表示走法的数量。答案可能非常大, 请输出答案除以 1000000007 的余数。

**【样例输入】**

5 6 1 \\begin\{array\}\{llll\}5&6&1\\end\{array\} 561

3 4 1 1 2 1 \\begin\{array\}\{llllllll\}3 & 4 & 1 & 1 & 2 & 1\\end\{array\} 341121

**【样例输出】**

11 \\begin\{array\}\{llll\}11\\end\{array\} 11

**【样例说明】**

用  ( r , c , h ) (r, c, h) (r,c,h) 表示第  r r r 行第  c c c 列第  h h h 层, 可能的走法有以下几种:

1.   ( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(1,3,1)-(1,6,1)-(3,6,1)-(5,6,1) (1,1,1)−(1,3,1)−(1,6,1)−(3,6,1)−(5,6,1)。
2.   ( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 3 , 3 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(1,3,1)-(3,3,1)-(3,6,1)-(5,6,1) (1,1,1)−(1,3,1)−(3,3,1)−(3,6,1)−(5,6,1) 。
3.   ( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 3 , 3 , 1 ) − ( 5 , 3 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(1,3,1)-(3,3,1)-(5,3,1)-(5,6,1) (1,1,1)−(1,3,1)−(3,3,1)−(5,3,1)−(5,6,1) 。
4.   ( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 3 , 3 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(3,1,1)-(3,3,1)-(3,6,1)-(5,6,1) (1,1,1)−(3,1,1)−(3,3,1)−(3,6,1)−(5,6,1)。
5.   ( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 3 , 3 , 1 ) − ( 5 , 3 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(3,1,1)-(3,3,1)-(5,3,1)-(5,6,1) (1,1,1)−(3,1,1)−(3,3,1)−(5,3,1)−(5,6,1) 。
6.   ( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 5 , 1 , 1 ) − ( 5 , 3 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(3,1,1)-(5,1,1)-(5,3,1)-(5,6,1) (1,1,1)−(3,1,1)−(5,1,1)−(5,3,1)−(5,6,1) 。
7.   ( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 5 , 1 , 1 ) − ( 5 , 4 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(3,1,1)-(5,1,1)-(5,4,1)-(5,6,1) (1,1,1)−(3,1,1)−(5,1,1)−(5,4,1)−(5,6,1) 。
8.   ( 1 , 1 , 1 ) − ( 1 , 4 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(1,4,1)-(1,6,1)-(3,6,1)-(5,6,1) (1,1,1)−(1,4,1)−(1,6,1)−(3,6,1)−(5,6,1)。
9.   ( 1 , 1 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(1,6,1)-(3,6,1)-(5,6,1) (1,1,1)−(1,6,1)−(3,6,1)−(5,6,1) 。
10.  ( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(3,1,1)-(3,6,1)-(5,6,1) (1,1,1)−(3,1,1)−(3,6,1)−(5,6,1) 。
11.  ( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 5 , 1 , 1 ) − ( 5 , 6 , 1 ) (1,1,1)-(3,1,1)-(5,1,1)-(5,6,1) (1,1,1)−(3,1,1)−(5,1,1)−(5,6,1) 。

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

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

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

对于所有评测用例,  1 ≤ n , m , w ≤ 1000 , 1 ≤ r 1 , r 2 ≤ n , 1 ≤ c 1 , c 2 ≤ m 1 \\leq n, m, w \\leq 1000,1 \\leq r\_\{1\}, r\_\{2\} \\leq n, 1 \\leq c\_\{1\}, c\_\{2\} \\leq m 1≤n,m,w≤1000,1≤r1,r2≤n,1≤c1,c2≤m,  1 ≤ h 1 , h 2 ≤ w 1 \\leq h\_\{1\}, h\_\{2\} \\leq w 1≤h1,h2≤w, 陷阴不在起点或终点, 两个陷阱不同。

[Link 1]: https://www.captainbed.cn/dl
[7fe03399da84432a873315bb6c162a42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/299649ac5a4742838a86f167ae4d454a.png
[814d603ef4694428a3ee05a412bd080f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/af13b043c99743ec9e2b7c1eceacd090.png
[c52d498108194860b10233be18005cc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/00dc77d7f133417885bdbd037292fe8d.png
[0c14c702e600456c8d464ca005541de2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/1f3d40f29e544b91a63dd0b6b67ae1b4.png