#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
ifstream fin ("hyper.in");
ofstream fout ("hyper.out");
int n, m, viz[32][32], cnt[32][32];
ll comb[62][62];
ll k;
char ch[32][32];
deque<pair<int, int>>q;
int dl[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};
int main ()
{
//ios_base::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> ch[i][j];
for (int i = 0; i <= n + m; i++) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++)
comb[i][j] = min(INF, comb[i - 1][j] + comb[i - 1][j - 1]);
}
cin >> k;
viz[1][1] = 1;
cnt[1][1] = 1;
q.push_back({1, 1});
for (int pas = 1; pas <= n + m - 1; pas++) {
vector<ll>nr(26);
for (auto p: q) {
if (INF / cnt[p.first][p.second] < comb[n - p.first + m - p.second][n - p.first])
nr[ch[p.first][p.second] - 'a'] += INF;
else
nr[ch[p.first][p.second] - 'a'] += 1ll * cnt[p.first][p.second] * comb[n - p.first + m - p.second][n - p.first];
nr[ch[p.first][p.second] - 'a'] = min(nr[ch[p.first][p.second] - 'a'], INF);
}
for (int j = 1; j < 26; j++)
nr[j] = min(INF, nr[j] + nr[j - 1]);
char letter;
for (int j = 0; j < 26; j++)
if (k <= nr[j]) {
letter = j + 'a';
k -= (j == 0 ? 0 : nr[j - 1]);
break;
}
cout << letter;
int sz = q.size();
for (int i = 1; i <= sz; i++) {
auto p = q.front();
q.pop_front();
if (ch[p.first][p.second] != letter)
continue;
for (int k = 0; k < 4; k++) {
int x = p.first + dl[k];
int y = p.second + dc[k];
if (x >= 1 && x <= n && y >= 1 && y <= m) {
if (!viz[x][y] && x - 1 + y - 1 == pas) {
q.push_back({x, y});
viz[x][y] = 1;
cnt[x][y] = 1;
}
else
cnt[x][y]++;
}
}
}
}
return 0;
}
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:50:10: warning: 'letter' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | char letter;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
