题目内容

大语言模型逐词元生成文本时，候选序列的数量会随长度指数增长，逐一枚举并不现实。束搜索（Beam Search）的做法是：每一轮只保留少量得分最高的候选，用有限的束宽，在可以接受的计算量内近似挑出概率较高的若干条完整序列。

请你按下面的规则模拟一次束搜索：从起始词元出发，沿给定的转移表不断往后接词元，最后汇总出得分最高的若干条完整序列。

一条序列 $Y=(y_1,y_2,\dots,y_T)$ 的得分为它经过的所有转移的对数概率之和：

输入直接给出每个转移的 $\log P$ 数值，累加即可。对数概率都是负数，因此得分越接近 $0$，这条序列出现的概率越大。

搜索流程

初始状态：活跃束（Active Beams）中只有一条序列 $[\,start\,]$，得分为 $0.00$。

扩展：对活跃束中的每条序列，取它末尾的词元 $u$。

• 如果 $u$ 在转移表中没有任何出边，这条序列直接进入已完成列表，视为走进死胡同；
• 否则对 $u$ 的每一条出边 $(v,\ell)$ 生成后继序列，新得分为原得分加上 $\ell$：
  • 若 $v$ 就是 $end$，后继序列进入已完成列表；
  • 否则后继序列作为活跃候选，等待剪枝。

剪枝：只对活跃候选排序——得分高的在前，得分相同时词元序列字典序小的在前——保留前 $beam\_width$ 条，作为下一轮的活跃束。已完成序列不参加剪枝，也不占用活跃束的名额。

终止：出现下列任一情况时结束搜索。

1. 活跃束为空；
2. 活跃束中序列的长度已经达到 $max\_length$，此时活跃束中的序列全部转入已完成列表。

输出排序：把已完成列表中的全部序列按下面的规则排序，输出最前面的至多 $beam\_width$ 条。

1. 得分降序；
2. 得分相同则序列长度升序；
3. 得分与长度都相同则词元序列字典序升序。

初始序列 $[\,start\,]$ 不会因为 $start=end$ 而自动完成：一条序列只有在走到 $end$、撞上死胡同、或长度达到 $max\_length$ 时才算完成。$N$ 个词元的转移行都要给出，$end$ 对应的那一行也不例外。

约束条件

• $1\le N\le 1000$，$0\le start,end<N$，$1\le beam\_width\le 100$，$1\le max\_length\le 100$；
• 转移表中的对数概率 $\ell$ 为负数，小数位不超过两位；
• 若最终没有任何序列完成，输出 None。

输入描述

第一行五个整数 $N$、$start$、$end$、$beam\_width$、$max\_length$：

• $N$：词元总数，词元编号为 $0$ 到 $N-1$；
• $start$：起始词元编号；
• $end$：结束词元编号；
• $beam\_width$：束宽；
• $max\_length$：序列长度上限（包含起始词元）。

接下来 $N$ 行，第 $i$ 行（$i=0,1,\dots,N-1$）描述词元 $i$ 的转移表，格式为

M next_1 prob_1 next_2 prob_2 ... next_M prob_M

其中 $M$ 为出边条数，紧随其后的 $2M$ 个数按顺序成对给出每条出边的目标词元编号与对数概率。$M=0$ 时该行只有一个 0。

输出描述

输出至多 $beam\_width$ 行，每行一条序列，格式为

score seq_len token_1 token_2 ... token_seq_len

score 为序列得分，四舍五入保留两位小数；seq_len 为序列长度；其后是这条序列的全部词元编号（含起始词元）。若没有任何序列完成，只输出一行 None。

样例1

输入

6 2 5 2 5
0
1 2 -0.40
3 3 -0.20 5 -0.70 1 -0.55
2 4 -0.30 1 -0.25
2 5 -0.15 3 -0.60
0

输出

-0.65 4 2 3 4 5
-0.70 2 2 5

说明

转移表为：词元 $0$、$5$ 没有出边；$1\to2$（$-0.40$）；$2\to3$（$-0.20$）、$2\to5$（$-0.70$）、$2\to1$（$-0.55$）；$3\to4$（$-0.30$）、$3\to1$（$-0.25$）；$4\to5$（$-0.15$）、$4\to3$（$-0.60$）。

• 第 1 轮：$[2]$ 展开得到活跃候选 $[2,3]$（$-0.20$）、$[2,1]$（$-0.55$），并完成 $[2,5]$（$-0.70$）。两条候选都保留。
• 第 2 轮：$[2,3]$ 展开出 $[2,3,1]$（$-0.45$）、$[2,3,4]$（$-0.50$）；$[2,1]$ 展开出 $[2,1,2]$（$-0.95$）。取前 $2$ 条，$[2,1,2]$ 被剪掉。
• 第 3 轮：$[2,3,1]$ 展开出 $[2,3,1,2]$（$-0.85$）；$[2,3,4]$ 展开出 $[2,3,4,3]$（$-1.10$），并完成 $[2,3,4,5]$（$-0.65$）。两条候选都保留。
• 第 4 轮：得到活跃候选 $[2,3,1,2,3]$（$-1.05$）、$[2,3,4,3,1]$（$-1.35$）、$[2,3,1,2,1]$（$-1.40$）、$[2,3,4,3,4]$（$-1.40$），后两条得分相同，按字典序排后面，被剪掉；同时完成 $[2,3,1,2,5]$（$-1.55$）。

此时活跃束长度达到 $max\_length=5$，$[2,3,1,2,3]$ 与 $[2,3,4,3,1]$ 也转入已完成列表。全部已完成序列按得分排序为 $[2,3,4,5]$（$-0.65$）、$[2,5]$（$-0.70$）、$[2,3,1,2,3]$（$-1.05$）、$[2,3,4,3,1]$（$-1.35$）、$[2,3,1,2,5]$（$-1.55$），取前 $2$ 条输出。

样例2

输入

5 3 3 2 3
0
1 3 -0.10
1 3 -0.10
2 1 -0.20 2 -0.20
0

输出

-0.30 3 3 1 3
-0.30 3 3 2 3

说明

$start=end=3$，但初始序列 $[3]$ 不会自动完成。第 1 轮由 $[3]$ 展开出 $[3,1]$ 与 $[3,2]$，得分都是 $-0.20$，按字典序升序全部保留；第 2 轮两条序列各自走到 $3$，得到 $[3,1,3]$（$-0.30$）与 $[3,2,3]$（$-0.30$），得分相同，最终按字典序输出，并且输出里不含 $[3]$ 本身。

样例3

输入

5 0 4 2 4
2 1 -0.10 2 -0.10
0
1 4 -0.05
0
0

输出

-0.10 2 0 1
-0.15 3 0 2 4

说明

第 1 轮由 $[0]$ 展开出 $[0,1]$ 与 $[0,2]$，得分同为 $-0.10$，按字典序都保留。第 2 轮中词元 $1$ 没有出边，$[0,1]$ 作为死胡同直接完成；$[0,2]$ 沿 $2\to4$ 到达 $end$，完成 $[0,2,4]$（$-0.15$）。活跃束清空后搜索结束，死胡同序列 $[0,1]$ 得分更高，排在前面。