#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const int N = 50;
char a[N][N];
ll ways[N][N];
int main()
{
///freopen ("kthpath.in", "r", stdin);
/// freopen ("kthpath.out", "w", stdout);
int n, m, i, j;
cin >> n >> m;
for (i = 1; i <= n; i++)
cin >> a[i] + 1;
ways[n][m] = 1;
for (i = n; i; i--)
for (j = m; j; j--)
if (!(i == n && j == m))
ways[i][j] = ways[i][j + 1] + ways[i + 1][j];
i = 1, j = 1;
ll k;
cin >> k;
cout << a[i][j];
while (!(i == n && j == m))
{
if (i != n && j != m)
{
pair <int, int> minloc = {i + 1, j};
if (a[i + 1][j] > a[i][j + 1])
minloc = {i, j + 1};
if (k > ways[minloc.f][minloc.s])
{
k -= ways[minloc.f][minloc.s];
i = 2 * i + 1 - minloc.f;
j = 2 * j + 1 - minloc.s;
}
else
{
i = minloc.f;
j = minloc.s;
}
}
else
if (i == n)
j++;
else
i++;
cout << a[i][j];
}
return 0;
}
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:17:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | cin >> a[i] + 1;
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
