Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma warning (disable : 4996)
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <map>
- #include <string>
- #include <iomanip>
- using namespace std;
- #define FILE_NAME "file"
- #define CONTEST "binary"
- #define M_PI 3.14159265358979323846
- #define ALL(a) (a).begin(), (a).end()
- #define mp make_pair
- #define sqr(x) ((x) * (x))
- typedef long long ll;
- typedef long double ld;
- const ld EPS = 1e-12;
- const ld PI = acos(-1.0);
- const int NN = 10;
- const int N1 = 22;
- vector<vector<int>> vvv(10, vector<int>(10, 0));
- int dp1[NN][NN][N1];
- int dp2[NN][N1];
- ll dp10[N1];
- void count_dp(){
- for (int i = 0; i < NN; ++i){
- for (int j = 0; j < NN; ++j){
- dp1[i][j][0] = vvv[i][j];
- }
- }
- for (int p10 = 1; p10 < N1; ++p10){
- for (int a = 0; a < NN; ++a){
- for (int b = 0; b < NN; ++b){
- dp1[a][b][p10] = a;
- for (int i = 0; i < 10; ++i)
- dp1[a][b][p10] = dp1[dp1[a][b][p10]][b][p10 - 1];
- }
- }
- }
- for (int p10 = 0; p10 < N1; ++p10){
- for (int a = 0; a < NN; ++a){
- dp2[a][p10] = a;
- for (int b = 0; b < NN; ++b){
- dp2[a][p10] = dp1[dp2[a][p10]][b][p10];
- }
- }
- }
- dp10[0] = 1;
- for (int i = 1; i < N1; ++i){
- dp10[i] = dp10[i - 1] * 10ll;
- }
- }
- int func1(int a, int b, ll kol){
- int res = a;
- for (int i = 0; i < N1; ++i){
- int koef = kol % 10ll;
- kol /= 10ll;
- for (int j = 0; j < koef; ++j)
- res = dp1[res][b][i];
- }
- return res;
- }
- int func2(int a, int p10, ll kol){
- map<int, int> M;
- M[a] = 0;
- int ii = 0;
- int ki = 0;
- int ca = a;
- while (1){
- ca = dp2[ca][p10];
- if (M.count(ca)){
- ki = ii;
- ii = M[ca];
- break;
- }
- else{
- M[ca] = ii++;
- }
- }
- int lens = ii;
- int lcyc = ki - ii + 1;
- int res = a;
- if (kol < lens){
- for (int i = 0; i < kol; ++i){
- res = dp2[res][p10];
- }
- return res;
- }
- int rest = kol - ((kol - lens) / lcyc) * lcyc;
- for (int i = 0; i < rest + lens; ++i){
- res = dp2[res][p10];
- }
- return res;
- }
- int get_r10(ll num, int i){
- num = num % dp10[i + 1];
- return num / dp10[i];
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout << fixed << setprecision(12);
- #ifdef DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen(CONTEST ".in", "r", stdin);
- freopen(CONTEST ".out", "w", stdout);
- #endif
- for (int i = 0; i < vvv.size(); ++i){
- for (int j = 0; j < vvv[i].size(); ++j){
- cin >> vvv[i][j];
- }
- }
- ll a, b;
- cin >> a >> b;
- count_dp();
- vector<ll> ans;
- for (int i = 0; i < N1 - 1; ++i){
- int r1 = get_r10(a, i);
- int r2 = get_r10(b, i);
- ll ost_la = a / dp10[i + 1];
- ll ost_ra = a % dp10[i];
- ll ost_lb = b / dp10[i + 1];
- ll ost_rb = b % dp10[i];
- /*if (i == 0){
- ++ost_ra;
- //--ost_rb;
- } */
- int res = r1;
- ll kol;
- if (ost_lb - ost_la > 0){
- kol = dp10[i] - ost_ra - 1ll;
- res = func1(res, r1, kol);
- for (int j = r1 + 1; j < 10; ++j)
- res = dp1[res][j][i];
- res = func2(res, i, ost_lb - ost_la - 1ll);
- for (int j = 0; j < r2; ++j)
- res = dp1[res][j][i];
- kol = ost_rb + 1;
- res = func1(res, r2, kol);
- }
- else if (r1 < r2){
- kol = dp10[i] - ost_ra - 1ll;
- res = func1(res, r1, kol);
- for (int j = r1 + 1; j < r2; ++j)
- res = dp1[res][j][i];
- kol = ost_rb + 1;
- res = func1(res, r2, kol);
- }
- else{
- ll kol = b - a;
- res = func1(res, r1, kol);
- }
- ans.push_back(res);
- }
- reverse(ans.begin(), ans.end());
- int it = 0;
- while (it < ans.size() && ans[it] == 0) ++it;
- if (it == (int)ans.size()){
- cout << 0;
- return 0;
- }
- while (it < ans.size())
- cout << ans[it++];
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement