← 返回题目列表

Codeforces · 1729/C

C. 在瓷砖上跳跃

中文机器翻译题面 查看原题

Polycarp 得到了一排瓷砖。每个图块包含一个拉丁字母的小写字母。整个图块序列形成字符串 $$$s$$$。

换句话说,给你一个由小写拉丁字母组成的字符串$$$s$$$。

最初,Polycarp 位于该行的第一块图块上,并希望通过跳跃到最后一块图块。从第 $$$i$$$ 个图块跳转到第 $$$j$$$ 个图块的成本等于 $$$|index(s_i) - index(s_j)|$$$,其中 $$$index(c)$$$ 是字母表中字母 $$$c$$$ 的索引(例如,$$$index($$$'a'$$$)=1$$$, $$$index($$$'b'$$$)=2$$$, ..., $$$index($$$'z'$$$)=26$$$) 。

Polycarp 希望以最小的总成本到达第 $$$n$$$ 块,但同时进行最大的跳跃次数。

换句话说,在以最小的总成本到达最后一块砖的所有可能方法中,他会选择跳跃次数最多的方法。

Polycarp 最多可以访问每个方块一次。

Polycarp 请求你帮忙 — 打印他应该跳转的字符串 $$$s$$$ 的索引序列。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。

每个测试用例由字符串 $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$) 给出,其中 $$$|s|$$$ — 是字符串 $$$s$$$ 的长度。字符串 $$$s$$$ 由小写拉丁字母组成。

保证所有测试用例的字符串长度 $$$s$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

每个测试用例的答案由两行组成。

在第一行中打印两个整数 $$$cost$$$,$$$m$$$,其中 $$$cost$$$ 是路径的最小总成本,$$$m$$$ 是 Polycarp 可以在最小总成本 $$$cost$$$ 下到达 $$$n$$$ 块的最大访问图块数(即跳转次数为$$$m-1$$$)。

在下一行中打印 $$$m$$$ 不同的数字 $$$j_1, j_2, \dots, j_m$$$ ($$$1 \le j_i \le |s|$$$) - Polycarp 将跳转的图块索引序列。序列中的第一个数字必须是 $$$1$$$(即 $$$j_1=1$$$),最后一个数字必须是 $$$|s|$$$ 的值(即 $$$j_m=|s|$$$)。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

6
logic
codeforces
bca
aaaaaaaaaaa
adbaadabad
to

输出 #1

9 4
1 4 3 5
16 10
1 8 3 4 9 5 2 6 7 10
1 2
1 3
0 11
1 8 10 4 3 5 7 2 9 6 11
3 10
1 9 5 4 7 3 8 6 2 10
5 2
1 2

注意

第一个测试用例中,所需路径对应图片:

在这种情况下,实现了路径的最小可能总成本。由于$$$index($$$'l'$$$)=12$$$,$$$index($$$'o'$$$)=15$$$,$$$index($$$'g'$$$)=7$$$,$$$index($$$'i'$$$)=9$$$,$$$index($$$'c'$$$)=3$$$,则路径的总成本为$$$|12-9|+|9-7|+|7-3|=3+2+4=9$$$。