#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define foreach(it, S) for (__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define _ ios_base :: sync_with_stdio(false); cin.tie(NULL);
#ifdef inputf
#define fname ""
#else
#define fname "" // <- Here
#endif
const double eps = 1e-9;
const int MaxN = int(2e5) + 256;
const int MOD = int(1e9) + 7;
template <typename T> inline T gcd(T a, T b) {
return b ? gcd (b, a % b) : a;
}
inline bool Palindrome(const string& s) {
return equal(s.begin(), s.end(), s.rbegin());
}
ll c[100][100];
char a[100][100];
int main() { _
#ifdef lcl
freopen(fname".in", "r", stdin);
freopen(fname".out", "w", stdout);
#endif
for (int i = 0; i <= 60; ++i) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; ++j)
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
int n, m; cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
ll k; cin >> k;
int x = 1, y = 1;
int len = 0;
string res = "";
while (len < n + m - 2) {
// cerr << len << endl;
res += a[x][y];
vector <pair <char, pair <int, int> > > v;
if (y + 1 <= m) v.push_back(make_pair(a[x][y + 1], make_pair(x, y + 1)));
if (x + 1 <= n) v.push_back(make_pair(a[x + 1][y], make_pair(x + 1, y)));
sort(all(v));
for (int i = 0; i < (int)v.size(); ++i) {
int X = v[i].second.first;
int Y = v[i].second.second;
char ch = v[i].first;
ll cnt = c[n - X + m - Y][n - X];
// cerr << k << " " << cnt << endl;
if (k <= cnt) {
// res += ch;
x = X; y = Y;
break;
} else {
k -= cnt;
}
}
++len;
}
res += a[x][y];
cout << res;
return 0;
}
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:68:9: warning: unused variable 'ch' [-Wunused-variable]
char ch = v[i].first;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2272 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2272 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
