Submission #993423

#	Time	Username	Problem	Language	Result	Execution time	Memory
993423		Phuocbua	K-th path (IZhO11_kthpath)	C++17	0 / 100	0 ms	348 KiB

kthpath

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int phu_ho_di(int m, int n) {
    return static_cast<int>(tgamma(max(m, n) + 1) / (tgamma(min(m, n) + 1) * tgamma(max(m, n) - min(m, n) + 1)));
}

int phu_ho_cac_cu_moi_ngay(int m, int n) {
    return phu_ho_di(m + n - 2, n - 1);
}

int main() {
    int b, a;
    cin >> b >> a;
    vector<vector<char>> arr(b);
    for (int i = 0; i < b; i++) {
        string row;
        cin >> row;
        arr[i] = vector<char>(row.begin(), row.end());
    }
    int k;
    cin >> k;
    int ptr_x = 0, ptr_y = 0;
    string str = "";
    int nt = 1;
    while (ptr_x < b && ptr_y < a) {
        str += arr[ptr_x][ptr_y];
        if (ptr_x == b - 1) {
            ptr_y++;
        } else if (ptr_y == a - 1) {
            ptr_x++;
        } else {
            if (arr[ptr_x + 1][ptr_y] > arr[ptr_x][ptr_y + 1]) {
                if (nt + phu_ho_cac_cu_moi_ngay(b - ptr_x, a - ptr_y - 1) <= k) {
                    nt += phu_ho_cac_cu_moi_ngay(b - ptr_x, a - ptr_y - 1);
                    ptr_x++;
                } else {
                    ptr_y++;
                }
            } else {
                if (nt + phu_ho_cac_cu_moi_ngay(b - ptr_x - 1, a - ptr_y) <= 1) {
                    nt += phu_ho_cac_cu_moi_ngay(b - ptr_x - 1, a - ptr_y);
                    ptr_y++;
                } else {
                    ptr_x++;
                }
            }
        }
    }
    cout << str << endl;
    return 0;
}

• Subtask 1: 0 / 100