4197 - AB - Revision history

RaulOtet: Pagină nouă: 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
2024-07-30T15:03:46Z

Pagină nouă: 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 <code>N</code> linii și <code>M</code> coloane toate numerele <code>1</code>, <code>2</code>, …, <code>N × M</code>, 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 <co...

New page
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 <code>N</code> linii și <code>M</code> coloane toate numerele <code>1</code>, <code>2</code>, …, <code>N × M</code>, 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 <code>K</code> valori din matrice, care sa nu fie adiacente orizontal sau adiacente vertical. Apoi, ea va încerca să reintroducă aceste <code>K</code> 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 <code>K</code> numere pe pozițiile libere.

= Cerința =
Scrieți un program care, cunoscând matricea AB inițială și <code>Q</code> 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 <code>N</code>, <code>M</code> și <code>Q</code>, separate prin câte un spațiu, având semnificația din enunț. Pe următoarele <code>N</code> linii se află câte <code>M</code> valori, separate prin câte un spațiu, reprezentând matricea AB construită de Alice. Urmează apoi <code>Q</code> interogări, fiecare interogare fiind descrisă pe două linii. Prima linie care descrie o interogare conține numărul natural <code>K</code>, reprezentând numărul de valori eliminate de către Bob. Pe a doua linie din descrierea interogării se află cele <code>K</code> numere eliminate, separate prin câte un spațiu.

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

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 2.000</code>
* <code>1 ≤ Q ≤ 25</code>
* <code>K ≥ 1</code>
* 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 <code>4.000.000</code>.
* 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 <code>1</code>, <code>5</code> și <code>9</code>, matricea după eliminare arătând astfel:

<code>? 2 4</code>

<code>3 ? 8</code>

<code>6 7 ?</code>

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

A doua interogare presupune eliminarea valorilor <code>5</code>, <code>4</code> și <code>6</code>:

<code>1 2 ?</code>

<code>3 ? 8</code>

<code>? 7 9</code>

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

<code>1 2 5</code>

<code>3 6 8</code>

<code>4 7 9</code>

<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

# Example usage:
N, M = 3, 3
queries = [
[5, 7, 9],
[1, 3, 6],
[2, 4, 8]
]
print(is_unique_solution(N, M, queries))
</syntaxhighlight>