SHARE
TWEET

Untitled

a guest May 19th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math.h>
  3. #include <string.h>
  4. #include <vector>
  5. #include <map>
  6.  
  7. long long nChoosek(int n, int k)
  8. {
  9.     if (k > n) return 0;
  10.     if (k * 2 > n) k = n-k;
  11.     if (k == 0) return 1;
  12.  
  13.     long long result = n;
  14.     for( int i = 2; i <= k; ++i ) {
  15.         result *= (n-i+1);
  16.         result /= i;
  17.     }
  18.     return result;
  19. }
  20.  
  21. void func5() {
  22.     int n, m;
  23.     std::cin >> n;
  24.     std::cin >> m;
  25.     char table[n][m];
  26.     for (int i = 0; i < n + 1; i++) {
  27.         std::string row;
  28.         std::getline(std::cin, row);
  29.         for (int j = 0; j < m; j++) {
  30.             table[i - 1][j] = row[j];
  31.         }
  32.     }
  33.     int l;
  34.     std::cin >> l;
  35.     int sum = n + m - 2;
  36.     int caseCounter = 0;
  37.     int i = 0, j = 0;
  38.     bool flag = false;
  39.     std::map<char, std::vector<std::pair<int, int>>> steps;
  40.     std::vector<std::pair<int, int>> newStep;
  41.     newStep.emplace_back(std::make_pair(0, 0));
  42.     steps[table[0][0]] = newStep;
  43.     std::string res = "";
  44.     res += table[0][0];
  45.     for (int t = 0; t < sum; t++) {
  46.         std::map<char, std::vector<std::pair<int, int>>> newSteps;
  47.         for (std::map<char, std::vector<std::pair<int, int>>>::iterator it = steps.begin(); it != steps.end(); it++){
  48.             for (std::vector<std::pair<int, int>>::iterator it2 = it->second.begin(); it2 != it->second.end(); it2++) {
  49.                 if (it2->first + 1 < n) {
  50.                     std::map<char, std::vector<std::pair<int, int>>>::iterator it3 = newSteps.find(table[it2->first + 1][it2->second]);
  51.                     if (it3 != newSteps.end()) {
  52.                         it3->second.emplace_back(std::make_pair(it2->first + 1, it2->second));
  53.                     } else {
  54.                         newStep.clear();
  55.                         std::vector<std::pair<int, int>> newVec;
  56.                         newStep.emplace_back(std::make_pair(it2->first + 1, it2->second));
  57.                         newSteps[table[it2->first + 1][it2->second]] = newStep;
  58.                     }
  59.                 }
  60.                 if (it2->second + 1 < m) {
  61.                     std::map<char, std::vector<std::pair<int, int>>>::iterator it3 = newSteps.find(table[it2->first][it2->second + 1]);
  62.                     if (it3 != newSteps.end()) {
  63.                         it3->second.emplace_back(std::make_pair(it2->first, it2->second + 1));
  64.                     } else {
  65.                         newStep.clear();
  66.                         std::vector<std::pair<int, int>> newVec;
  67.                         newStep.emplace_back(std::make_pair(it2->first, it2->second + 1));
  68.                         newSteps[table[it2->first][it2->second + 1]] = newStep;
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.         for (std::map<char, std::vector<std::pair<int, int>>>::iterator it = newSteps.begin(); it != newSteps.end(); it++){
  74.             int counter = 0;
  75.             for (std::vector<std::pair<int, int>>::iterator it2 = it->second.begin(); it2 != it->second.end(); it2++) {
  76.                 counter += nChoosek(sum - it2->first - it2->second, n - 1 - it2->first);
  77.             }
  78.             if (l <= counter) {
  79.                 steps.clear();
  80.                 steps[it->first] = it->second;
  81.                 res += it->first;
  82.                 break;
  83.             }
  84.             l -= counter;
  85.         }
  86.     }
  87.     std::cout << res;
  88. }
  89.  
  90. int main()
  91. {
  92.     func5();
  93.     return 0;
  94. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top