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:

it prints 0, and adds 4 to its value, so the current value is 4, and the output is 0;

it prints 4, and adds 4 to its value, so the current value is 8, and the output is 04;

it prints 8, and adds 4 to its value, so the current value is 12, and the output is 048;

it prints 2, and adds 2 to its value, so the current value is 14, and the output is 0482;

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 <= 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.

Input
The first line contains a single string s (1 ≤ |s| ≤ 2*10^6, s_i ∈ {0- 9}) — the remaining data you have. It’s guaranteed that s_1 = 0.

Output
Print a 10 * 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.

SampleInput
0840
SampleOutput
-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

Note

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.

题意：给你一个序列 然后让你输出一个10*10的矩阵 i j代表 i-j计数器
每次可以选择+i或者+j 如果加上之后＞10的话就模10 问你每个i-j计数器让包含这个序列需要添加的最少的数字个数是多少 如果不存在 则输出-1 可以在这个序列中插入 但是不能改变这个序列的原本数字顺序或者删除序列的数字

这个是学长拉的手速赛的题 当时是真的懵逼 看懂了题意却真的不知道要怎么去做
看了神犇的代码真的是被惊呆了 谁敢信这个最短路的题 floyd
下面具体说一下怎么floyd
我们从0到9开始 每一次可以+x也可以+y 这样就有路可走 也就是d[i][(i+x)%10]=1,d[i][(i+y)%10]=1
不懂的话认真思考一下 其实很好理解
然后要怎么做呢？
我们从0到9去跑个floyd 维护两个点之间的最短路
然后去用给的序列循环 加上每相邻两个数的d[i][i+1]-1 为什么要减去1呢？
举个例子
比如序列08 假设d[0][8]=3 说明0到8最少需要进行三步 也就是0->x->y->8 但是8是给了的 所以加上的数字是两个
当然了 如果相邻两点之间无路可走 那么直接返回-1呢就可以了
复杂度 100*(10+1000+（strlen(n)-1）)
极限数据大约2e8 2s随便跑
当然也可以更加的省去一半的时间 我们可以知道i-j计数器与j-i计数器的答案一定是一样的

#include <bits/stdc++.h>
using namespace std;
int n,dis[15][15];
char s[2000005];
int fun(int x,int y){

    memset(dis,0x3f,sizeof(dis));
    
    for(int i=0;i<10;i++)
        dis[i][(i+x)%10]=1,dis[i][(i+y)%10]=1;

    for(int k=0;k<10;k++)
        for(int i=0;i<10;i++)
            for(int j=0;j<10;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

    int ans=0;
    for(int i=0;i<n-1;i++){
        if(dis[s[i]-'0'][s[i+1]-'0']==0x3f3f3f3f)
            return -1;
        ans+=dis[s[i]-'0'][s[i+1]-'0']-1;
    }
    return ans;

}
int main(){
    cin>>s;
    n=strlen(s);
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            cout<<fun(i,j)<<' ';
        }
       puts("");
    }

    return 0;
}