Se numeste tabela o matrice de N linii si doua 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 si 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:
- prima linie a descrierii unei tabele contine numarul Li de linii ale
acesteia;
- 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
3 <= N <= 30
Numarul de linii in fiecare din
tabelele date este mai mare sau egal cu 0 si mic sau egal
cu 30.
Numarul
de linii din tabela rezultata si din orice tabela rezultata pe parcursul efectuarii operatiilor nu va depasi 100 milioane.
Numarul minim de operatii nu va depasi
100 milioane.
Exemplu
join.in
join.out
Explicatie
3
3
1
1
2
1
1
3
2
1
4
3
4
1
4
3
8
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.