yl-9/probench huggingface dataset:
# 小红的图上加边

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有一张 $n$ 个点 $m$ 条边的无向图，每个节点的权值是 $a_i$。  
$\,\,\,\,\,\,\,\,\,\,$现在小红希望加边把这个图连成连通图，每次连接的代价是新形成的联通块的最大元素值，小红想知道最小需要消耗多少代价可以把这个图连成连通的。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入两个整数$n$ 和 $m\ (1 \leq n \leq 10^5;$ $0 \leq m \leq 10^5)$ 表示点数和边数。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1 \leq a_i \leq 10^9)$ 表示每个节点的权值。  
    $\,\,\,\,\,\,\,\,\,\,$接下来 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leq u_i,v_i \leq n)$ 表示无向图上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ ，保证没有重边。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，表示最小需要消耗的代价。
    
      
    

示例1 

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

## 输出
    
    
    9

## 说明
    
    
    先加上 $(1, 4)$ 这条边，代价是 $4$，然后加上 $(1, 5)$ 这条边，代价是 $5$，总代价是 $9$。


## 时空限制

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

Tags: 图论, 连通性, 贪心
# 小红的括号串

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小红有一个只包含 '(' 、')' 和 '?' 的字符串，小红想知道有多少种将 '?' 替换成 '(' 或 ')' 的方式使得存在一种循环移位、让该字符串为合法的括号串。  
$\,\,\,\,\,\,\,\,\,\,$假设一个长度为 $n$ 的字符串 $s[k:n] + s[1:k)$ 是字符串 $s$ 的循环移位，且 $s[k:n] + s[1:k)$ 是一个合法的括号串，那么字符串 $s$ 符合题目要求。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\ (1 \le n \le 10^5)$ 代表字符串长度。
    
    $\,\,\,\,\,\,\,\,\,\,$第二行输入一个长度为 $n$ ，且只由 '(' 、')' 和 '?' 三种字符组成的字符串 $s$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个整数，代表合法替换方式数量。由于答案可能很大，你需要输出答案对 $10^9 + 7$ 取模的结果。

示例1 

## 输入
    
    
    10
    ()(??(?)??

## 输出
    
    
    10

## 说明
    
    
    其中一种替换方式为：()())())((，可以循环移位得到 ((()())())，是合法的括号串。


## 时空限制

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

Tags: 组合数学, 数论
# 小红的同余

## 题目描述

给出一个奇数 $m$，请找出一个整数 $x$（$0 \leq x < m$），使得 $2 x \equiv 1 \pmod m$，也就是 $2 x$ 除以 $m$ 的余数是 $1$。你需要输出这个整数 $x$。  
  
可以证明，这样的整数 $x$ 存在且唯一。

## 输入描述:
    
    
    第一行一个整数 $m$，表示给出的奇数。  
    $3 \leq m \leq 10^9$

## 输出描述:
    
    
    输出一个整数 $x$（$0 \leq x < m$），满足 $2 x \equiv 1 \pmod m$。

示例1 

## 输入
    
    
    3

## 输出
    
    
    2

## 说明
    
    
    $2 \times 2 \equiv 1 \pmod 3$


## 时空限制

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

Tags: 数学
Difficulty: 400
# 小红的三倍数

## 题目描述

现在有$n$个整数，需要寻找一种拼接方式，将所有整数首尾相连，是否存在一种方式让拼接后的整数是3的倍数。

## 输入描述:
    
    
    第一行给出一个$n$，代表有多少个数字。  
    第二行输入$n$个整数$a_i$。  
    $1 \leq n \leq 100$  
    $1 \leq a_i \leq 10^{100}$

## 输出描述:
    
    
    如果有一种拼接方式让这个数是3的倍数，那么就输出“YES”，否则输出 “NO”。  
    
    
      
    

示例1 

## 输入
    
    
    3
    12 3 7

## 输出
    
    
    NO

## 说明
    
    
    不存在一种拼接方式让这个数是3的倍数。  
    
    
      
    

示例2 

## 输入
    
    
    3
    12 3 6

## 输出
    
    
    YES

## 说明
    
    
    1263 是 3 的倍数。


## 时空限制

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

Tags: 数学, 贪心
Difficulty: 400
# 小红充电

## 题目描述

小红手机充满电是100%，现在手机有$x$%的电，不充电玩手机每分钟会损失$y$%的电，充着电玩手机每分钟会充$a$%的电，充着电不玩手机每分钟会充$b$%的电，电量不高于$t$%开始触发超级充电(充到$t$%之后仍然保持超级充电)，超级充电时不能玩手机，每分钟会充$c$%的电。小红现在有急事要出门，问最短多长时间会充满电？

## 输入描述:
    
    
    第一行输入6个整数$x,y,t,a,b,c$。  
    $1 \leq x, y, t \leq 100$  
    $1 \leq a \leq b \leq c \leq 100$

## 输出描述:
    
    
    输出小红充满电的最短时间，如果你的答案与标准答案的绝对误差不超过$10^{-6}$，则视为正确。

示例1 

## 输入
    
    
    10 2 20 3 4 5

## 输出
    
    
    18.000000000

## 说明
    
    
    已经触发了超级充电，所以不玩手机，每分钟充5%的电，所以18分钟充满电。


## 时空限制

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

Tags: 数学
Difficulty: 700
# 小红的 gcd

## 题目描述

给两个正整数$a,b$，输出他们的最大公约数 $\gcd(a, b)$。

## 输入描述:
    
    
    第一行一个正整数 $a$。  
    第二行一个正整数 $b$。  
    $len$表示$a$的十进制位数，$1\leq len \leq 10^6$。  
    $1\leq b \leq 10^9$。

## 输出描述:
    
    
    输出一个整数，表示$\gcd(a, b)$。

示例1 

## 输入
    
    
    12345678
    12

## 输出
    
    
    6


## 时空限制

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

Tags: 数论
Difficulty: 1000
# 小红走矩阵

## 题目描述

给定$n \times n$的矩阵，矩阵中的每个元素都是正整数，小红能当前位于左上角$(1,1)$，每次可以从 $(x, y)$ 走到 $(x+1, y)$、$(x, y+1)$、$(x-1, y)$、$(x, y-1)$，但不能走出矩阵。小红希望找到一条到右下角$(n,n)$的路径，定义路径权值为路径上经过的每个点的最大值，求所有路径中的最小路径权值。

## 输入描述:
    
    
    第一行一个整数$n$，表示矩阵的大小。  
    接下来$n$行，每行$n$个整数，表示矩阵中的元素$a_{ij}$。  
    $1 \leq n \leq 500$  
    $1 \leq a_{ij} \leq 10^9$。

## 输出描述:
    
    
    输出一个整数，表示所有路径中的最小路径权值。

示例1 

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

## 输出
    
    
    7

## 说明
    
    
    先一直往右走，再一直往下走，路径上的最大值为7。


## 时空限制

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

Tags: 图论, 最短路, 数据结构, 并查集, 二分, 分治, 搜索
Difficulty: 1200
# 小红的数组

## 题目描述

小红有一个数组，这个数组中有 $n$ 个数 $a_i$。  
小红有 $q$ 次询问，每次询问给定一个区间 $[l,r]$，询问区间连续子段和的绝对值最大是多少，即区间存在 $x,y$使得 $l \leq x \leq y \leq r$，求最大的 $\mathrm{abs}(a[x]+a[x+1]+.....+a[y])$是多少。

## 输入描述:
    
    
    第一行输入一个整数 $n$ 表示数组的长度。  
    第二行输入 $n$ 个整数 $a_i$ 表示数组的元素。  
    第三行输入一个整数 $q$ 表示询问的次数。  
    接下来 $q$ 行，每行输入两个整数 $l,r$ 表示询问的区间。  
    $1 \leq n, q \leq 5 \times 10^5$  
    $-10^9 \leq a_i \leq 10^9$  
    $1 \leq l \leq r \leq n$

## 输出描述:
    
    
    输出 $q$ 行，每行输出一个整数表示对应询问的答案。

示例1 

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

## 输出
    
    
    3
    7
    7


## 时空限制

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

Tags: 数据结构, ST表, 枚举, 前缀和, RMQ
Difficulty: 1600
# 小红的最小最大

## 题目描述

给定三个正整数 $a,b,x$，小红想知道 $\min(a,b)+x$ 是否大于 $\max(a,b)$。请你帮助她解决这个问题。

## 输入描述:
    
    
    第一行三个正整数 $a,b,x$。  
    $1 \leq a,b,x \leq 1000$

## 输出描述:
    
    
    如果 $\min(a,b)+x$ 大于 $\max(a,b)$，输出 "YES"，否则输出 "NO"。

示例1 

## 输入
    
    
    1 3 2

## 输出
    
    
    NO

示例2 

## 输入
    
    
    1 3 3

## 输出
    
    
    YES


## 时空限制

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

Tags: 模拟
Difficulty: 400
# 小红的四则运算（easy）

## 题目描述

easy 版本和 hard 版本唯一的区别是 hard 版本不可以调整三个数的顺序，而 easy 版本可以调整三个数的顺序。  
  
小红有三个正整数 $a,b,c$，小红想知道经过任意四则运算后可得的最大值，允许加括号，但每个数只能被使用一次，且必须被使用一次。

## 输入描述:
    
    
    第一行输入三个正整数 $a,b,c$，表示小红的三个正整数。  
    $1 \leq a,b,c \leq 1000$。

## 输出描述:
    
    
    输出一个整数，表示经过任意四则运算后可得的最大值。

示例1 

## 输入
    
    
    1 3 2

## 输出
    
    
    9

## 说明
    
    
    $(1 + 2) \times 3 = 9$。


## 时空限制

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

Tags: 贪心
Difficulty: 400
# 小红的四则运算（hard）

## 题目描述

easy 版本和 hard 版本唯一的区别是 hard 版本不可以调整三个数的顺序，而 easy 版本可以调整三个数的顺序。  
  
小红有三个正整数 $a,b,c$，小红想知道保持 $a,b,c$ 顺序下，插入任意四则运算后可得的最大值，允许加括号，但每个数只能被使用一次，且必须被使用一次。

## 输入描述:
    
    
    第一行输入三个正整数 $a,b,c$，表示小红的三个正整数。  
    $1 \leq a,b,c \leq 1000$。

## 输出描述:
    
    
    输出一个整数，表示经过任意四则运算后可得的最大值。

示例1 

## 输入
    
    
    1 3 2

## 输出
    
    
    8

## 说明
    
    
    $(1 + 3) \times 2 = 8$。


## 时空限制

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

Tags: 枚举
Difficulty: 400
# 小红的因式分解

## 题目描述

小红有三个整数 $a,b,c$，要将 $ax^2+bx+c$ 分解为 $(a_1x+b_1)(a_2x+b_2)$ 的形式，其中 $a_1,b_1,a_2,b_2$ 均为整数。  
如果可以分解，请按 $a_1,b_1,a_2,b_2$ 的顺序输出，若有多解输出任意一种，若无解，输出 "NO"。

## 输入描述:
    
    
    第一行输入一个整数 $T$，表示有 $T$ 组测试数据。  
    接下来 $T$ 行，每行输入三个整数 $a,b,c$。  
    $1 \leq T \leq 100$  
    
    
    $-10^6 \leq a,b,c \leq 10^6$
    
    $a \neq 0$  
    

## 输出描述:
    
    
    输出 $T$ 行，每行输出四个整数 $a_1,b_1,a_2,b_2$，表示 $(a_1x+b_1)(a_2x+b_2)$ 的形式，若无解，输出 "NO"。

示例1 

## 输入
    
    
    2
    1 2 1
    1 3 1

## 输出
    
    
    1 1 1 1
    NO

## 说明
    
    
    对于第一组数据，$x^2+2x+1=(x+1)(x+1)$。  
    


## 时空限制

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

Tags: 质因数分解, gcd与exgcd, 数论
Difficulty: 1200
# 小红的树上移动

## 题目描述

小红有一棵 $n$ 个点的树，根节点为 $1$，有一个物块在根节点上，每次它会等概率随机移动到当前节点的其中一个子节点，而后等概率随机传送到一个同深度节点，若此时它位于叶子节点，则停止移动。  
求其移动到子节点的次数的期望值，答案对 $998244353$ 取模。

## 输入描述:
    
    
    第一行输入一个整数 $n$，表示树的节点数。  
    接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示 $u$ 和 $v$ 之间有一条边。  
    $1 \leq n \leq 10^6$  
    $1 \leq u,v \leq n$

## 输出描述:
    
    
    输出一个整数，表示其移动到子节点的次数的期望值。

示例1 

## 输入
    
    
    3
    1 2
    2 3

## 输出
    
    
    2

## 说明
    
    
    物块在根节点上，移动到子节点的次数的期望值为 2。

示例2 

## 输入
    
    
    4
    1 2
    1 3
    2 4

## 输出
    
    
    499122178

## 说明
    
    
    有一半的概率停止在 3 号节点，移动次数为 1，有一半的概率停止到 4 号节点，移动次数为 2，故答案为 3/2。  
    
    
      
    


## 时空限制

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

Tags: 数学, 概率期望, 广度优先搜索(BFS), 搜索
Difficulty: 1700
# 小红的网格

## 题目描述

有一个无限大的仅由整数点构成的图，给定 $R$，两个点 $(x_1,y_1),(x_2,y_2)$ 间有连边当且仅当 $(x_1-x_2)^2+(y_1-y_2)^2=R$，求连通块个数，如果无穷多则输出 $\inf$。

## 输入描述:
    
    
    第一行输入一个整数 $T$，表示数据组数。  
    接下来 $T$ 行，每行输入一个整数 $R$。  
    $1 \leq T \leq 10$  
    $1 \leq R \leq 10^{10}$

## 输出描述:
    
    
    输出 $T$ 行，每行输出一个整数，表示连通块个数，如果无穷多则输出 $\inf$。

示例1 

## 输入
    
    
    3
    25
    9
    3

## 输出
    
    
    1
    9
    inf


## 时空限制

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

Tags: 质因数分解, gcd与exgcd, 构造, 数论, 暴力
Difficulty: 2200