#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()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2908 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
2908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
