join
Se numeste tabela o matrice de N linii si 2 coloane, cu elemente intre 1 si 4 inclusiv, in care nu conteaza ordinea liniilor (deci doua tabele se considera identice daca sunt identice dupa ordonarea liniilor).
Se defineste operatia JOIN pe doua tabele T1 si T2, cu P, respectiv Q linii, avand ca rezultat o tabela T. Operatia este aproape similara celei de la baze de date si se efectueaza in felul urmator:
- pentru fiecare linie din T1, de forma X Y, se alege fiecare linie din T2, de forma Y Z;
- se introduce in tabela rezultat o linie de forma X Z.
De exemplu, un JOIN intre tabelele
1 1
2 1
1 3
si
1 4
3 4
duce la obtinerea tabelei
1 4
2 4
1 4
Se considera ca operatia de JOIN se executa in P*Q operatii elementare, astfel:
- pentru fiecare linie din T1, se verifica fiecare linie din T2 si se testeaza daca incepe cu al doilea element din linia din T1;
- in caz afirmativ se introduce o linie in tabela rezultat. Se considera ca acest pas face parte din operatia elementara in care s-a verificat continutul celor doua linii.
Tabela rezultat poate avea intre 0 si P*Q linii, in functie de datele din T1 si T2.
Se observa ca operatia de JOIN nu este comutativa (daca am fi luat tabelele in ordine inversa am fi obtinut o tabela cu 0 linii). In schimb, operatia este asociativa, adica (T1 JOIN T2) JOIN T3 = T1 JOIN (T2 JOIN T3); reamintim ca doua tabele care difera numai prin ordinea liniilor se considera identice.
Cerinta
Dandu-se un sir de N tabele T1, T2, … TN, sa se determine, folosind asociativitatea, numarul minim de operatii elementare in care se poate efectua calculul T1 JOIN T2 JOIN … JOIN TN.
Date de intrare
Fisierul join.in contine:
- pe prima linie numarul N de tabele;
- pe urmatoarele linii descrierile tabelelor, in urmatorul format:
o prima linie a descrierii unei tabele contine numarul Li de linii ale acesteia;
o pe urmatoarele Li linii se gasesc liniile tabelei.
Date de iesire
In fisierul join.out se va afisa un singur numar intreg, numarul minim de operatii elementare in care se poate efectua calculul precizat anterior.
Restrictii
Exemplu
join.in
3
3
1 1
2 1
1 3
2
1 4
3 4
1
4 3
join.out
8
Explicatie
Daca se calculeaza (T1 JOIN T2) JOIN T3, se vor efectua 3*2=6 operatii elementare pentru primul JOIN, va rezulta o tabela cu 3 linii si se vor efectua inca 3*1 operatii pentru al doilea JOIN, rezultand un total de 9 operatii.
Daca alegem varianta T1 JOIN (T2 JOIN T3), atunci primul JOIN efectuat necesita 2 operatii elementare si duce la obtinerea unei tabele cu 2 linii; pentru al doilea JOIN se vor efectua 3*2=6 operatii, deci in total se vor efectua 8 operatii elementare. Acest rezultat este optim.
Timp maxim de executie/test: 0.1 secunde
Stroe Mihai
Univ. Politehnica, Bucuresti