| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 17862 | Erzhann | K-th path (IZhO11_kthpath) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
/\ /\
| ).|.( |
| >-< |
=========
It's AdilkhanKo miaaaaaau
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl "\n"
#define foreach(it, S) for(__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define mp make_pair
#define f first
#define s second
#define name ""
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int MaxN = int (2e5) + 256;
const int INF = int(1e9);
const int mod = (int)(1e9) + 7;
ll n, a[44][44], k, m, t;
char c[44][44];
string ans;
void rec(int x, int y){
ans = ans + c[x][y];
if(x == n && y == m){
return;
}
char r, v;
if(x + 1 <= n){
v = c[x + 1][y];
}else{
rec(x, y + 1);
}
if(y + 1 <= m){
r = c[x][y + 1];
}else{
rec(x + 1, y);
}
if(r <= v){
int I = n - x + 1;
int J = m - y;
if(a[I][J] >= k){
rec(x, y + 1);
}else{
k -= a[I][J];
rec(x + 1, y);
}
}else{
int I = n - x;
int J = m - y + 1;
if(a[I][J] >= k)
rec(x + 1, y);
else{
k -= a[I][J];
rec(x, y + 1);
}
}
}
int main () { _
/*#ifdef ONLINE_JUDGE
freopen (name".in","r",stdin);
freopen (name".out","w",stdout);
#else
freopen (".in","r",stdin);
freopen (".out","w",stdout);
#endif */
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> c[i][j];
}
}
cin >> k;
for(int i = 2; i <= m; i++)
a[1][i] = 1;
for(int i = 2; i <= n; i++){
a[i][1] = 1;
for(int j = 2; j <= m; j++){
a[i][j] = a[i - 1][j] + a[i][j - 1];
}
}
cout << a[n][m] << endl;
rec(1, 1);
ans =
cout << ans << endl;
return 0;
}