AjM: Pagină nouă: == Enunt == Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente. == Cerinţa == Să se răspundă la Q întrebări de tipul: a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ? b) 2 i j, cu semnificația: care e...

2024-06-03T17:27:38Z

Pagină nouă: == Enunt == Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente. == Cerinţa == Să se răspundă la Q întrebări de tipul: a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ? b) 2 i j, cu semnificația: care e...

New page

== Enunt ==
Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente.
== Cerinţa ==
Să se răspundă la Q întrebări de tipul:
a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ?
b) 2 i j, cu semnificația: care este valoarea ce se găsește pe poziția mediană în vectorul obținut prin interclasarea vectorilor având numerele de ordine i,i+1,…,j (i<j).
== Date de intrare ==
Fişierul de intrare qvect.in conţine pe prima linie două numerele naturale N Q, separate printr-un spațiu, ce reprezintă numărul de vectori, respectiv numărul de întrebări.

Pe fiecare dintre următoarele N linii se găsește descrierea unui vector sub forma: k a1 a2 … ak, unde k reprezintă numărul de elemente, iar a1 a2 … ak reprezintă elementele vectorului, separate prin câte un spațiu.

Pe fiecare dintre următoarele Q linii se găsește descrierea unei întrebări sub forma unui triplet de numere naturale: t i j, separate prin câte un spațiu, unde t reprezintă tipul întrebării şi poate lua numai valorile 1 sau 2, iar i și j au semnificația precizată în cerinţă.
== Date de ieșire ==
Fişierul de ieşire qvect.out va conţine Q numere întregi, câte unul pe linie, reprezentând în ordine, răspunsurile la cele Q întrebări.
== Restricţii şi precizări ==
* 1 ≤ N, i, j ≤ 100
* 1 ≤ Q ≤ 1000
* 1 ≤ t ≤ 2
* 1 ≤ k ≤ 5000
* -1 000 000 000 ≤ ap ≤ 1 000 000 000
* Prin valoarea aflată pe poziția mediană a unui vector a cu k elemente se înțelege valoarea elementului situat pe poziţia [k/2], adică partea întreagă a lui k / 2.
* 15% dintre teste vor conține numai întrebări de tipul 1
* 15% dintre teste vor conține numai întrebări de tipul 2
== Exemplu ==
; qvect.in
3 3
7 1 4 5 8 11 18 19
6 2 4 5 10 21 29
4 13 14 15 15
2 2 3
1 2 3
2 1 3
; qvect.out
13
3
10
<br>

== Explicație ==
Prima întrebare este de tipul 2. Vectorul nou obținut prin interclasarea vectorilor numerotați cu 2 și cu 3 este următorul: 2,4,5,10,13,14,15,15,21,29 și conține 6+4=10 elemente, valoarea elementului median este 13

A doua întrebare este de tipul 1. Diferența minimă se obține pentru perechea (10,13), unde valoarea 10 aparține vectorului numerotat cu 2, iar valoarea 13 aparține vectorului numerotat cu 3.

A treia întrebare este de tipul 2. Poziția mediană în vectorul nou obținut prin interclasare este (7+6+4)/2 = 8, deci valoarea ce se găsește pe poziția mediană este 10.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def find_min_difference(vector1, vector2):
min_diff = float('inf')
i, j = 0, 0
while i < len(vector1) and j < len(vector2):
diff = abs(vector1[i] - vector2[j])
min_diff = min(min_diff, diff)
if vector1[i] < vector2[j]:
i += 1
else:
j += 1
return min_diff

def merge_and_find_median(vector1, vector2):
merged_vector = []
i, j = 0, 0
while i < len(vector1) and j < len(vector2):
if vector1[i] < vector2[j]:
merged_vector.append(vector1[i])
i += 1
else:
merged_vector.append(vector2[j])
j += 1
merged_vector.extend(vector1[i:])
merged_vector.extend(vector2[j:])
median_index = len(merged_vector) // 2
return merged_vector[median_index]

def main():
with open("qvect.in", "r") as fin:
N, Q = map(int, fin.readline().split())
vectors = [list(map(int, fin.readline().split()))[1:] for _ in range(N)]
queries = [tuple(map(int, fin.readline().split())) for _ in range(Q)]

with open("qvect.out", "w") as fout:
for query in queries:
t, i, j = query
if t == 1:
min_diff = find_min_difference(vectors[i-1], vectors[j-1])
fout.write(f"{min_diff}\n")
elif t == 2:
median = merge_and_find_median(vectors[i-1], vectors[j-1])
fout.write(f"{median}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1104 - Qvect - Revision history