Qvect

qvect

== include(page="template/taskheader" task_id="qvect") ==

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.
 
h2. Cerinta
 
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).

Poveste şi cerinţă...

h2. 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,…,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ţă.

Fişierul de intrare $qvect.in$ ...

h2. 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.

În fişierul de ieşire $qvect.out$ ...

h2. Restricţii

* 1 ≤ N, i, j ≤ 100
* 1 ≤ Q ≤ 1000
* 1 ≤ t ≤ 2
* 1 ≤ k ≤ 5000
* -1 000 000 000 ≤  a ~1~ , a ~2~ , a ~3~ ..., a ~k~   ≤ 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.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. qvect.in |_. qvect.out |

| 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
| 13
3
10

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. 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.

...

== include(page="template/taskfooter" task_id="qvect") ==

9933