seuOJ572 - XCPC 重开

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：Div.1, 2025 帆软杯, Special Judge

题目描述

一场 XCPC 的时长是 $300$ 分钟。

有 $n$ 道题，数字编号依次是 $1,2,\cdots,n$，字母编号依次是 $\texttt{A},\texttt{B},\cdots$。

已知数字编号为 $i$ 的题做 $t_i$ 分钟（不必连续）才能通过，且通过前会有 $d_i$ 次错误的提交。

若数字编号为 $i$ 的题拼尽全力也无法战胜，则 $t_i=301$。

需要注意的是，在同一分钟内你们只能做同一道题。

最后，通过的题目数量多的队伍排名靠前。若通过的题目数量相等，则罚时少的队伍排名靠前。

设某支队伍分别在 $s_1,s_2,\cdots,s_m$ 分钟时通过了数字编号为 $p_1,p_2,\cdots,p_m$ 的题，则该队伍的罚时是

求最优策略——在使通过的题目数量最多的前提下，使罚时最少。

输入格式

第一行一个整数 $T$（$1\le T\le15000$），表示该测试点有 $\boldsymbol{T}$ 组数据。

接下来，对于每组数据：

• 第一行一个整数 $n$（$1\le n\le26$）。
• 接下来 $n$ 行中的第 $i$ 行，有两个整数 $t_i,d_i$（$1\le t_i\le301$，$0\le d_i\le t_i$）。

保证 $T$ 组数据中的 $n$ 之和 $\sum n\le202500$。

输出格式

对于每组数据，输出 $2$ 或 $11$ 行：

第一行两个整数，分别表示采取最优策略时通过的题目数量以及罚时。

第二行一个长度为 $300$ 的字符串，表示最优策略：

• 第 $i$ 个字符是第 $i$ 分钟在做的题的字母编号。特别地，若第 $i$ 分钟不在做题，则第 $i$ 个字符是 $\texttt{-}$。
• 若数字编号为 $j$ 的题从前到后的第 $t_j$ 次出现是在第 $x$ 个字符，则认为在 $x$ 分钟时通过该题。

因为字符串较长，你也可以把它分成 $10$ 行，每行 $30$ 个字符，以便于展示。如果这样，那么该组数据输出 $11$ 行。

若有多个最优策略，只需输出任意一个。

样例

输入

2
2
9 9
295 0
3
246 3
37 7
169 4

一个满足要求的输出

1 189
AAAAAAAAABBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB-------
------------------------------
------------------------------
BB-----B----------------------
------------------------------
------------------------------
------------------------------
-----------B------------------
2 463
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA