4197 - AB

Alice tocmai s-a decis să-și impresioneze fratele mai mic, Bob, cu abilitățile sale de deducție matematică. Astfel, ea așează într-o matrice cu N linii și M coloane toate numerele 1, 2, …, N × M, astfel încât fiecare linie și respectiv fiecare coloană, să fie sortată strict crescător. O matrice cu aceste proprietăți se numește o matrice AB. Alice îi cere apoi lui Bob să elimine K valori din matrice, care sa nu fie adiacente orizontal sau adiacente vertical. Apoi, ea va încerca să reintroducă aceste K valori în matrice astfel încât sa rămână o matrice AB. După câteva încercări, Alice realizează că, în anumite situații pot exista mai multe moduri de a aranja cele K numere pe pozițiile libere.

Cerința

Scrieți un program care, cunoscând matricea AB inițială și Q interogări, constând fiecare dintr-o listă de elemente eliminate din matrice, determină pentru fiecare interogare dacă există o soluție unică de a aranja elementele eliminate în matrice astfel încât aceasta să fie matrice AB.

Date de intrare

Prima linie a datelor de intrare conține trei numere naturale N, M și Q, separate prin câte un spațiu, având semnificația din enunț. Pe următoarele N linii se află câte M valori, separate prin câte un spațiu, reprezentând matricea AB construită de Alice. Urmează apoi Q interogări, fiecare interogare fiind descrisă pe două linii. Prima linie care descrie o interogare conține numărul natural K, reprezentând numărul de valori eliminate de către Bob. Pe a doua linie din descrierea interogării se află cele K numere eliminate, separate prin câte un spațiu.

Date de ieșire

Veți afișa Q linii, fiecare reprezentând un număr întreg. Cea de a i-a linie va conține răspunsul pentru a i-a interogare: răspunsul va fi 1 dacă există o soluție unică de a aranja elementele eliminate astfel încât să se obțină o matrice AB, respectiv 0 în caz contrar.

Restricții și precizări

• 1 ≤ N, M ≤ 2.000
• 1 ≤ Q ≤ 25
• K ≥ 1
• Se garantează că în orice interogare numerele eliminate sunt distincte și respectă condiția din enunț (nu sunt adiacente orizontal sau vertical).
• Numărul total al valorilor din interogări nu depășește 4.000.000.
• Punctajul pentru un test va fi acordat doar dacă răspunsurile pentru toate interogările din testul respectiv sunt corecte.
• Datorită dimensiunilor mari ale datelor de intrare, doar unele teste au fost adăugate.

Exemplu:

Intrare

3 3 2
1 2 4
3 5 8
6 7 9
3
1 5 9
3
5 4 6

Ieșire

1
0

Explicație

Prima interogare presupune eliminarea numerelor 1, 5 și 9, matricea după eliminare arătând astfel:

? 2 4

3 ? 8

6 7 ?

Se observă că aranjarea celor trei numere este unică, obținându-se matricea originală.

A doua interogare presupune eliminarea valorilor 5, 4 și 6:

1 2 ?

3 ? 8

? 7 9

Rearanjarea nu este unică, o soluție alternativă fiind:

1 2 5

3 6 8

4 7 9

<syntaxhighlight lang="python" line="1"> def is_unique_solution(N, M, queries):

   results = []
   for query in queries:
       if len(query) == 0:
           results.append("YES")
           continue
       
       positions = [(val - 1) // M, (val - 1) % M for val in query]
       sorted_query = sorted(query)
       
       for i in range(1, len(sorted_query)):
           pos1 = positions[sorted_query[i-1] - 1]
           pos2 = positions[sorted_query[i] - 1]
           
           if pos1[0] == pos2[0] and pos1[1] + 1 == pos2[1]:
               results.append("NO")
               break
           if pos1[1] == pos2[1] and pos1[0] + 1 == pos2[0]:
               results.append("NO")
               break
       else:
           results.append("YES")
   
   return results

1. Example usage:

N, M = 3, 3 queries = [

   [5, 7, 9],
   [1, 3, 6],
   [2, 4, 8]

] print(is_unique_solution(N, M, queries)) </syntaxhighlight>