Submission #993415

#	Time	Username	Problem	Language	Result	Execution time	Memory
993415		vjudge1	K-th path (IZhO11_kthpath)	Cpython 3	0 / 100	12 ms	2908 KiB

kthpath

#Language: Python(Pypy3)
#Time complexity: O(m*n+(m+n)*i)(i is time complexity of math.comb())
import math
def phu_ho_di(m,n):
    return math.comb(max(m,n),min(m,n))
def phu_ho_cac_cu_moi_ngay(m,n):
    return phu_ho_di(m+n-2,n-1)
def luck():
    b,a = map(int,input().split())
    arr=[list(input()) for x in range(b)]
    k=int(input())
    ptr=[0,0]
    str_=""
    nt = 1
    while ptr[0]<b and ptr[1]<a:
        str_+=arr[ptr[0]][ptr[1]]
        if ptr[0]==b-1:
            ptr[1]+=1
        elif ptr[1]==a-1:
            ptr[0]+=1
        else:
            if ord(arr[ptr[0]+1][ptr[1]]) > ord(arr[ptr[0]][ptr[1]+1]):
                if nt + phu_ho_cac_cu_moi_ngay(b-ptr[0],a-ptr[1]-1) <= k:
                    nt+=phu_ho_cac_cu_moi_ngay(b-ptr[0],a-ptr[1]-1)
                    ptr[0]+=1
                else:
                    ptr[1]+=1
            else:
                if nt + phu_ho_cac_cu_moi_ngay(b-ptr[0]-1,a-ptr[1]) <= 1:
                    nt+=phu_ho_cac_cu_moi_ngay(b-ptr[0]-1,a-ptr[1])
                    ptr[1]+=1
                else:
                    ptr[0]+=1
                    
    print(str_)
luck()

• Subtask 1: 0 / 100