Advertisement
Guest User

Untitled

a guest
May 19th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.37 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement