.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » join

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
join


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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.

Stroe Mihai
Univ. Politehnica, Bucuresti

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: produs, salvare, alpinist
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor