← 返回题目列表

Codeforces · 1809/D

D. 二进制字符串排序

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

给你一个二进制字符串 $$$s$$$,仅包含字符 0 和/或 1。

您可以对此字符串执行多项操作(可能为零)。有两种类型的操作:

- 选择两个连续的元素并交换它们。为了执行此操作,您需要支付 $$$10^{12}$$$ 硬币;
- 从字符串中选择任何元素并将其删除。为了执行此操作,您需要支付 $$$10^{12}+1$$$ 硬币。

你的任务是计算以非递减顺序对字符串 $$$s$$$ 进行排序所需的最小硬币数(即变换 $$$s$$$ 以便 $$$s_1 \le s_2 \le \dots \le s_m$$$,其中 $$$m$$$ 是应用所有操作后字符串的长度)。空字符串也被视为按非降序排序。

输入

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

每个测试用例的唯一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$),仅包含字符 0 和/或 1。

所有给定字符串的长度总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 以非递减顺序对字符串 $$$s$$$ 进行排序所需的最小硬币数。

示例

输入 #1

6
100
0
0101
00101101
1001101
11111

输出 #1

1000000000001
0
1000000000000
2000000000001
2000000000002
0

注意

在第一个示例中,您必须删除 $$$1$$$-st 元素,因此字符串变为等于 00。

在第二个示例中,字符串已经排序。

在第三个示例中,您必须交换 $$$2$$$-nd 和 $$$3$$$-rd 元素,因此字符串等于 0011。

在第四个示例中,您必须交换第 $$$3$$$-rd 和第 $$$4$$$-th 元素,因此字符串变为等于 00011101,然后删除第 $$$7$$$-th 元素,因此字符串变为等于 0001111。

在第五个示例中,您必须删除 $$$1$$$-st 元素,因此字符串变为等于 001101,然后删除 $$$5$$$-th 元素,因此字符串变为等于 00111。

在第六个示例中,字符串已经排序。