yl-9/probench huggingface dataset:
# 虫洞操纵者

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$你需要在一个可以上下左右移动的 $n\times n$ 棋盘上解开一个迷宫：棋盘四周都是墙；每个方格要么是可以通过的空方格 $\sf '0'$ ，要么是不可通过的墙方格 $\sf '1'$ ；你可以沿着空方格通行；你已经被传送到了迷宫的左上角（第 $1$ 行第 $1$ 列的位置），你知道终点位于迷宫右下角（第 $n$ 行第 $n$ 列的位置）。  
$\,\,\,\,\,\,\,\,\,\,$别人都不知道的是，你是一个虫洞大师，当你所在的位置能同时看到左右两侧或上下两侧**最近** 的那两面相对的墙时，你可以在这两面墙上开启虫洞，**靠近后** 从一侧进入，穿越它到达另一侧。  
$\,\,\,\,\,\,\,\,\,\,$现在，你准备好以最短的步数离开迷宫了吗！

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\left(2\le n \le 10^3\right)$ 代表迷宫的大小。
    
    $\,\,\,\,\,\,\,\,\,\,$此后 $n$ 行，第 $i$ 行输入 $n$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,n} \left(0\le a_{i,j}\le 1\right)$ 代表迷宫中第 $i$ 行第 $j$ 列这个格子中的情况，其中 $0$ 代表空方格，$1$ 代表墙方格。保证起点和终点不为墙壁。  
    

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表离开迷宫需要的最短步数，如果无论如何都无法离开迷宫，则直接输出 $-1$ 。

示例1 

## 输入
    
    
    5
    0 0 0 1 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 1 0
    1 0 0 0 0

## 输出
    
    
    3

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$该样例示意图如下图所示。全部墙壁的位置都使用粗黑线标注。先从 $(1,1)$ 向右移动一步走到 $(1,2)$ ，此时可以开启一个虫洞（使用紫色箭头标注），向上移动一步到达 $(5,2)$ ；此时可以开启第二个虫洞（使用红色箭头标注），向左移动一步到达 $(5,5)$ 。  
    
    
    $\,\,\,\,\,\,\,\,\,\,$![](https://uploadfiles.nowcoder.com/images/20240811/0_1723373440781/F51BE5B71BB1ED0C538001A9CB832C36)
    
    $\,\,\,\,\,\,\,\,\,\,$注意，在该样例中，不能直接从 $(1,1)$ 开启虫洞（使用黑色箭头标注）到达 $(1,5)$ ，因为 $(1,4)$ 存在两面墙遮挡了视线；不能直接从 $(4,3)$ 开启虫洞（使用绿色箭头标注）到达 $(1,3)$ ，因为这两面墙不是相对的。  
    
    
    $\,\,\,\,\,\,\,\,\,\,$![](https://uploadfiles.nowcoder.com/images/20240811/0_1723372709548/75B08F0B186811E6ED62E8067AD5032E)  
    

示例2 

## 输入
    
    
    5
    0 0 0 1 0
    1 1 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 1 0

## 输出
    
    
    5

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$![](https://uploadfiles.nowcoder.com/images/20240811/0_1723376004123/386C5E360446BCD8843283F26300E0F5)

示例3 

## 输入
    
    
    2
    0 1
    1 0

## 输出
    
    
    -1


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 搜索
Difficulty: 1300
# 小红的序列乘积2.0

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$对于一个长度为 $m$ 的整数序列 $\\{b_1,b_2,\dots,b_m\\}$，定义 $f_i = b_1 \times b_2 \times \cdots \times b_i$ ，即前 $i$ 项的乘积。这个序列的权值即为 $f_1, f_2, \dots, f_m$ 中个位数是 $6$ 的数字个数。

$\,\,\,\,\,\,\,\,\,\,$小红有一个长度为 $n$ 的整数序列 $\\{a_1,a_2,\dots,a_n\\}$，她想知道这个序列全部 $2^n-1$ 个非空 _子序列_ 的权值和是多少。 

  


$\,\,\,\,\,\,\,\,\,\,$如果序列 $a$ 可以通过删除序列 $b$ 中的若干（可能为零或全部）元素得到，则序列 $a$ 是序列 $b$ 的 _子序列_ 。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n \left(1 \leq n \leq 10^5\right)$ 代表序列中元素的数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n \left(1 \leq a_i \leq 10^9\right)$ 代表序列元素。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，输出一个整数，表示全部子序列的权值和。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

示例1 

## 输入
    
    
    3
    4 4 6

## 输出
    
    
    4

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于子序列 $[4]$ ，没有贡献；  
    $\,\,\,\,\,\,\,\,\,\,$对于子序列 $[6]$ ，$f=\{6\}$ 贡献为 $1$ ；  
    $\,\,\,\,\,\,\,\,\,\,$对于子序列 $[4,4]$ ，$f=\{4,16\}$ 贡献为 $1$ ；  
    $\,\,\,\,\,\,\,\,\,\,$对于子序列 $[4,6]$ ，$f=\{4,24\}$ ，没有贡献；  
    $\,\,\,\,\,\,\,\,\,\,$对于子序列 $[4,4,6]$ ，$f=\{4,16,96\}$ 贡献为 $2$ 。

示例2 

## 输入
    
    
    5
    1 2 3 4 4

## 输出
    
    
    12


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 动态规划
Difficulty: 1700
# 灯下定影

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$为了省电，W星的灯都是感应灯，有人进入到感应区域后立即亮起（包含边界），在人离开区域后延迟一定时间熄灭。当然，如果在此期间有其他人进入感应区域，则重新开始计时。  
$\,\,\,\,\,\,\,\,\,\,$已知感应区域是以灯所在位置为中心的一个圆，有一些人同时从初始位置出发、沿给定的**向量方向** 、以给定的速度运动。  
$\,\,\,\,\,\,\,\,\,\,$你能求解出路灯亮起的总时间吗。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入三个整数 $x_0,y_0$ 和 $r\ (-1000 \leq x_0,y_0 \le 1000;\ 1\le r \le 100)$ 代表灯所在的位置和灯的感应区域半径。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入两个整数 $n$ 和 $x\ (1\le n \le 10^5;\ 0\le x \le 1000)$ 代表行人人数和延迟熄灭时间。  
    $\,\,\,\,\,\,\,\,\,\,$此后 $n$ 行，每行输入五个小数点后位数不超过 $9$ 位的实数 $u_s,v_s,u_e,v_e$ 和 $s\ (-1000 \le u_s,v_s,u_e,v_e\le 1000;\ 1\le s \le 1000)$ 代表行人初始位置、**前进路线上的另一个点（注意不是终点）** 与移动速度，保证 $(u_s,v_s)\neq(u_e,v_e)$ 且 $(u_s,v_s)$ 不位于灯的感应区域内。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个实数，代表路灯亮起的总时间。如果相对误差或绝对误差不超过 $10^{-6}$ ，您的答案将被接受。具体来说，设您的答案为 $a$ ，裁判的答案为 $b$ ，当且仅当 $\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$ 时，您的答案将被接受。

示例1 

## 输入
    
    
    4 2 6
    3 2
    14 -6 8 -4 1
    10 4 0 -4 1
    8.00 -4.000 0.00 -4.000 1

## 输出
    
    
    17.719185869293

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$该样例的示意图见下方所示。  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 对于第一个行人，其到达和离开感应区域的时间分别为 $t_{{\rm in}_1}=7.96696376$ 和 $t_{{\rm out}_1}=16.06634645$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 对于第二个行人，其到达和离开感应区域的时间分别为 $t_{{\rm in}_2}=0.34716059$ 和 $t_{{\rm out}_2}=11.52204531$ ;  
    $\,\,\,\,\,\,\,\,\,\,$所以，从 $t_{{\rm in}_2}$ 到 $t_{{\rm out}_1}$ 这段时间路灯一直都是亮着的，$t_{{\rm out}_1}$ 时刻之后，路灯延迟 $2$ 秒关闭。  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 对于第三个行人，其到达和离开感应区域的时间均为 $t_{{\rm in}3}=t_{{\rm out}_3}=2$ ；  
    $\,\,\,\,\,\,\,\,\,\,$最终亮起总时间 $t_{{\rm out}1}-t_{{\rm in}_2}+2=17.719186$ 。
    
    $\,\,\,\,\,\,\,\,\,\,$![](https://uploadfiles.nowcoder.com/images/20240805/0_1722853291521/7BFD8C3F740F11E09F98DBCE048DC47B)

示例2 

## 输入
    
    
    -6 -9 9
    5 0
    -10 1 -3 -7 1
    4 -7 -2 0 1
    -7 1 -2 5 1
    3 -6 -2 9 1
    -9 4 -2 -1 1.000000001

## 输出
    
    
    16.519229877697


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

Tags: 计算几何, 数据结构, STL
Difficulty: 2000
# 清楚姐姐的糖葫芦

## 题目描述

> $\,\,\,\,\,\,\,\,\,\,$清楚年少时，随家人各处跑商。一日，车马歇于野外树林歇息，遇一老妪叫卖糖葫芦：“三文一串，十文三串……”  
>  $\,\,\,\,\,\,\,\,\,\,$清楚算了算，觉其价高，非善贾也，遂摇首拒之：“NO喵”。  
>  $\,\,\,\,\,\,\,\,\,\,$但是很想吃糖葫芦，于是决定自己动手。 

$\,\,\,\,\,\,\,\,\,\,$清楚姐姐很喜欢串糖葫芦，现在给你一个糖葫芦字符串，请你数一下有多少颗糖葫芦。 

$\,\,\,\,\,\,\,\,\,\,$糖葫芦字符串是一个只包含字符 $\rm o$ 和字符 $-$ 的字符串，其中，$\rm o$ 代表糖葫芦，$-$ 代表木棍。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入一个长度不超过 $10^3$ 且只由字符 $\rm o$ 和 $-$ 构成的字符串 $s$ ，代表糖葫芦串。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表糖葫芦的数量 。

示例1 

## 输入
    
    
    --ooo--

## 输出
    
    
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 模拟
Difficulty: 400
# 清楚姐姐买竹鼠

## 题目描述

> $\,\,\,\,\,\,\,\,\,\,$清楚十五六岁时进京赶考，途经一处山村，忽见一铺专卖竹鼠。竹鼠很贵，但是竹鼠很可爱！  
>  $\,\,\,\,\,\,\,\,\,\,$先等等。遂清点囊中碎银。可以上了。它说，可以上了！ 

$\,\,\,\,\,\,\,\,\,\,$清楚姐姐买竹鼠，$a$ 元可以买一只竹鼠，$b$ 元可以买三只竹鼠，问至少买 $x$ 只竹鼠要花多少钱。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入三个整数 $a,b$ 和 $x\ (1\leq a, b, x \leq 10^9)$ ，其含义已在题目中声明。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数表示至少买 $x$ 只竹鼠要花多少钱。

示例1 

## 输入
    
    
    4 10 10

## 输出
    
    
    34

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$花费 $3\times b = 30$ 元买 $9$ 只竹鼠，再花费 $1\times a = 4$ 元买 $1$ 只竹鼠，共花费 $34$ 元。我们可以证明，没有更优的购买方式。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 数学, 贪心
Difficulty: 500
# 竹鼠饲养物语

## 题目描述

> $\,\,\,\,\,\,\,\,\,\,$清楚进店，见一老妪端坐其中，竟是当年卖糖葫芦那厮。  
>  $\,\,\,\,\,\,\,\,\,\,$老妪也认出了清楚，率先开口：“有缘千里来相会，你买下竹鼠，我带你去探寻宝物”。  
>  $\,\,\,\,\,\,\,\,\,\,$言毕，见清楚执意要买，又添一句：“还需出饲料钱。”

$\,\,\,\,\,\,\,\,\,\,$鼠鼠快速成长饲料一共分为 $m$ 个等级，初始时全部竹鼠都是零级竹鼠，投喂一袋“鼠鼠快速成长饲料 $\rm I$ ”可以升级为一级竹鼠，继续投喂“鼠鼠快速成长饲料 $\rm II$ ”可以升级为二级竹鼠，……。需要注意的是，你不能越级投喂，例如，向零级竹鼠投喂“鼠鼠快速成长饲料 $\rm II$ ”没有任何效果。

$\,\,\,\,\,\,\,\,\,\,$清楚一共有 $n$ 袋饲料和无限多的零级竹鼠，问最多可以进行多少次有效投喂。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行上输入两个整数 $n,m\ (1\le n\le 10^5;\ 1\le m \le 10^9)$ 代表饲料数量和饲料等级数量。
    
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1\le a_i \le m)$ 代表每一袋饲料的等级。  
    

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表清楚至多进行的有效投喂次数。

示例1 

## 输入
    
    
    7 5
    1 1 1 2 2 3 5

## 输出
    
    
    6

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$● 可以将第一只竹鼠直接升到三级，此时剩下 $4$ 袋饲料 $\{1,1,2,5\}$ ；
    
    $\,\,\,\,\,\,\,\,\,\,$● 将第二只竹鼠升到两级，此时剩下 $2$ 袋饲料 $\{1,5\}$ ；
    
    $\,\,\,\,\,\,\,\,\,\,$● 将第三只竹鼠升到一级，此时剩下最后 $1$ 袋饲料 $\{5\}$ ；
    
    $\,\,\,\,\,\,\,\,\,\,$最后一袋饲料无法使任何竹鼠升级，故最终使用了 $6$ 袋饲料。  
    

示例2 

## 输入
    
    
    6 114514
    1 1 4 5 1 4

## 输出
    
    
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 数学, 贪心
Difficulty: 600
# 清楚姐姐跳格子

## 题目描述

> $\,\,\,\,\,\,\,\,\,\,$老妪遂递一羊皮卷轴，上面什么都没有，清楚欲问，老妪却缄口不言。  
>  $\,\,\,\,\,\,\,\,\,\,$清楚性格刚直，放下鼠资，正欲再问，忽觉眼前一花，老妪和店铺却都消失不见，唯卷轴与竹鼠。  
>  $\,\,\,\,\,\,\,\,\,\,$“怪哉”，清楚回头走，见到地上有一些格子。 

$\,\,\,\,\,\,\,\,\,\,$清楚正在玩跳格子游戏。地上有 $n$ 个格子，清楚一开始在 $1$ 号格子，目标是 $n$ 号格子。 

$\,\,\,\,\,\,\,\,\,\,$第 $i$ 个格子上有一个数字 $a_i$ ，清楚在这个格子上可以往左右两边选一个方向，然后选择 $a_i$ 的一个正整数因子作为长度，进行一次跳跃，但是不可以跳出边界。  
$\,\,\,\,\,\,\,\,\,\,$请问清楚最少跳多少步，就可以到达 $n$ 号格子。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (\ 1 \leq n \leq 10^3\ )$ 代表格子数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (\ 1 \leq a_i \leq 10^{18}\ )$ 代表格子上的数字。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表到达终点需要的最少步数 。

示例1 

## 输入
    
    
    5
    2 3 1 5 4

## 输出
    
    
    2

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$在 $1$ 号节点 ，选择 $a_1$ 的因子 $1$ ，往右跳 $1$ 步，到达 $2$ 号节点。  
    $\,\,\,\,\,\,\,\,\,\,$在 $2$ 号节点 ，选择 $a_2$ 的因子 $3$ ，往右跳 $3$ 步，到达 $5$ 号节点。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 质因数分解, 搜索, 数论
Difficulty: 1000
# 清楚姐姐的布告规划

## 题目描述

> $\,\,\,\,\,\,\,\,\,\,$待榜之期，漫长如年。为自己和竹鼠们的生计，清楚在京师寻得一份张贴布告之差事，既可糊口，亦广交良朋，共商寻宝大业。 
> 
> $\,\,\,\,\,\,\,\,\,\,$某日，清楚在张贴布告时，浆糊不慎落于羊皮卷上，湿透之处，竟现复杂图形…… 

$\,\,\,\,\,\,\,\,\,\,$清楚需要在长度为 $n$ 个单位的布告板上张贴至多 $n$ 张布告，第 $i$ 张布告的长度为 $a_i$ 个单位，如果选择第 $i$ 张贴布告时需要满足： 

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 第 $i$ 张布告必须要覆盖掉布告板的第 $i$ 个位置；  


$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 布告不能够相互重叠，但是可以紧贴。

$\,\,\,\,\,\,\,\,\,\,$清楚想要知道自己按照要求，至少需要张贴几张布告，才能将布告板贴满。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1\le T\le 100)$ 代表数据组数，每组测试数据描述如下：  
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1   \leq n \leq   5000)$ 代表布告板的长度（同时也代表布告的张数）。
    
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1 \leq a_i \leq n)$ 代表每一张布告的长度。  
    $\,\,\,\,\,\,\,\,\,\,$除此之外，保证所有的 $n$ 之和不超过 $5000$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，在一行上输出一个整数代表清楚至少需要贴的布告数量；如果无解，直接输出 $-1$ 。

示例1 

## 输入
    
    
    2
    4
    1 2 2 3
    3
    2 2 2

## 输出
    
    
    2
    -1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于第一组测试数据，有两种合法的选择方式：  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 贴第一、四张布告；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 贴第二、三张布告；  
    $\,\,\,\,\,\,\,\,\,\,$对于第二组测试数据，无论怎么张贴都会有重叠部分。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 背包问题, 动态规划
Difficulty: 1300
# 竹鼠，宝藏与故事

## 题目描述

> $\,\,\,\,\,\,\,\,\,\,$收工回店，清楚开始仔细研究这些图形。竹鼠忽开口言：“蒙君饱腹之恩，吾等当助君得宝。“言罢，摇身一变，化作数道白光没入轴中，清楚定睛一看，方觉卷轴乃一微型迷宫也。 
> 
> $\,\,\,\,\,\,\,\,\,\,$迷宫曲折，然竹鼠数量众多、各行其道，不消片刻，白光再现，宝物尽数被带出。 

$\,\,\,\,\,\,\,\,\,\,$$n \times m$ 的迷宫中有无数珍宝，左上角为迷宫的起点，右下角为终点。我们使用数字 $-1$ 标记这个格子无法被通过；使用自然数来代表这个格子上宝藏的珍惜程度（数字为 $0$ 即代表该位置上不存在宝藏）。现在，你需要找出所有从起点出发、直达终点的 _简单路径_ ，输出这些路径上的宝藏珍惜度之和。

$\,\,\,\,\,\,\,\,\,\,$请注意，每一份宝藏只能被取一次。若某一条路径已经取走了 $A$ 处的宝藏，那么当另一条路径也经过 $A$ 处时，将无法再取。

$\,\,\,\,\,\,\,\,\,\,$这里的 _简单路径_ 是指从起点出发，每一步都可以选择上下左右任意一个方向行走（前提是目标格可以通行），且路径上的每一个格子至多只经过一次，最终到达终点的路径。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入两个整数 $n$ 和 $m\ (2 \le n,m \le 1000)$ ，代表迷宫的长和宽。  
    $\,\,\,\,\,\,\,\,\,\,$此后 $n$ 行，每行输入 $m$ 个数字 $a_1,a_2,\dots,a_m\ (-1 \le a_i \le 10^9)$ ，表示迷宫中这一行的情况，其中 $-1$ 表示该单元格无法通行。第一行第一个字符必定不为 $-1$ ，代表起点；最后一行最后一个字符必定不为 $-1$ ，代表终点。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表所有直达终点的路径上的宝藏数量。

示例1 

## 输入
    
    
    3 4
    0 1 -1 9
    0 -1 1 -1
    0 0 0 0

## 输出
    
    
    0

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$如下图所示，只有唯一的路径可以直达终点，而这条路径上没有宝藏，所以答案为 $0$ 。
    
    $\,\,\,\,\,\,\,\,\,\,$![](https://uploadfiles.nowcoder.com/images/20240705/0_1720152547385/FC204CCF57B73E7EA0CE6ED8E16F1142)

示例2 

## 输入
    
    
    4 4
    0 1 0 3
    0 -1 1 0
    0 -1 -1 0
    2 -1 0 0

## 输出
    
    
    5

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$如下图所示，一共有两条直达终点的路径，虽然两条路径都经过了第一行第二列的宝藏单元格，但每份宝藏只能被取一次，所以最终答案仍为 $1+3+1=5$ 。
    
    ![](https://uploadfiles.nowcoder.com/images/20240705/0_1720152631064/56215C9E9E0E45C8334E75B0DDCD3071)


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 图论, 连通性
Difficulty: 2200
# 小红小紫投硬币

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红和小紫玩投硬币游戏，小紫投了 $n$ 枚硬币，小红投了 $n + 1$ 枚硬币。硬币都是质地均匀的、且每次投掷正面反面的概率相等均为 $\frac{1}{2}$ 。  
$\,\,\,\,\,\,\,\,\,\,$小红想知道，她投的硬币正面朝上的次数比小紫投的硬币正面朝上的次数多的概率是多少。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1 \leq n \leq 2 \times 10^5)$ 表示小紫投的硬币数。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$输出一个实数，表示小红投的硬币正面朝上的次数比小紫投的硬币正面朝上的次数多的概率，为了减少计算过程中误差带来的影响，当你的输出与标准答案的误差不超过 $10^{-6}$ 时，均被视为正确。  
    $\,\,\,\,\,\,\,\,\,\,$具体的说，使用 $a$ 代表你的答案，使用 $b$ 代表标准答案，当 $\dfrac{|a-b|}{\max(1,b)}\le 10^{-6}$ 成立时， $a$ 被视为正确答案。

示例1 

## 输入
    
    
    2

## 输出
    
    
    0.500000

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$小红的投掷结果有 8 种情况：{正，正，正}，{正，正，反}，{正，反，正}，{反，正，正}，{正，反，反}，{反，正，反}，{反，反，正}，{反，反，反}。  
    $\,\,\,\,\,\,\,\,\,\,$小紫的投掷结果有 4 种情况：{正，正}，{正，反}，{反，正}，{反，反}。  
    $\,\,\,\,\,\,\,\,\,\,$一共有 $32$ 种情况，其中小红投的硬币正面朝上的次数比小紫投的硬币正面朝上的次数多的情况有 $16$ 种，所以概率是 $\frac{1}{2}$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 数学, 概率期望
# 小红的字符串

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有一个长度为 $n$ 的字符串 $s$ ，她可以执行以下操作：  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 选择一个索引 $i$ ，将 $s_i$ 的字母右移替换为字母表中的下一个字母。例如：'$\rm a$' 右移一位为 '$\rm b$' ，特别的，'$\rm z$' 右移一位为 '$\rm a$' 。  
$\,\,\,\,\,\,\,\,\,\,$现在请你帮助小红求出把 $s$ 变成 _回文串_ 的最少操作次数。  
$\,\,\,\,\,\,\,\,\,\,$一个字符串被称作 _回文串_ 当且仅当这个字符串从左往右读和从右往左读都是相同的，例如 "$\rm level$" 、"$\rm reder$" 都是回文串。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入一个长度不超过 $1000$ 且仅由小写字母构成的字符串字符串 $s$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表把 $s$ 变成回文串的最少操作次数。

示例1 

## 输入
    
    
    abcd

## 输出
    
    
    4

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$其中一个可行操作的方案是 "$\rm dccd$" 。

示例2 

## 输入
    
    
    nuhhhh

## 输出
    
    
    19


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 贪心
# 小红的 01 消除

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有一个长度为 $n$ 且仅由 '$\rm 0$' 和 '$\rm 1$' 构成的字符串 $s$，她有以下三种操作：  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 删除任意一个子串 "$11$"，例如 "$01101$" 操作之后变成 "$001$"；  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 删除任意一个子串 "$01$"，例如 "$01101$" 操作之后变成 "$101$" 或者 "$011$"；  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 删除任意一个子串 "$00$"，例如 "$00100$" 操作之后变成 "$100$" 或者 "$001$" 。  
$\,\,\,\,\,\,\,\,\,\,$ 小红至多可以执行操作一 $x$ 次、操作二 $y$ 次、操作三 $z$ 次，问小红最多可以执行多少次操作二。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1 \leq n \leq 10^5)$ 代表字符串的长度 。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入一个长度为 $n$ 且仅由 '$\rm 0$' 和 '$\rm 1$' 构成的字符串 $s$ 。  
    $\,\,\,\,\,\,\,\,\,\,$第三行输入三个整数 $x, y, z\ (0 \leq x, y, z \leq 10^5)$ 代表各个操作至多执行的次数。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表小红最多可以执行多少次操作二。

示例1 

## 输入
    
    
    7
    1110011
    3 3 3

## 输出
    
    
    2

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$先执行一次操作一，得到 "$10011$"；再执行一次操作二，得到 "$101$"；再执行一次操作二，得到 "$1$"。
    
    $\,\,\,\,\,\,\,\,\,\,$最多可以执行两次操作二。

示例2 

## 输入
    
    
    6
    110010
    0 1 0

## 输出
    
    
    1


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数据结构, 栈, 模拟
# 小红组比赛

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红希望出一场题目，但是他的实力又不够，所以他想到可以从以前的比赛中各抽一题，来组成一场比赛。不过一场比赛的难度应该是有限制的，所以所以这一场比赛会给一个目标难度分数 $\rm target$ 。  
$\,\,\,\,\,\,\,\,\,\,$小红选 $n$ 场比赛，每场 $m$ 个题，小红会从每一场选一道题，使其组成的题的难度分数尽量接近 $\rm target$ 。小红想知道挑选的题的难度分数与 $\rm target$ 相差的最小值是多少。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入两个整数 $n, m\ (1 \leq n \leq 100, 1 \leq m \leq 20)$ 代表小红选了 $n$ 场比赛，每场比赛有 $m$ 道题。  
    $\,\,\,\,\,\,\,\,\,\,$此后 $n$ 行，第 $i$ 行输入 $m$ 个整数 $a_{i,j}\ (1 \leq a_{i,j} \leq 50)$ 代表第 $i$ 场比赛的第 $j$ 道题的难度分数。  
    $\,\,\,\,\,\,\,\,\,\,$最后一行输入一个整数 ${\rm target}\ (1 \leq  {\rm target} \leq 5000)$ 代表小红希望这一场比赛的难度分数。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，表示挑选的题的难度分数与 $\rm target$ 相差的最小值。

示例1 

## 输入
    
    
    3 3
    1 4 7
    2 5 8
    3 6 9
    10

## 输出
    
    
    1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$小红可以选第一场比赛的第一道题，第二场比赛的第一道题，第三场比赛的第二道题，这样挑选的题的难度分数为 $1 + 2 + 6 = 9$，与 $\rm target$ 相差的最小值为 $1$。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 背包问题, 动态规划
# 折半丢弃

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$已知长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ，定义一次操作的过程为：选择任意一个元素，随后，将 $\left \lfloor \dfrac{a_i}{2} \right \rfloor$（向下取整）添加到原序列的结尾，并将 $a_i$ 从原序列中删除。  
$\,\,\,\,\,\,\,\,\,\,$你可以进行任意多次操作（也可以一次操作都不做），要求使得序列的 $\rm MEX$ 最大。  
$\,\,\,\,\,\,\,\,\,\,$数组的 $\rm MEX$ 定义为：没有出现在数组中的最小非负整数，例如，数组 $\\{3,1,2\\}$ 的 $\rm MEX$ 为 $0$ 。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多个测试点。第一行输入一个整数 $T\ (1\le T\le 10^4)$ 代表测试数据组数，每组测试数据描述如下：  
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1\le n\le 10^5)$ ，代表序列的长度。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (0\le a_i \le 10^6)$ 。数字彼此间通过空格间隔。  
    $\,\,\,\,\,\,\,\,\,\,$除此之外，保证所有的 $n$ 之和不超过 $10^5$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一个测试点，在一行上输出一个整数，代表当前序列的最大 $\rm MEX$ 。

示例1 

## 输入
    
    
    4
    6
    0 1 2 4 8 12
    5
    1 2 4 8 12
    4
    0 1 3 4
    10
    1 1 1 2 1 3 2 2 1 1

## 输出
    
    
    5
    5
    4
    4

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于第一个测试点：  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 操作第 $6$ 个元素 $12$ ，随后将 $\left \lfloor \dfrac{12}{2} \right \rfloor=6$ 加入到序列结尾，新的序列为 $\{0,1,2,4,8,6\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 继续操作刚刚新加入的元素 $6$ ，随后将 $\left \lfloor \dfrac{6}{2} \right \rfloor=3$ 加入到序列结尾，新的序列为 $\{0,1,2,4,8,3\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,$此时，得到原序列的最大 $\rm {MEX}$ 为 $5$ 。可以穷举证明此时没有比 $5$ 更大的答案。  
    $\,\,\,\,\,\,\,\,\,\,$对于第二个测试点：  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 操作第 $5$ 个元素，新的序列为 $\{1,2,4,8,6\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 继续操作第 $5$ 个元素，新的序列为 $\{1,2,4,8,3\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 选择第 $4$ 个元素操作，新的序列为 $\{1,2,4,3,4\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 选择第 $3$ 个元素操作，新的序列为 $\{1,2,3,4,2\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 选择第 $2$ 个元素操作，新的序列为 $\{1,3,4,2,1\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 最后选择第 $1$ 个元素，新的序列为 $\{3,4,2,1,0\}$ ；  
    $\,\,\,\,\,\,\,\,\,\,$此时，得到答案 $\rm MEX$ 为 $5$ 。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 构造, 贪心, 二分, 分治
# 小红走矩阵

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$$n \times m$ 的矩阵由障碍和空地组成，初始时小红位于起点 $(1, 1)$ ，她想要前往终点 $(n,m)$ 。小红每一步可以往上下左右四个方向的空地移动一格。  
$\,\,\,\,\,\,\,\,\,\,$小红在起点处可以进行最多一次操作：选择矩阵中的一处障碍替换为空地，但代价是小红必须选择失去向上下左右四个方向中一个移动的能力。  
$\,\,\,\,\,\,\,\,\,\,$求小红从起点到达终点的最小步数，如果无法到达则输出 $-1$ 。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入两个整数 $n, m\ (1 \leq n, m \leq 1000)$ 代表矩阵的大小。  
    $\,\,\,\,\,\,\,\,\,\,$此后 $n$ 行，每行输入 $m$ 个字符 $a_1a_2\dots a_n\ (a_i\in\{$'$\rm X$','$\rm .$'$\})$ 描述矩阵中这一行的情况，其中 '$\rm X$'（Ascii：88）代表障碍，'$\rm .$'（Ascii：46）代表空地。保证起点和终点都是空地。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，表示小红从起点到达终点的最小步数；如果无论怎么操作都无法到达，则直接输出 $-1$ 。

示例1 

## 输入
    
    
    4 4
    ..X.
    XXX.
    .X..
    .X..

## 输出
    
    
    6

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$小红失去向上走的能力，消除 $(1, 3)$ 处障碍，从起点到终点的最小步数为 $6$ 。

示例2 

## 输入
    
    
    4 4
    .XX.
    XXX.
    .X..
    .X..

## 输出
    
    
    -1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$小红最多只能删除一个障碍，无法到达终点。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 广度优先搜索(BFS), 搜索
# 游游的删点直径

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$游游拿到了一棵树，她定义 $f(i)$ 为：不经过 $i$ 号节点的所有路径中，最长的路径长度。特殊的，如果所有长度不小于1的路径都经过 $i$ 号节点，则 $f(i)=0$ 。  
$\,\,\,\,\,\,\,\,\,\,$现在游游希望你分别求出 $f(1)$ 到 $f(n)$ 的全部的值。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1\le n \le 10^5)$ 代表树的节点数量。  
    
    
    $\,\,\,\,\,\,\,\,\,\,$此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leq u_i, v_i \leq n;\ u_i \neq v_i)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证树联通，没有重边。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$一共需要输出 $n$ 行，第 $i$ 行输出一个整数代表 $f(i)$ 的值。

示例1 

## 输入
    
    
    3
    1 2
    2 3

## 输出
    
    
    1
    0
    1

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$不经过一号节点的最长路径为 $2\to 3$，长度为 $1$；  
    $\,\,\,\,\,\,\,\,\,\,$所有长度不小于 $1$ 的路径都会经过二号节点，因此输出 $0$ ；  
    $\,\,\,\,\,\,\,\,\,\,$不经过三号节点的最长路径为 $1\to 2$ ，长度为 $1$。  
    

示例2 

## 输入
    
    
    5
    1 2
    1 3
    1 4
    1 5

## 输出
    
    
    0
    2
    2
    2
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 动态规划, 树形dp
# 两数之和

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$对于给定的正整数 $z$ ，你需要寻找两个不同的正整数 $x$ 和 $y$ ，使得 $x+y=z$ 成立。 

$\,\,\,\,\,\,\,\,\,\,$如果不存在这样的 $x$ 和 $y$ ，你只需要输出 $\rm NO$ 。 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入一个整数 $z\ (1 \le z \le 2 \cdot 10^5)$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$如果存在符合要求的答案，你需要先输出 $\rm YES$ ，随后在第二行上输出两个正整数 $x$ 和 $y$ 代表你的答案；否则，直接输出 $\rm NO$ 。

示例1 

## 输入
    
    
    2

## 输出
    
    
    NO

示例2 

## 输入
    
    
    3

## 输出
    
    
    YES
    1 2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 数学
# 小红装匣子

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有 $a$ 块 $1\times 2$ 大小的物块，$b$ 块 $1\times 3$ 的大小的物块，小红想知道能不能填满 $2\times n$ 大小的匣子。 

**$\,\,\,\,\,\,\,\,\,\,$物块可以旋转使用，可以有剩余。**

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1\le T\le 10^5)$ 代表数据组数，每组测试数据描述如下：  
    $\,\,\,\,\,\,\,\,\,\,$在一行上输入三个整数 $a,b$ 和  $n\ (0 \leq a,b \leq 2\times 10^9;$ $1 \leq n \leq 2\times 10^9)$ 表示有 $a$ 块 $1\times 2$ 大小的物块，$b$ 块 $1\times 3$ 的大小的物块，匣子的大小为 $2\times n$。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$对于每一组测试数据，如果存在一种方式使得物块可以填满匣子，在一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$ 。
    
      
    

示例1 

## 输入
    
    
    1
    3 2 6

## 输出
    
    
    YES

## 说明
    
    
    其中一种可行的放置方式如下图所示：
    
    ![](https://uploadfiles.nowcoder.com/images/20240717/0_1721195693031/30A44153D5CBD56FEF3B4961989AD082)  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学, 贪心
# 小红的数字对对碰

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有一个长度为 $n$ 的数组 $a$ ，第 $i$ 位的值为 $a_i$ 。她想通过以下方式，尽可能地减少数组长度。  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 当 $len(a)>1$ 且存在二元组 $(i,j)$ ，满足 $i<j$ 且 $a_i + a_j \leq 0$ ，则可消去 $a_i$ 和 $a_j$ 。  
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$● 当 $len(a)>1$ 且存在二元组 $(i,j)$ ，满足 $i<j$ 且 $a_i \oplus a_j \leq 0$ ，则可消去 $a_i$ 和 $a_j$ 。  


$\,\,\,\,\,\,\,\,\,\,$请你输出最小化后的数组的长度。 

$\,\,\,\,\,\,\,\,\,\,$$\oplus$ 表示按位异或，数字以 $32$ 位补码形式存储。  


## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (\ 1 \leq n \leq 10^5\ )$ 代表初始元素数量。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (-10^9 \leq a_i \leq 10^9)$ 代表初始的数组。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表最小化后的数组的长度。

示例1 

## 输入
    
    
    5
    -3 -1 0 2 4

## 输出
    
    
    1

## 说明
    
    
    $a_1$ 和 $a_4$ 按照方式一消除。  
    $a_2$ 和 $a_5$ 按照方式二消除。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 贪心
# 小红的最大字典序

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有 $n$ 个数字 $a_1,a_2,\dots,a_n$ 和一个空字符串 $s$ ，现在她需要执行 $n$ 次操作：第 $i$ 次操作需要将 $a_i$ 按照数位上的相对顺序、从左到右的取出并依次插入 $s$ （在 $s$ 中不需要连续，但需要保持原有相对顺序）。 

$\,\,\,\,\,\,\,\,\,\,$小红想要构造一个这样的字符串 $s$ ，使得它的字典序是所有合法构造方案中最大的。

$\,\,\,\,\,\,\,\,\,\,$ 

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1\leq n\leq  10^5)$ 代表数字个数。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1\leq a_i\leq 10^9)$ 代表数组中的元素。  
    $\,\,\,\,\,\,\,\,\,\,$除此之外，保证所有的数字数位长度之和 $\sum_{i=1}^n{\rm len}(a_i)$ 不超过 $2\cdot 10^5$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个长度为 $\sum_{i=1}^n{\rm len}(a_i)$ ，且只由数字组成的字符串 $s$ ，代表字典序最大的构造答案。

示例1 

## 输入
    
    
    2
    92 86

## 输出
    
    
    9862

## 说明
    
    
    一共有六种合法构造方案：** _86_** 92、** _8_** 9** _6_** 2、** _**_8_**_****** ____9 2** _6_** __、9** _86_** 2、9** _8_** 2** _6_** 、92** _86_** 。

示例2 

## 输入
    
    
    2
    912 215

## 输出
    
    
    921512


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 字符串