题目描述

$Bob$ 所在的村庄停电了，村长需要将一个重要信息通知给 $n$ 个村民，但由于长时间停电，电话手机都用不了，只能口口相传。

村长可以给一个或多个村民通知，通知一个村民要花费 $p$ 的代价。

接收到消息的村民，可以给其他村民通知，第 $i$ 个村民可以给不超过 $a_i$ 个村民，通知一个村民花费 $b_i$ 的代价。

$Bob$ 想知道通知全村 $n$ 个人需要花费的总代价的最小值。

输入格式

第一行 ，两个整数 $n$ 和 $p$

第二行，$n$ 个正整数，$a_1,a_2,...,a_n$，表示每个村民最多通知的人数

第三行，$n$ 个正整数，$b_1,b_2,...,b_n$，表示每位村民向另外一个村民通知的代价

输出格式

一个整数，表示通知到全村 $n$ 个人最低代价。

6 3
2 3 2 1 1 3
4 3 2 6 3 6

16

样例1 解释

1. 村长通知第三，五，六名村民，花费 $p+p+p=9$ 的代价。
2. 第三村民向第一、二个村民传递信息，花费 $b_3+b_3=2+2=4$ 的代价。
3. 第二个村民再向第四个村民传递信息，花费 $b_2=3$ 的代价。

总代价就是 $9+4+3=16$，可以证明没有比这低的其他方案了。

数据规模与约定

subtask1 : $1 \leq n ,p \leq 1000,1 \leq a_i,b_i \leq 1000$ , $50分$

subtask2: $1 \leq n,p \leq 10^5, 1 \leq a_i,b_i \leq 10^5$ , $50分$

题目描述

aqx 又要组织学生参加"大学生程序设计竞赛"，为了公平，要组织一场校内选拔赛，为了能组一套好题，他费了很大心思。

现在有 $n$ 道题目可供选择，第 $i$ 道题目难度为 $c_i$，组出一套满意的题目，他提出以下要求：

1. 一套模拟题，题目数量要大于等于 $4$. （题目道数要够 $4$ 道）
2. 最简单的题目难度不高于 $l$，最难的题目难度要不低于 $r$. (有简单题也要有难题)
3. 整套题目总难度要不低于 $x$. （总难度要够）

题目难度的顺序也会影响参赛者发挥，因此同样的题，如果安排顺序不同，也看作不同的套题。

aqx 想知道他有多少种不同的组题方案，方案数可能很多，答案取 998244353 的余数。

输入格式

第一行，$4$ 个整数: $n,l,r,x$

第二行，$n$ 个整数表示 $c_i$

输出格式

一个整数，表示两个数的积

4 1 2 4
1 2 3 4

24

样例1解释

4 道题全选，都符合题目要求，最低分小于等于 1, 最高分大于等 2，总分大于等于 4，4道题目，共有 24 种排列方式，答案是 24

10 5 5 30
10 9 8 7 6 5 4 3 2 1

9792408

20 10 5 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

967634610

数据规模与约定

所有数据满足： $4 \leq n \leq 20, 1 \leq l,r,x \leq 10^9 , 1 \leq c_i \leq 10^6$

$subtask1$: $4 \leq n \leq 10$ , $50$分。

$subtask2$: $4 \leq n \leq 20$ , $50$分。

题目描述

有一个长度为$n$的传送带，第$i$个位置要么是>，要么是<。

有一个人，一开始会从传送带的某个位置进入传送带。

如果这个位置是<，则他会向左走一格，然后把刚才那个位置改成>。

如果这个位置是>，则他会向右走一格，然后把刚才那个位置改成<。

当他走出界外，则结束本次旅程。

问：他从每一个位置进入传送带，经过几次会出去。

输入格式

第一行输入$n$。

接下来一行输入一个长度为$n$的字符串，每个位置不是<就是>。

输出格式

输出$n$个数字表示答案。

样例输入 #1

3
><<

样例输出 #1

3 6 5

样例输入 #2

6
<><<<>

样例输出 #2

1 4 7 10 8 1

数据范围

对于30%的数据：保证$1\leq n\leq 500$。

对于60%的数据：保证$1\leq n\leq 5000$。

对于另20%的数据：保证最多有$20$个<。

对于100%的数据：保证$1\leq n \leq 5\times 10^5$。

题目描述

有$n$个人，从$1$开始报数，报到$k$，再变成$1$，也就是报数序列是$1,2,3,...,k,k-1,...,2,1,2,3,...$

现在已知你是第$n$个人，报的是$x$，问：$k$有多少种不同的可能。

注意：$k$在本题中一定是$\geq 2$的。

输入格式

第一行输入$T$，一共$T$组数据。

接下来$T$行，每行输入$n,x$。

输出格式

对于每组数据，输出一个数字表示答案。

样例输入 #1

5
10 2
3 1
76 4
100 99
1000000000 500000000

样例输出 #1

4
1
9
0
1

数据范围

对于20%的数据：保证$n\leq 1000$。

对于40%的数据：保证$n\leq 10^4$。

对于50%的数据：保证$n\leq 10^5$。

对于70%的数据：保证$n\leq 5\times 10^5$。

对于100%的数据：保证$1\leq T\leq 100$，$1\leq x<n\leq 10^9$。

题目描述

$Bob$ 梦想成真，当了一名消防员。今天接到一项“营救”任务，在一个 $h \times w$ 网格的区域营救 $num(num=1,2)$ 个人。

网格区域是由 '.' , '#' , '*' 构成的，共 $h$ 行 $w$ 列，需要营救的人的位置是 '$'。

其中： '.' 表示空格，可以自由走动。'#' 是门，但需要暴力破门。'*' 是墙，无法通过。'$' 表示要营救的人，当然营救的位置没有门，也没有墙。

网格区域四周都可以自由进入，'.' 是空格，可以自由出入的，'#' 的位置需要暴力破门，$Bob$ 的想知道至少需要暴力打开几扇门才能将 其中 $num$ 个人全部救出，当然此次营救任务比较简单，$num =1$ 或 $2$. （门暴力打来一次后，门就永久打开了）

当然如果无法完成营救任务，也就是无法将 $num$ 个人全部救出，输出 "impossible"

输入格式

第一行，两个整数 $h$ 和 $w$

接下来 $h$ 行，每行 $w$ 个字符（由‘.’，‘#’，‘*’，‘$’）构成。

输出格式

一个整数，表示将全部人营救出来，需要最少暴力破门的次数。

5 5
##*##
#####
##$#*
#####
##.##

1

5 5
##*##
##*##
#*$**
##*##
##.##

impossible

5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********

4

5 9
****#****
*..#.#..*
****.****
*$#.#.*$*
*********

impossible

5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*

0

9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

9

样例6解释

营救路线如下图：

数据规模与约定

$subtask1 : 1\leq h,w \leq 100,num=1$ , $50$分；

$subtask2: 1\leq h,w \leq 100, num \in \{1,2 \}$ , $50$分；