3698 - Bemo

Se dă o matrice cu R linii şi C coloane de numere distincte de la 1 la R * C. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate (1, 1), în colţul inferior dreapta, de coordonate (R, C). Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior, adică dacă (i, j) este poziţia unui număr de pe un drum, atunci următorul număr poate fi cel de pe poziţia (i + 1, j) sau cel de pe poziţia (i, j + 1). Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic, de exemplu [1,3,5,6,8] < [1,4,5,6,7].

Date de intrare

Fișierul de intrare bemoIN.txt conține pe prima linie două numere naturale R și C, unde R este numărul liniilor, iar C numărul coloanelor matricei lui Bemo. Pe următoarele R linii se vor găsi câte C numere separate printr-un spaţiu. Fiecare număr va fi unic şi va fi cuprins în intervalul [1, R*C].

Date de ieșire

Fișierul de ieșire bemoOUT.txt va conține R+C-1 numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi scrise separate printr-un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 0 < R, C < 1501;
• Pentru 40% din teste: 0 < R, C < 751;
• Pentru 70% din teste: 0 < R, C < 1301;
• Spunem că un drum A = (a1, a2, …, aR+C-1) este mai mic lexicografic decât un drum B = (b1, b2,…, bR+C-1) dacă există o poziție p astfel încât ap < bp și a1 = b1, a2 = b2, …, ap-1 = bp-1.

Exemplu 1:

bemoIN.txt

4 4
7 4 13 3
8 11 12 2
10 9 1 5
16 14 15 6

bemoOUT.txt

7 4 11 9 1 5 6

Exemplu 2:

bemoIN.txt

4 1502
7 4 13 3
8 11 12 2
10 9 1 5
16 14 15 6

bemoOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line="1"> import sys

NMAX = 2011

A = [[0] * NMAX for _ in range(NMAX)] row = [0] * (NMAX * NMAX) col = [0] * (NMAX * NMAX) selected = [0] * (NMAX * NMAX) elems = [0] * (2 * NMAX)

R = C = nelems = 0

def ReadInput():

   global R, C
   with open("bemoIN.txt", "r") as f:
       data = f.read().split()
   R, C = int(data[0]), int(data[1])
   
   # Verifică imediat după citirea dimensiunilor
   if not (0 < R < 1501 and 0 < C < 1501):
       with open("bemoOUT.txt", "w") as f:
           f.write("Datele nu corespund restrictiilor impuse\n")
       sys.exit()
   
   index = 2
   for i in range(1, R + 1):
       for j in range(1, C + 1):
           A[i][j] = int(data[index])
           row[A[i][j]] = i
           col[A[i][j]] = j
           index += 1

def Solve():

   global nelems
   selected[A[1][1]] = 1
   nelems = 1
   elems[1] = A[1][1]
   
   if R == 1 and C == 1:
       return
   
   selected[A[R][C]] = 1
   nelems += 1
   elems[nelems] = A[R][C]

   for i in range(1, R * C + 1):
       if selected[i]:
           continue
       
       li, ls, before = 1, nelems, 0
       
       while li <= ls:
           mid = (li + ls) // 2
           if row[elems[mid]] <= row[i] and col[elems[mid]] <= col[i]:
               before = mid
               li = mid + 1
           else:
               ls = mid - 1
       
       if before == 0:
           continue
       
       if row[i] <= row[elems[before + 1]] and col[i] <= col[elems[before + 1]]:
           for j in range(nelems, before, -1):
               elems[j + 1] = elems[j]
           elems[before + 1] = i
           nelems += 1
           selected[i] = 1

   if nelems != R + C - 1:
       with open("bemoOUT.txt", "w") as f:
           f.write("Not enough elements selected!\n")
       sys.exit()

def WriteOutput():

   with open("bemoOUT.txt", "w") as f:
       for i in range(1, nelems + 1):
           f.write(f"{elems[i]}")
           if i < nelems:
               f.write(" ")
       f.write("\n")

def main():

   ReadInput()
   Solve()
   WriteOutput()

if __name__ == "__main__":

   main()

</syntaxhighlight>