Advertisement
Guest User

Untitled

a guest
Nov 30th, 2015
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.67 KB | None | 0 0
  1. #pragma warning (disable : 4996)
  2.  
  3. #include <iostream>
  4. #include <fstream>
  5. #include <vector>
  6. #include <set>
  7. #include <algorithm>
  8. #include <map>
  9. #include <string>
  10. #include <iomanip>
  11.  
  12. using namespace std;
  13.  
  14. #define FILE_NAME "file"
  15. #define CONTEST "binary"
  16. #define M_PI 3.14159265358979323846
  17. #define ALL(a) (a).begin(), (a).end()
  18. #define mp make_pair
  19. #define sqr(x) ((x) * (x))
  20.  
  21. typedef long long ll;
  22. typedef long double ld;
  23. const ld EPS = 1e-12;
  24. const ld PI = acos(-1.0);
  25.  
  26. const int NN = 10;
  27. const int N1 = 22;
  28. vector<vector<int>> vvv(10, vector<int>(10, 0));
  29. int dp1[NN][NN][N1];
  30. int dp2[NN][N1];
  31. ll dp10[N1];
  32.  
  33. void count_dp(){
  34.     for (int i = 0; i < NN; ++i){
  35.         for (int j = 0; j < NN; ++j){
  36.             dp1[i][j][0] = vvv[i][j];
  37.         }
  38.     }
  39.  
  40.     for (int p10 = 1; p10 < N1; ++p10){
  41.         for (int a = 0; a < NN; ++a){
  42.             for (int b = 0; b < NN; ++b){
  43.                 dp1[a][b][p10] = a;
  44.                 for (int i = 0; i < 10; ++i)
  45.                     dp1[a][b][p10] = dp1[dp1[a][b][p10]][b][p10 - 1];
  46.             }
  47.         }
  48.     }
  49.  
  50.     for (int p10 = 0; p10 < N1; ++p10){
  51.         for (int a = 0; a < NN; ++a){
  52.             dp2[a][p10] = a;
  53.             for (int b = 0; b < NN; ++b){
  54.                 dp2[a][p10] = dp1[dp2[a][p10]][b][p10];
  55.             }
  56.         }
  57.     }
  58.  
  59.     dp10[0] = 1;
  60.     for (int i = 1; i < N1; ++i){
  61.         dp10[i] = dp10[i - 1] * 10ll;
  62.     }
  63. }
  64.  
  65. int func1(int a, int b, ll kol){
  66.     int res = a;
  67.  
  68.     for (int i = 0; i < N1; ++i){
  69.         int koef = kol % 10ll;
  70.         kol /= 10ll;
  71.         for (int j = 0; j < koef; ++j)
  72.             res = dp1[res][b][i];
  73.     }  
  74.  
  75.     return res;
  76. }
  77.  
  78. int func2(int a, int p10, ll kol){
  79.     map<int, int> M;
  80.     M[a] = 0;
  81.     int ii = 0;
  82.     int ki = 0;
  83.     int ca = a;
  84.     while (1){
  85.         ca = dp2[ca][p10];
  86.         if (M.count(ca)){
  87.             ki = ii;
  88.             ii = M[ca];
  89.             break;
  90.         }
  91.         else{
  92.             M[ca] = ii++;
  93.         }
  94.     }
  95.  
  96.     int lens = ii;
  97.     int lcyc = ki - ii + 1;
  98.     int res = a;
  99.     if (kol < lens){
  100.         for (int i = 0; i < kol; ++i){
  101.             res = dp2[res][p10];
  102.         }
  103.         return res;
  104.     }
  105.  
  106.     int rest = kol - ((kol - lens) / lcyc) * lcyc;
  107.     for (int i = 0; i < rest + lens; ++i){
  108.         res = dp2[res][p10];
  109.     }
  110.  
  111.     return res;
  112. }
  113.  
  114. int get_r10(ll num, int i){
  115.     num = num % dp10[i + 1];
  116.     return num / dp10[i];
  117. }
  118.  
  119. int main()
  120. {
  121.     ios_base::sync_with_stdio(false);
  122.     cin.tie(NULL);
  123.     cout << fixed << setprecision(12);
  124. #ifdef DEBUG
  125.     freopen("input.txt", "r", stdin);
  126.     freopen("output.txt", "w", stdout);
  127. #else
  128.     freopen(CONTEST ".in", "r", stdin);
  129.     freopen(CONTEST ".out", "w", stdout);
  130. #endif  
  131.  
  132.     for (int i = 0; i < vvv.size(); ++i){
  133.         for (int j = 0; j < vvv[i].size(); ++j){
  134.             cin >> vvv[i][j];
  135.         }
  136.     }
  137.     ll a, b;
  138.     cin >> a >> b;
  139.     count_dp();
  140.  
  141.     vector<ll> ans;
  142.     for (int i = 0; i < N1 - 1; ++i){
  143.         int r1 = get_r10(a, i);
  144.         int r2 = get_r10(b, i);
  145.         ll ost_la = a / dp10[i + 1];
  146.         ll ost_ra = a % dp10[i];
  147.         ll ost_lb = b / dp10[i + 1];
  148.         ll ost_rb = b % dp10[i];
  149.         /*if (i == 0){
  150.             ++ost_ra;
  151.             //--ost_rb;
  152.         }   */     
  153.  
  154.         int res = r1;
  155.         ll kol;
  156.         if (ost_lb - ost_la > 0){
  157.             kol = dp10[i] - ost_ra - 1ll;
  158.             res = func1(res, r1, kol);
  159.  
  160.             for (int j = r1 + 1; j < 10; ++j)
  161.                 res = dp1[res][j][i];
  162.  
  163.             res = func2(res, i, ost_lb - ost_la - 1ll);
  164.            
  165.             for (int j = 0; j < r2; ++j)
  166.                 res = dp1[res][j][i];
  167.  
  168.             kol = ost_rb + 1;
  169.             res = func1(res, r2, kol);
  170.         }
  171.         else if (r1 < r2){
  172.             kol = dp10[i] - ost_ra - 1ll;
  173.             res = func1(res, r1, kol);
  174.  
  175.             for (int j = r1 + 1; j < r2; ++j)
  176.                 res = dp1[res][j][i];
  177.  
  178.             kol = ost_rb + 1;
  179.             res = func1(res, r2, kol);
  180.         }
  181.         else{
  182.             ll kol = b - a;
  183.             res = func1(res, r1, kol);
  184.         }
  185.         ans.push_back(res);
  186.     }
  187.     reverse(ans.begin(), ans.end());
  188.     int it = 0;
  189.     while (it < ans.size() && ans[it] == 0) ++it;
  190.     if (it == (int)ans.size()){
  191.         cout << 0;
  192.         return 0;
  193.     }
  194.     while (it < ans.size())
  195.         cout << ans[it++];
  196.  
  197.     return 0;
  198. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement