← 返回题目列表

Codeforces · 1202/B

B. 给你一个十进制字符串......

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

假设您有一个特殊的 $$$x$$$-$$$y$$$-计数器。该计数器可以将一些值存储为十进制数;首先,计数器的值为 $$$0$$$。

计数器执行以​​下算法:打印其最低位,然后将 $$$x$$$ 或 $$$y$$$ 添加到其值中。因此该计数器生成的所有序列都是从 $$$0$$$ 开始的。例如,$$$4$$$-$$$2$$$-计数器的作用如下:

1.打印$$$0$$$,并将$$$4$$$添加到其值中,因此当前值为$$$4$$$,输出为$$$0$$$;
2. 打印$$$4$$$,并将$$$4$$$添加到其值中,因此当前值为$$$8$$$,输出为$$$04$$$;
3. 打印$$$8$$$,并在其值上加上$$$4$$$,因此当前值为$$$12$$$,输出为$$$048$$$;
4. 打印$$$2$$$,并将$$$2$$$添加到其值中,因此当前值为$$$14$$$,输出为$$$0482$$$;
5. 它打印 $$$4$$$,并将 $$$4$$$ 添加到其值中,因此当前值为 $$$18$$$,输出为 $$$04824$$$。

这只是可能的输出之一;例如,如果我们选择在每个步骤中添加 $$$2$$$,则同一计数器可以生成 $$$0246802468024$$$ 作为输出。

你从这样的$$$x$$$-$$$y$$$-计数器之一写下了一个打印序列。但序列已损坏,序列中的几个元素可能被删除。

现在您想恢复丢失的数据,但您甚至不知道您使用的计数器的类型。您有一个十进制字符串 $$$s$$$ — 序列的剩余数据。

对于所有 $$$0 \le x, y < 10$$$,计算必须在字符串 $$$s$$$ 中插入的最少位数,以使其成为 $$$x$$$-$$$y$$$ 计数器的可能输出。请注意,您无法更改字符串 $$$s$$$ 中的数字顺序或删除其中任何数字;只允许插入。

输入

第一行包含单个字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^6$$$, $$$s_i \in \{\text{0} - \text{9}\}$$$) — 您拥有的剩余数据。保证 $$$s_1 = 0$$$。

输出

打印一个 $$$10 \times 10$$$ 矩阵,其中第 $$$i$$$ 行上的第 $$$j$$$ 整数($$$0$$$ 索引)($$$0$$$ 索引)等于您必须在字符串 $$$s$$$ 中插入的最小位数,以使其成为该字符串的可能输出$$$i$$$-$$$j$$$-计数器,或者$$$-1$$$(如果没有办法这样做)。

示例

输入 #1

0840

输出 #1

-1 17 7 7 7 -1 2 17 2 7 
17 17 7 5 5 5 2 7 2 7 
7 7 7 4 3 7 1 7 2 5 
7 5 4 7 3 3 2 5 2 3 
7 5 3 3 7 7 1 7 2 7 
-1 5 7 3 7 -1 2 9 2 7 
2 2 1 2 1 2 2 2 0 1 
17 7 7 5 7 9 2 17 2 3 
2 2 2 2 2 2 0 2 2 2 
7 7 5 3 7 7 1 3 2 7

注意

让我们以$$$4$$$-$$$3$$$-计数器为例。计数器可能打印的结果之一是 $$$0(4)8(1)4(7)0$$$(丢失的元素在括号中)。

$$$2$$$-$$$3$$$ 计数器可以打印的可能结果之一是 $$$0(35)8(1)4(7)0$$$。

$$$6$$$-$$$8$$$计数器可以准确打印字符串$$$0840$$$。