#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18 + 5;
const int MAXN = 30;
char mat[MAXN + 1][MAXN + 1];
ll dp[MAXN + 1][MAXN + 1];
bool vis1[MAXN + 1][MAXN + 1], vis2[MAXN + 1][MAXN + 1];
inline void add(ll &x, ll y) {
x += y;
if(x > INF)
x = INF;
}
int main() {
ifstream cin("kthpath.in");
ofstream cout("kthpath.out");
int i, j, n, m;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(i = 1; i <= n; i++) {
cin >> mat[i] + 1;
}
ll k;
cin >> k;
dp[n][m] = 1;
for(i = n; i >= 1; i--) {
for(j = m; j >= 1; j--) {
add(dp[i][j], dp[i + 1][j] + dp[i][j + 1]);
}
}
/*for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
cerr << dp[i][j] << " ";
}
cerr << "\n";
}*/
vector <char> sol;
sol.push_back(mat[1][1] - 'a');
vector < pair <int, int> > cur;
cur.push_back({1, 1});
while(cur.size()) {
vector < pair <int, int> > aux;
vector <ll> fr(26);
for(auto it : cur) {
int l = it.first, c = it.second;
if(l + 1 <= n) {
add(fr[mat[l + 1][c] - 'a'], dp[l + 1][c]);
}
if(c + 1 <= m) {
add(fr[mat[l][c + 1] - 'a'], dp[l][c + 1]);
}
}
char ch = -1;
ll s = 0;
for(i = 0; i < 26; i++) {
s += fr[i];
if(s >= k) {
k -= (s - fr[i]);
ch = i;
break;
}
}
if(ch != -1) {
sol.push_back(ch);
}
for(auto it : cur) {
int l = it.first, c = it.second;
if(l < n && mat[l + 1][c] == ch + 'a') {
aux.push_back({l + 1, c});
}
if(c < m && mat[l][c + 1] == ch + 'a') {
aux.push_back({l, c + 1});
}
}
cur = aux;
}
for(auto it : sol) {
cout << (char) (it + 'a');
}
cin.close();
cout.close();
return 0;
}
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:27:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
cin >> mat[i] + 1;
~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
