Clasa a VII-a lecția 3 - 3 oct 2019

From Algopedia
Jump to navigationJump to search

Anunțuri

  • Avertisment ultimatum următorilor elevi: Dragoș Cojocariu. Dragoș, atitudinea ta este aceeași de la finalul anului trecut. Nu poți continua așa. Temele tale sînt forță brută, la minima rezistență. Mă refer la selecție rezolvată prin sortare și la bile1 rezolvată fără liste, cu o matrice ce depășește memoria. Cu părere de rău, la prima temă în batjocură îți vei pierde calificarea la IQ Academy.

Tema - rezolvări

Selecție

Selecția este o problemă clasică de teoria informaticii.

Comentarii generale

  • Timpul problemei este cam strîns, iar unii din voi ați avut TLE-uri. Iertare, dar altfel nu aveam cum să diferențiez între o sortare bine scrisă, O(n log n) și algoritmul quickselect.
  • Felicitări celor ce au reușit o soluție proprie!
  • Pentru cei ce au implementat pivotarea Lomuto: atenție, este lentă. Folosiți pivotarea Hoare, pe care o vedeți mai jos.
  • Avertismente: Cojocariu (rezolvare prin sortare), Grecu (nici o sursă) Moroșan (nici o sursă)

Swap

Problema swap a fost dată la ONI 2013 baraj gimnaziu.

Problema bile1

Problema bile1 a fost dată la ONI 2012 clasa a 7a. Ea poate fi rezolvată folosind o matrice caracteristică a obstacolelor. Dar dacă memoria permisă ar fi fost mai mică nu o puteam rezolva în acest fel. Rezolvarea cu liste necesită doar O(m+n+p) memorie.

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: prea mulți să vă enumăr, bravo tuturor!
  • Pare că majoritatea ați înțeles listele. Felicitări!
  • Mulți dintre voi au testat finalul de listă astfel: while ( l > 0 ). Este greșit conceptual să comparăm aritmetic un terminator. El este terminator sau nu este. Comparația corectă este cu inegalitate: while ( l != 0 ).
  • Avertismente: Aizic (sursă în batjocură, fără liste), Burac (nici o sursă), Chivu (nici o sursă), Cojocariu (rezolvare fără liste), Dobre (rezolvare fără liste), Hossu (nici o sursă), Mușat (rezolvare fără liste), Moroșan (nici o sursă).

Comentarii individuale

Prima grupă

  • Aizic: Sursă trimisă în ultima clipă, nu are treabă cu ce se cere, o rezolvare cu liste. Scopul problemei este exact să învățam liste. În plus tratezi obstacolele ca și cînd ar fi ordonate după linii, evident incorect. Foarte urît, dacă începi iar cu d-astea ne supărăm.
  • Badea: Program foarte bun, bravo! Observație minoră, testul față de NIL este inegalitate, nu de comparație, mai mare, altfel presupui că NIL este zero.
  • Benescu: Rezolvarea din temă e ciudată, am discutat. Cea din afara temei este foarte bună, bravo! Linia col[0]=list[0]=next[0]=-1; este inutilă, nu ajută la nimic. Observație minoră, testul față de NIL este inegalitate, nu de comparație, mai mare, altfel presupui că NIL este zero.
  • Burac: nimic? Ne supărăm.
  • Calotă: Program foarte bun, bravo! Observație minoră, testul față de NIL este inegalitate, nu de comparație, mai mare, altfel presupui că NIL este zero. Ce este un spațiu în loc de un \n? Este diferența între 0 și 100p.
  • Chivu: nimic? Ne supărăm.
  • Cojocariu: soluție care nu are nici o treabă cu listele. Scopul este să învățăm liste. Mai mult, e forță brută. Nu te-ai obosit măcar să găsești o soluție care se încadrează în memorie.
  • Dobre: Rezolvarea ta nu folosește liste, exact scopul problemei. Ne supărăm!
  • Hossu: Nimic? Ne supărăm!
  • Iordache: Program foarte bun, bravo! Linia li[0]=col[0]=next[0]=-1; este inutilă, nu ajută la nimic.
  • Mocanu: Grijă mare, nu ai înțeles listele. Atenție maximă atît la rezolvare, cît și la lecția de azi!
  • Mușat: Apreciez străduința. Nu apreciez dopajul și mai ales nu apreciez că nu ai folosit liste în rezolvare, care este scopul acestei probleme.
  • Nicola: Program foarte bun, bravo! Atenție la neatenție: numărul de obstacole este 10000, nu 2000. De aceea pici teste.
  • Petcu: Program foarte bun, bravo!
  • Ștefănescu: Construcția listelor este bună, te-ai încîlcit la parcurgerea lor. Cred că mai ai de lămurit puțin listele astea :) Urmărește te rog cu atenție atît rezolvarea problemei cît și lecția de azi.
  • Togan: Program corect. Dar încîlcit, stilul tău :-) Scrii liste[l-1]=i+1; pentru ca mai tîrziu să scrii i=liste[l]-1;. Asta pentru că vrei ca zero să se transforme în -1, terminatorul de listă. Era mai normal să setezi explicit terminatorul, în next[]. Ai grijă la repetiția inutilă de cod la actualizarea vectorului de bile, vezi soluția de mai jos.
  • Voicu: Program foarte bun, bravo!

A doua grupă

  • Asgari: Program foarte bun, bravo! Singura observație de finețe, la "while ( j > NIL )" comparația cu NIL este de egalitate, altfel presupui a priori că NIL este zero :-) Corect: "while ( j != NIL )".
  • Cadîr: Program foarte bun, bravo!
  • Dimulescu: Program foarte bun, bravo! Atenție la indentare! Nu este opțională, este obligatorie!
  • Fares: Program foarte bun, bravo! Din categoria simpatic:
      v[c - 1] += v[c] / 2;
      if (v[c] % 2 == 1)
        v[c - 1]++;

Dacă e 1, adunăm 1. Avem grijă să nu aplicăm matematica decît la orele de mate, nu? :-)

  • Ghica: Ai complicat soluția introducînd cazuri particulare care nu există. Pare că ai înțeles ceva din liste, dar nu complet. Urmărește lecția de azi, sper să te lămurești. Vezi și rezolvarea pe care o voi prezenta. O complicație, de exemplu, e faptul că ai tratat special obstacolele pe prima și ultima linie. Citește cu atenție enunțul: "Pe prima şi ultima linie, respectiv prima şi ultima coloană, nu există obstacole".
  • Grecu: Program foarte bun, bravo, se vede că ai înțeles listele. Observațiile sînt la alt capitol: unu, nu aveai nevoie de un al doilea vector pentru bile, deoarece obstacolele sînt distanțate între ele și valorile din vector nu se influențează una pe alta. Doi, dacă totuși folosești al doilea vector, copierea este ineficientă. Trebuia să folosești o matrice de două linii și să calculezi dintr-o linie în alta, așa cum am făcut anul trecut.
  • Ilie: Program foarte bun, bravo! Ca observație, te-ai complicat adăugînd la coada listei. Era mai simplu să adaugi la începutul listei, cod mai scurt. Obstacolele nu se dau într-o ordine anume.
  • Ipate: Program foarte bun, bravo! Ca observații minore:
    • inițializarea legăturilor cu NIL este inutilă:
  for ( i = 0; i < p; i++ )
    next[i] = -1;
    • Testul de NIL la începutul parcurgerii listei este inutil, el e preluat de "while":
    if (x != -1 ) {
      b[col[x] - 1] = b[col[x] - 1] + (b[col[x]] + 1) / 2;
      b[col[x] + 1] = b[col[x] + 1] + b[col[x]] / 2;
      b[col[x]] = 0;
      x = next[x];
      while ( x != - 1 ) {
        b[col[x] - 1] = b[col[x] - 1] + (b[col[x]] + 1) / 2;
        b[col[x] + 1] = b[col[x] + 1] + b[col[x]] / 2;
        b[col[x]] = 0;
        x = next[x];
      }
    }
  • Marcu: Program foarte bun, bravo! Observație minoră, i și j merg sincron (au aceleași valori) deci nu ai nevoie de ambele:
    i=0;
    for(j=0;j<p;j++) {
        fscanf(fin,"%d%d",&l,&c);
        l--;
        c--;
        col[i]=c;
        next[i]=liste[l];
        liste[l]=i;
        i++;
    }
  • Moroșan: Nimic? Ne supărăm!
  • Nicu: Program foarte bun, bravo!
  • Petrescu: Program foarte bun, bravo! Gîndești puțin încîlcit, e bine sa înveți să simplifici. Iată, la parcurgerea unei liste tu scrii:
        if(liste[i]!=0) {
          colv=liste[i];
          nexti=-1;
          while(nexti!=0) {
            v[col[colv]-1]=v[col[colv]-1]+v[col[colv]]-v[col[colv]]/2;
            v[col[colv]+1]=v[col[colv]+1]+v[col[colv]]/2;
            v[col[colv]]=0;
            nexti=next[colv];
            colv=nexti;
          }
        }

Probleme: acel if nu este necesar, el este preluat de while. Iar colv și nexti merg în paralel, ele au exact aceleași valori cu excepția începutului de parcurgere. Puteai să folosești doar colv. Dacă vei simplifica codul vei obține:

          colv=liste[i];
          while(colv!=0) {
            v[col[colv]-1]=v[col[colv]-1]+v[col[colv]]-v[col[colv]]/2;
            v[col[colv]+1]=v[col[colv]+1]+v[col[colv]]/2;
            v[col[colv]]=0;
            colv=next[colv];
          }
  • Popescu: Program foarte bun, bravo!
  • Rebengiuc: Program foarte corect. Este clar că ai înțeles listele. Comentarii bune, mi-au ușurat înțelegerea codului. Te-ai complicat. Nu e necesar să copiezi obstacolele într-un vector. Poți folosi chiar lista, ea ține locul unui vector. Și deoarece obstacolele sînt distanțate unul de altul nu ai nevoie de un al doilea vector de bile.
  • Rughiniș: Program foarte bun, bravo! Ca observație minoră, nu ai nevoie de if la începutul parcurgerii listei, el este acoperit de while:
    if(list[i]!=NIL){
      a=list[i];
      while(a!=NIL){
        b[col[a]-1]+=b[col[a]]/2+b[col[a]]%2;
        b[col[a]+1]+=b[col[a]]/2;
        b[col[a]]=0;
        a=next[a];
      }
    }
  • Stancu: Program foarte bun, bravo! Atenție la dimensionarea vectorilor! Dacă îi folosești de la 1 pentru a avea NIL zero este în regulă, dar atunci trebuie să îi dimensionezi cu un element în plus! Atenție la greșelile astea, de clasa a cincea :-)
  • Tatomir: Program foarte bun, bravo! Observație minoră, cînd testezi finalul de listă folosești inegalitate (!=) nu comparație. Altfel presupui că el este zero.
  • Teodorescu: Program foarte bun, bravo!
  • Voicu: Ideea programului este bună. Dacă repari obesrvațiile cu grav de mai jos programul tău trece toate testele. Ia aminte la observații, trebuie să îți corectezi stilul de programare. Iată observațiile:
    • Grav: ai denumit greșit fișierul de intrare! Atenție la greșeli de gîgă!
    • Grav: nu ai afișat rezultatul în formatul cerut în enunț!
    • Indentarea! Atenție, nu ai voie să ai greșeli de indentare.
    • Denumirile variabilelor sînt greoaie și greu de urmărit. În loc de vlist[] era mai bine col[] sau coloane[]. În loc de nnlist[] era mai bine next[] care este o denumire clasică.
    • Atenție la dimensionări! Vectorul de bile v[] are doar 2000 de elemente, nu 10000! Așa ceva te poate costa la olimpiadă. Dacă declarai constante cu #define poate nu aveai problema asta.
    • Minor: te-ai complicat adăugînd la coada listei. Este mai ușor să adaugi la început. Scăpai de vectorul finish[].
    • Minor: ar fi bine sa nu declari variabile prin cod, doar la început.

Tema opțională - rezolvări

Zigzag

Problema zigzag a fost dată la ONI 2012 clasa a 7a.

La coadă

Problema lacoada a fost dată la cercul Vianu 2014 clasele 9/10. Este o problemă grea prin gradul de detaliu atît la elaborarea algoritmului, cît și la implementare.

Comentarii generale

  • Este o problemă foarte grea. Felicitări celor ce au reușit să o rezolve: Asgari, Ilie, Voicu.
  • Extra felicitări celor ce au dat o rezolvare ne-dopată, gîndită chiar de ei, cu liste simplu înlănțuite: Ilie. Sfatul meu pentru ceilalți doi: gîndiți cu capul vostru, este în general util.

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-10-03-clasa-7-lectie-info-03-720p.mp4</html5media>

Error in widget video: Unable to load template 'wiki:video'

Liste - continuare

Să vedem cîteva exemple de manipulare a listelor. În toate aceste exemple vom considera liste de întregi reprezentate astfel:

int key[MAXL];  // valori intregi memorate de lista
int next[MAXL]; // următorul element in lista

Lista este definită de prima sa celulă:

int l;

Lungimea unei liste

Să se calculeze lungimea unei liste.

// returneaza numarul de elemente al unei liste
int listLen( int l ) {
  int len = 0;         // initial lungimea este zero

  while ( l != NIL ) { // l pointeaza la o celula?
    len++;             // numaram acea celula
    l = next[l];       // si avansam la urmatoarea celula
  }

  return len; // returnam numarul de celule numarate
}

Cautare liniară element in listă

Să se caute indicele (pointerul) primei celule ce conține un element.

// returneaza indicele celulei care contine elementul e
// sau NIL daca el nu exista
int listFind( int e, int l ) {
  while ( l != NIL && key[l] != e ) // avem o celula in l si nu contine e?
    l = next[l];                    // avansam la urmatoarea celula

  return l; // l va fi fie celula elementului gasit, fie NIL cind negasit
}

Răsturnare listă

Să se răstoarne o listă. La final lista inițială va fi distrusă. Lista cea nouă va conține exact celulele listei originale, dar cu elementele în ordine inversă.

// rastoarna lista primita si returneaza lista rasturnata
// distruge lista initiala
int listReverse( int l ) {
  int cell,  // pointer la o celula
    r = NIL; // lista noua, cea rasturnata
    
  while ( l != NIL ) {
    cell = l;       // memoram celula curenta, capul listei l
    l = next[l];    // avansam in lista l
    next[cell] = r; // adaugam celula curenta in capul listei r
    r = cell;       // cell devine lista r
  }

  return r;
}

Eliminare duplicate în listă sortată crescător

Dată o listă ale cărei elemente sînt ordonate crescător, să se transforme în listă mulțime prin eliminarea duplicatelor.

// transforma o lista ordonata crescator intr-o lista multime
// prin eliminarea duplicatelor
// nu schimba elementul initial al listei
void listSet( int l ) {
  if ( l != NIL ) {
    while ( next[l] != NIL )
      if ( key[next[l]] == key[l] ) // elementul urm este egal cu cel curent?
        next[l] = next[next[l]];    // daca da, elimina elementul urmator
      else
        l = next[l];                // altfel avanseaza la elementul urmator
  }
}

Exemplu de folosire a funcțiilor de mai sus

Iată un program care folosește funcțiile de mai sus:

// Exemple de implementare diverse operatii elementare pe liste
#include <stdio.h>

#define NIL -1
#define MAXL 1000

int key[MAXL];  // valori intregi memorate de lista
int next[MAXL]; // următorul element in lista

// returneaza numarul de elemente al unei liste
int listLen( int l ) {
  int len = 0;         // initial lungimea este zero

  while ( l != NIL ) { // l pointeaza la o celula?
    len++;             // numaram acea celula
    l = next[l];       // si avansam la urmatoarea celula
  }

  return len; // returnam numarul de celule numarate
}

// returneaza indicele celulei care contine elementul e
// sau NIL daca el nu exista
int listFind( int e, int l ) {
  while ( l != NIL && key[l] != e ) // avem o celula in l si nu contine e?
    l = next[l];                    // avansam la urmatoarea celula

  return l; // l va fi fie celula elementului gasit, fie NIL cind negasit
}

// rastoarna lista primita si returneaza lista rasturnata
// distruge lista initiala
int listReverse( int l ) {
  int cell,  // pointer la o celula
    r = NIL; // lista noua, cea rasturnata
    
  while ( l != NIL ) {
    cell = l;       // memoram celula curenta, capul listei l
    l = next[l];    // avansam in lista l
    next[cell] = r; // adaugam celula curenta in capul listei r
    r = cell;       // cell devine lista r
  }

  return r;
}

// transforma o lista ordonata crescator intr-o lista multime
// prin eliminarea duplicatelor
// nu schimba elementul initial al listei
void listSet( int l ) {
  if ( l != NIL ) {
    while ( next[l] != NIL )
      if ( key[next[l]] == key[l] ) // elementul urm este egal cu cel curent?
        next[l] = next[next[l]];    // daca da, elimina elementul urmator
      else
        l = next[l];                // altfel avanseaza la elementul urmator
  }
}

// tipareste elementele unei liste cu un spatiu intre ele
void listPrint( int l, FILE *f ) {
  while ( l != NIL ) {
    fprintf( f, "%d ", key[l] );
    l = next[l];
  }
}

int main() {
  FILE *fin, *fout;
  int n, i, e1, e2, l, r;

  fin = fopen( "lista.in", "r" );
  fscanf( fin, "%d%d%d", &n, &e1, &e2 );
  if ( n == 0 )
    l = NIL;
  else {
    l = 0;
    for ( i = 0; i < n; i++ ) {
      fscanf( fin, "%d", &key[i] );
      next[i] = i + 1;
    }
    next[n - 1] = NIL;
  }
  fclose( fin );
  
  fout = fopen( "lista.out", "w" );
  fprintf( fout, "lista citita: [" );
  listPrint( l, fout );
  fprintf( fout, "]\n" );

  fprintf( fout, "lungime: %d\n", listLen( l ) );

  fprintf( fout, "celula cu cheie %d are indice %d\n", e1, listFind( e1, l ) );
  fprintf( fout, "celula cu cheie %d are indice %d\n", e2, listFind( e2, l ) );

  r = listReverse( l );

  fprintf( fout, "lista inversata: [" );
  listPrint( r, fout );
  fprintf( fout, "]\n" );

  listSet( r );

  fprintf( fout, "lista multime: [" );
  listPrint( r, fout );
  fprintf( fout, "]\n" );

  fprintf( fout, "lungime: %d\n", listLen( r ) );
  fclose( fout );

  return 0;
}

Programul de mai sus a fost executat pe următorul fișier de intrare, lista.in:

10 6 1
9 9 7 7 6 5 5 4 3 3 2

Detecție listă cu buclă

Să se determine dacă o listă se întoarce la ea însăși (unul din elemente pointează la o celulă din-naintea lui). Nu aveți voie să vă legați de valorile memorate, ele pot fi duplicat. Vă puteți folosi strict de legătuirile listei, vectorul next[].

Vă rămîne ca temă de gîndire:

  • Ușor: O(n2) - unde n este numărul de elemente al listei
  • Greu: O(n)

Aplicație: problema onigim

Problema onigim a fost dată la ONI 2013 clasa a 5a. Ea admite o rezolvare foarte scurtă cu liste, desigur peste nivelul clasei a 5a.

Observăm că:

  • Toți elevii care au același număr de elevi "sub ei" vor avea același punctaj.
  • Elevii pot fi, deci, împărțiți în grupuri de elevi cu același punctaj.
  • Numărul de grupuri de elevi este exact numărul de punctaje distincte.
  • Deoarece punctajele distincte se dau în ordine crescătoare, un algoritm banal ar fi să parcurgem grupurile de elevi în ordinea crescătoare a numărului de elevi "sub" acel grup.
  • Toți elevii dintr-un grup primesc nota punctajului curent, apoi avansăm la următorul grup.

Cum implementăm acest algoritm destul de ușor? Trebuie să memorăm cumva aceste grupuri. Astfel, un grup este format din ID-uri, iar toate ID-urile au ceva în comun, care este unic: numărul de elevi "sub" acele ID-uri.

Astfel ne vine ideea să folosim liste: ce-ar fi ca pentru fiecare număr posibil de elevi "sub" să menținem cîte o listă de ID-uri? Dacă pentru un număr de elevi "sub" nu există ID-uri lista va fi vidă.

Iată gruparea de ID-uri de elevi pe liste, conform exemplului din problemă:

6 4
100 150 175 200
4 2 0 0 3 4
Exemplul din problema onigim - concept structură de date

Explicații: avem patru punctaje distincte obținute, 100 150 175 și 200. Avem șase elevi numerotați de la 1 la 6. În desen observăm că avem o listă de doi copii care au zero copii "sub" ei, anume cei cu ID-urile 4 și 3. De aceea ei sînt "agățați" la lista zero. Avem alți doi copii care au patru copii "sub" ei, cu ID-urile 1 și 6. Ei sînt "agățați" la lista patru. Și tot așa, mai avem cîte un singur copil în grupurile 2 și 3.

Cum rezolvăm problema pe baza acestei structuri? Printr-o parcurgere a listelor în ordine, de sus în jos și de la stînga la dreapta. Toate ID-urile din prima listă, 3 și 4, vor primi primul punctaj, adică 100. Toate ID-urile din a doua listă, adică 2, vor primi următorul punctaj, adică 150. Și așa mai departe. Printr-o singură parcurgere putem rezolva toate cele trei puncte ale problemei. Succes! :-)

De remarcat: o implementare îngrijită a acestui algoritm va avea circa 50 de linii, iar ca linii de program efectiv probabil 40.

Aplicație: problema macheta

Problema macheta a fost dată la ONI 2011 clasa a 8a. Ea admite o rezolvare foarte scurtă cu liste, care nu apare printre rezolvările oficiale.

Observăm că:

  • O clădire C este vizibilă dacă există o coordonată x pe care se află numai clădiri mai mici, în fața clădirii C.
  • Putem, astfel, verifica vizibilitatea unei clădiri verificînd vizibilitatea fiecărei coordonate x acoperite de ea.

Deja avem un algoritm rezonabil: pentru fiecare clădire C, parcurgem fiecare coordonată x a ei, iar pentru fiecare coordonată verificăm toate clădirile B dacă:

  • B este în fața lui C (y mai mic)
  • B acoperă coordonata x
  • B are înălțime mai mare ca C

Ce complexitate are acest algoritm?

Pentru fiecare clădire vom parcurge fiecare coordonată a ei, apoi fiecare altă clădire. Rezultă o complexitate O(N2 Lx). După înlocuiri rezultă circa 10 milioane de operații, pare că algoritmul acesta banal s-ar încadra în timp.

Dar să mergem mai departe cu observațiile:

  • Deoarece vom verifica doar clădirile din fața lui C, ne interesează doar clădirile cu y mai mic.
  • Pare a fi util să parcurgem clădirile în ordinea crescătoare a lui y.
  • Pentru fiecare coordonată x a clădirii C curente ne interesează maximul de înălțime de pînă acum, la acea coordonată.
  • Astfel, putem memora un vector de înălțimi maxime, care pentru fiecare coordonată x memorează cea mai înaltă clădire vizibilă la coordonata x, pînă la acest moment.

Cum implementăm acest algoritm?

Cumva trebuie să parcurgem clădirile în ordinea crescătoare a lui y. Soluțiile oficiale sar imediat la sortare. Dar să nu ne grăbim! Sortarea este lentă, ar fi bine să o evităm dacă putem.

Și desigur că putem: ce-ar fi să păstram pentru fiecare coordonată y o listă de clădiri ce încep la acea coordonată? Apoi parcurgem clădirile în ordinea lui y.

Iată gruparea de clădiri pe liste, conform exemplului din problemă:

Exemplul din problema macheta - desen
Exemplul din problema macheta - concept structură de date

Explicații: avem o clădire care începe la y=1 - clădirea 3. Avem o clădire care începe la y=2 - clădirea 2. Avem două clădiri care încep la y=3 - 4 și 5. Și o clădire care începe la y=6 - clădirea 1.

Cum rezolvăm problema pe baza acestei structuri? Printr-o parcurgere a listelor în ordine, de sus în jos și de la stînga la dreapta. Pentru fiecare clădire C parcurgem coordonatele ei x, verificînd vectorul de înălțimi h[x]. Dacă măcar una din înălțimi este mai mică, clădirea este vizibilă. Atenție, înălțimile trebuie actualizate dacă înălțimea lui C este mai mare decît cea a lui h[x].

De remarcat: o implementare îngrijită a acestui algoritm va avea circa 50 de linii, iar ca linii de program efectiv probabil 40.

Ce complexitate are acest algoritm?

Construcția listelor este O(N), numărul de clădiri. Parcurgerea listelor este O(N + Ly). Pentru fiecare clădire vom prelucra în timp constant fiecare coordonată x a sa. Rezultă complexitatea finală O(N Lx + Ly). După înlocuiri rezultă circa 100 000 de operații. Memoria va fi O(Lx), adică neglijabilă.

Din nou, o problemă intenționată spre a fi grea devine simplă prin folosirea listelor.

Temă

Tema 3 clasa a 7a

  • onigim dată la ONI 2013 clasa a 5a rezolvată cu liste
  • macheta dată la ONI 2011 clasa a 8a rezolvată cu liste
  • Opțional: gîndiți-vă la problema din curs, cum detectăm dacă o listă are o buclă în O(n)

Rezolvări aici [2]