Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- #include <string.h>
- #include <vector>
- #include <map>
- long long nChoosek(int n, int k)
- {
- if (k > n) return 0;
- if (k * 2 > n) k = n-k;
- if (k == 0) return 1;
- long long result = n;
- for( int i = 2; i <= k; ++i ) {
- result *= (n-i+1);
- result /= i;
- }
- return result;
- }
- void func5() {
- int n, m;
- std::cin >> n;
- std::cin >> m;
- char table[n][m];
- for (int i = 0; i < n + 1; i++) {
- std::string row;
- std::getline(std::cin, row);
- for (int j = 0; j < m; j++) {
- table[i - 1][j] = row[j];
- }
- }
- int l;
- std::cin >> l;
- int sum = n + m - 2;
- int caseCounter = 0;
- int i = 0, j = 0;
- bool flag = false;
- std::map<char, std::vector<std::pair<int, int>>> steps;
- std::vector<std::pair<int, int>> newStep;
- newStep.emplace_back(std::make_pair(0, 0));
- steps[table[0][0]] = newStep;
- std::string res = "";
- res += table[0][0];
- for (int t = 0; t < sum; t++) {
- std::map<char, std::vector<std::pair<int, int>>> newSteps;
- for (std::map<char, std::vector<std::pair<int, int>>>::iterator it = steps.begin(); it != steps.end(); it++){
- for (std::vector<std::pair<int, int>>::iterator it2 = it->second.begin(); it2 != it->second.end(); it2++) {
- if (it2->first + 1 < n) {
- std::map<char, std::vector<std::pair<int, int>>>::iterator it3 = newSteps.find(table[it2->first + 1][it2->second]);
- if (it3 != newSteps.end()) {
- it3->second.emplace_back(std::make_pair(it2->first + 1, it2->second));
- } else {
- newStep.clear();
- std::vector<std::pair<int, int>> newVec;
- newStep.emplace_back(std::make_pair(it2->first + 1, it2->second));
- newSteps[table[it2->first + 1][it2->second]] = newStep;
- }
- }
- if (it2->second + 1 < m) {
- std::map<char, std::vector<std::pair<int, int>>>::iterator it3 = newSteps.find(table[it2->first][it2->second + 1]);
- if (it3 != newSteps.end()) {
- it3->second.emplace_back(std::make_pair(it2->first, it2->second + 1));
- } else {
- newStep.clear();
- std::vector<std::pair<int, int>> newVec;
- newStep.emplace_back(std::make_pair(it2->first, it2->second + 1));
- newSteps[table[it2->first][it2->second + 1]] = newStep;
- }
- }
- }
- }
- for (std::map<char, std::vector<std::pair<int, int>>>::iterator it = newSteps.begin(); it != newSteps.end(); it++){
- int counter = 0;
- for (std::vector<std::pair<int, int>>::iterator it2 = it->second.begin(); it2 != it->second.end(); it2++) {
- counter += nChoosek(sum - it2->first - it2->second, n - 1 - it2->first);
- }
- if (l <= counter) {
- steps.clear();
- steps[it->first] = it->second;
- res += it->first;
- break;
- }
- l -= counter;
- }
- }
- std::cout << res;
- }
- int main()
- {
- func5();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement