You Are Given a Decimal String...

题意翻译

题目描述 你现在有一个神奇的计算器，~~这是闪现牌计算器（洛谷独家赞助，codeforces特别生产），~~ 这种计算器被称为$x-y$计算器。 因为是~~闪现牌~~神奇计算器，所以它的操作也非常神奇。这个计算器的初始数值为$0$，然后你可以加一个数值$x$或$y$。当然，在这一步之前，你需要先输出当前数值的最后一位。 这是$4-2$的一种情况： 1. 输出$0$，然后加上$4$，当前数值为$4$，当前输出$0$。 1. 输出$4$，然后加上$4$，当前数值为$8$，当前输出$04$。 1. 输出$8$，然后加上$4$，当前数值为$12$，当前输出$048$。 1. 输出$2$，然后加上$2$，当前数值为$14$，当前输出$0482$。 1. 输出$4$，然后加上$4$，当前数值为$18$，当前输出$04824$。 当然，这只是一种情况。如果我们每次都加$2$，还可以得到$0246802468024$这个序列。 现在你有一个由$x-y$计算器得到的序列$s$，但是由于这个计算器为初代产品，某些数字丢失了。 然而你想恢复这个序列，不过问题是你并不知道这是哪一款$x-y$计算器（即不知道$x$与$y$的大小），所以对于每一款$x-y(0≤x,y<10)$计算器，输出使序列$s$变为能由该款计算器能得到的序列最小所需插入的数字数。 输入格式 仅一行，一个字符串$s$，$s$的长度小于$2⋅10^6$且均有数字$0$~$9$组成。 输出格式 一个$10×10$的矩阵，第$i$行第$j$个为使序列$s$变为能由$i-j$计算器能得到的序列最小所需插入的数字数。如果不能，则输出$-1$（$i,j$皆从$0$开始编号）。

题目描述

Suppose you have a special $ x $ - $ y $ -counter. This counter can store some value as a decimal number; at first, the counter has value $ 0 $ . The counter performs the following algorithm: it prints its lowest digit and, after that, adds either $ x $ or $ y $ to its value. So all sequences this counter generates are starting from $ 0 $ . For example, a $ 4 $ - $ 2 $ -counter can act as follows: 1. it prints $ 0 $ , and adds $ 4 $ to its value, so the current value is $ 4 $ , and the output is $ 0 $ ; 2. it prints $ 4 $ , and adds $ 4 $ to its value, so the current value is $ 8 $ , and the output is $ 04 $ ; 3. it prints $ 8 $ , and adds $ 4 $ to its value, so the current value is $ 12 $ , and the output is $ 048 $ ; 4. it prints $ 2 $ , and adds $ 2 $ to its value, so the current value is $ 14 $ , and the output is $ 0482 $ ; 5. it prints $ 4 $ , and adds $ 4 $ to its value, so the current value is $ 18 $ , and the output is $ 04824 $ . This is only one of the possible outputs; for example, the same counter could generate $ 0246802468024 $ as the output, if we chose to add $ 2 $ during each step. You wrote down a printed sequence from one of such $ x $ - $ y $ -counters. But the sequence was corrupted and several elements from the sequence could be erased. Now you'd like to recover data you've lost, but you don't even know the type of the counter you used. You have a decimal string $ s $ — the remaining data of the sequence. For all $ 0 \le x, y < 10 $ , calculate the minimum number of digits you have to insert in the string $ s $ to make it a possible output of the $ x $ - $ y $ -counter. Note that you can't change the order of digits in string $ s $ or erase any of them; only insertions are allowed.

输入输出格式

输入格式

The first line contains a single string $ s $ ( $ 1 \le |s| \le 2 \cdot 10^6 $ , $ s_i \in \{\text{0} - \text{9}\} $ ) — the remaining data you have. It's guaranteed that $ s_1 = 0 $ .

输出格式

Print a $ 10 \times 10 $ matrix, where the $ j $ -th integer ( $ 0 $ -indexed) on the $ i $ -th line ( $ 0 $ -indexed too) is equal to the minimum number of digits you have to insert in the string $ s $ to make it a possible output of the $ i $ - $ j $ -counter, or $ -1 $ if there is no way to do so.

输入输出样例

输入样例 #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 

说明

Let's take, for example, $ 4 $ - $ 3 $ -counter. One of the possible outcomes the counter could print is $ 0(4)8(1)4(7)0 $ (lost elements are in the brackets). One of the possible outcomes a $ 2 $ - $ 3 $ -counter could print is $ 0(35)8(1)4(7)0 $ . The $ 6 $ - $ 8 $ -counter could print exactly the string $ 0840 $ .