Clasa a VI-a lecția 10 - 22 nov 2018

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Matrix

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Badea, Burac, Cojocariu, Hossu, Mocanu, Petcu, Rebengiuc, Rughiniș, Voicu, Dobre, Ipate, Marcu.
  • Mulți dintre voi ați folosit un vector suplimentar la rotații. El nu era necesar.
  • Mulți dintre voi ați folosit o a doua matrice! Extrem de rău, la olimpiadă s-ar putea să nu aveți spațiu.
  • Destul de mulți dintre voi ați avut probleme cu citirea caracterelor. Vedeți vă rog mai jos citirea elegantă.
  • Destul de mulți dintre voi ați făcut rotațiile prin interschimburi. Foarte ineficient, trei atribuiri în loc de una singură. Reveniți la baze, recitiți lecția de rotație din clasa a cincea.
  • Avertismente: Cojocaru pentru temă copiată și fentată (!), Dumitrescu pentru greșeli de bază.

Comentarii individuale

Grupa de dimineață

  • Aizic: Te-ai complicat la rotații, vezi mai jos soluția mai simplă.
  • Badea: Bun!
  • Benescu: Bun, dar ai folosit un vector suplimentar. Se poate și fără, vezi mai jos.
  • Burac: Bun!
  • Calotă: Te-ai complicat la flip. Folosești variabilele j și j2 care au mereu aceeași valoare, j2 e în plus. Și la rotații te-ai complicat foarte mult, mai și folosești un vector suplimentar. Vezi te rog soluția de mai jos.
  • Chivu: Bun, dar ai folosit un vector suplimentar. Se poate și fără, vezi mai jos.
  • Cojocariu: Bun!
  • Cojocaru: Tema ta este clar rezolvată de altcineva. Mai mult, soluția fentează problema, nu execută operații în matrice ci se folosește de o observație pentru a executa operațiuni pe vector.
  • Coman: Bun! Însă: avertisment important de compilare, nu ignora. Citire neelegantă.
  • Dragomir: Bun! Ai grijă la if-uri, ele trebuiau puse unul pe else-ul celuilalt.
  • Dumitrescu: Destul de bine. Ignori reguli de baza: ai declarat matricea in main. Ai declarat matricea de dimensiuni variabile, in loc sa o declari pe maxim, 100. If-urile trebuiau înlănțuite, unul pe else-ul celuilalt. Nu închizi fișiere.
  • Grecu: Ai folosit o matrice suplimentară la rotații. O soluție foarte risipitoare. De ce copiezi matricea în copia ei, la citire? Oricum o suprascrii la rotații. Vezi te rog soluția de mai jos, fără matrice suplimentară.
  • Hossu: Bun!
  • Iordache: ignori reguli de bază: citești c numai pentru a îl transfera în cc, while-ul e de fapt un if (se execută în mod clar o singură dată), nu înlănțuiești if-urile unul pe else-ul altuia. Ideea e interesantă, dar nu funcționează tocmai din cauza greșelii de while versus if, condiția de %2>0, care e corectă pentru flip, nu și pentru rotație.
  • Mocanu: Bun!
  • Mușat: Bun. Rotația ta este ineficientă, face multe interschimburi nenecesare. Copy/paste-ul te-a trădat, ultima rotație este greșită, ai pus incorect limitele de for.
  • Nicola: Bun. Dar ți-ai dat seama că ai o citire ciudată? Doar una din două bucle face ceva util, din cauză că tu citești doar un caracter per buclă, în loc de două. Vezi soluția de mai jos pentru o citire elegantă.
  • Petcu: Bun!
  • Rebengiuc: Bun!
  • Rughiniș: Bun! Dacă făceai și programul ăsta cu while-uri cred ca înnebuneam :)
  • Stoian: Bun! Ai uitat să închizi fișierele! Greșeală de începător, te rog să nu o mai faci.
  • Ștefănescu: Bun! Ai folosit un vector suplimentar. Se poate și fără, vezi mai jos.
  • Togan: Citire foarte urîtă. Dacă testezi un caracter în while nu ai voie ca prima instrucțiune din while să fie o citire a acelui caracter! Am discutat chiar data trecută despre asta, cît de greu e să reții? Rotații ineficiente, prin interschimburi. Nu este necesar, vezi te rog soluția de mai jos.
  • Voicu: Bun!

Grupa de după-amiază

  • Asgari: Bun. Iar ai trimis la arhivă pînă ce ai luat 100p. Ți-am scăzut 10p. Rotații ineficiente, cu interschimburi. Ai uitat clasa a cincea deja? Din cauza lor a trebuit să declari matricea cu un element în plus pe fiecare dimensiune. Urît.
  • Cadîr: Bun! Test incorect de final, cu EOF, trebuia \n. Funcționează și așa, dar face o buclă în plus, degeaba.
  • Dobre: Bun!
  • Fares: Bun! Nu ai închis fișierul de ieșire, atenție! Rotații ineficiente, cu interschimburi. Ai declarat matricea cu un element în plus pe ambele dimensiuni, urît. Vezi te rog soluția de mai jos.
  • Ilie: Bun. Rotații ineficiente, cu interschimburi. Vezi te rog soluția de mai jos.
  • Ipate: Bun!
  • Marcu: Bun!
  • Nicu: Totul ar fi fost minunat dacă nu făceai ciudat ultima rotație. Foarte straniu faptul că ai făcut diferit cele două rotații. Folosești inutil o matrice suplimentară. Ai declarat matricea cu un element în plus pe ambele dimensiuni, urît. Vezi te rog soluția de mai jos.
  • Stancu: E OK, dar ai folosit o matrice suplimentară. Toată ideea era să faci aceste operații în matrice. Ce înseamnă "for(j = 0; j < 1; j++)"? Lenea minții, puteai să scrii doar codul din interiorul acelui for cu 0 în loc de j.
  • Tatomir: Bun! Dar ai o greșeală de bază: nu înlănțui if-urile pe else-uri. Citirea e nu e cea mai elegantă posibil și nici modul cum testezi operația, un pic ineficient.
  • Teodorescu: Bun, dar ai folosit o a doua matrice la rotații. Vezi te rog lecția de anul trecut despre rotații vectori.

Rezolvare

Matrix, exercițiu de lucru cu matrice la vianuarena. Problema este o combinație de subprobleme elementare: flip și rotație. Pentru flip orizontal vom interschimba elemente situate la capete opuse ale coloanelor. Pentru flip vertical vom interschimba elemente situate la capete opuse ale liniilor. Pentru rotație orizontală vom roti fiecare linie, ca pe un vector (am făcut rotații de vectori anul trecut). Pentru rotație verticală vom roti fiecare coloană ca pe un vector.

Iată o posibilă implementare.

#include <stdio.h>

int a[100][100];

int main() {
  FILE *fin, *fout;
  int m, n, l, c, aux;
  char ch;

  fin = fopen( "matrix.in", "r" );
  fscanf( fin, "%d%d", &m, &n );
  for ( l = 0; l < m; l++ )
    for ( c = 0; c < n; c++ )
      fscanf( fin, "%d", &a[l][c] );
  // incepem operatiile
  ch = fgetc( fin );
  ch = fgetc( fin );
  while ( ch != '\n' ) {
    if ( ch == 'F' ) {   // este un flip
      ch = fgetc( fin );
      if ( ch == 'H' ) { // flip orizontal
        for ( l = 0; l < m / 2; l++ )
          for ( c = 0; c < n; c++ ) {
            aux = a[l][c];
            a[l][c] = a[m - 1 - l][c];
            a[m - 1 - l][c] = aux;
          }
      } else {           // flip vertical
        for ( c = 0; c < n / 2; c++ )
          for ( l = 0; l < m; l++ ) {
            aux = a[l][c];
            a[l][c] = a[l][n - 1 - c];
            a[l][n - 1 - c] = aux;
          }
      }
    } else {             // este o rotatie
      ch = fgetc( fin );
      if ( ch == 'H' ) { // rotatie orizontala
        for ( l = 0; l < m; l++ ) {
          aux = a[l][n - 1];
          for ( c = n - 1; c > 0; c-- )
            a[l][c] = a[l][c - 1];
          a[l][0] = aux;
        }
      } else {           // rotatie verticala
        for ( c = 0; c < n; c++ ) {
          aux = a[m-1][c];
          for ( l = m - 1; l > 0; l-- )
            a[l][c] = a[l-1][c];
          a[0][c] = aux;
        }
      }
    }
    ch = fgetc( fin );
  }
  fclose( fin );

  fout = fopen( "matrix.out", "w" );
  for ( l = 0; l < m; l++ ) {
    for ( c = 0; c < n; c++ )
      fprintf( fout, "%d ", a[l][c] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Reorganizare

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Hossu, Iordache, Nicola, Petcu, Rebengiuc, Ștefănescu, Togan, Voicu, Asgari, Dobre, Fares, Ilie, Ipate, Tatomir, Teodorescu.
  • Problema este ușoară. Trebuia să luați cu toții scor mare.
  • Mulți dintre voi ați trimis soluția de anul trecut. Care este, evident, creată cu mintea voastră de anul trecut. Algoritmi ciudați, contorsionați, implementări care nu respectă reguli de bază, cum ar fi duplicarea de cod. Soluții chinuite, pe care le-ați trimis fără să gîndiți. IQ Academy este un loc al gîndirii. Dacă vreți să nu gîndiți locul vostru nu este aici.
  • Topul leneșilor care au copiat soluția urîtă de anul trecut, preferînd să scape, nu să facă tema: Aizic, Badea, Calotă, Chivu, Dumitrescu, Mușat.
  • Avertismente: Cojocaru (soluție rudimentară, incompletă), Coman (soluție complet nefuncțională), Dumitrescu (soluție nefuncțională cu copy/paste greșit)

Comentarii individuale

Grupa de dimineață

  • Aizic: Soluția de anul trecut. Repeți cod, scrii i-- pe ambele ramuri ale if-ului, etc. Ai vrut să scapi, nu să rezolvi tema.
  • Badea: Soluția de anul trecut. Atît de ciudată încît nu știu unde să încep să corectez. Folosești vectori, ba chiar mari. Depui cifrele numerelor pînă la 10000, independent de valoarea de la intrare a lui n. Compui și recompui numărul, inversîndu-l, cînd puteai să răstorni cifrele în vector. O soluție urîtă chiar și la nivelul clasei a 5a. Ai vrut să scapi, nu să rezolvi tema.
  • Benescu: Rar o ciudățenie mai mare. Matrice inutilă, algoritm ciudat. Iar varianta 2 este inacceptabilă, are 92KB. De circa nouă ori mai mult decît se permite la olimpiadă și de circa 100 de ori mai mult decît este necesar pentru o sursă decentă. Urît.
  • Burac: Soluție rezonabilă. Cod puțin dezorganizat, repeți cod dar nu la fel, cred că ai cam multe cazuri particulare. Nu lăsa pauză între literă și operator la 'i++' (nu 'i ++').
  • Calotă: Soluția de anul trecut. Folosești inutil un vector. Ai vrut să scapi, nu să rezolvi tema.
  • Chivu: Soluția de anul trecut. O forță brută nedemnă de tine. Ai vrut să scapi, nu să rezolvi tema. Apoi ai trimis exact același lucru la reorganizare2. Crezi că soluțiile tale se încadrează la categoria 'excelență', sau la IQ Academy?
  • Cojocariu: Soluția de anul trecut. Care ar fi foarte rezonabilă dacă nu ai folosi vectori. La nivelul tău să te mulțumești cu o soluție amărîtă, de anul trecut, fără a încerca să o îmbunătățești, înseamnă un singur lucru: ai vrut să scapi, nu să rezolvi tema.
  • Cojocaru: Soluție incompletă. Tratezi numerele cu maxim trei cifre. O solulție slabă chiar și pentru clasa a 5a.
  • Coman: Programul tău nu merge nici măcar pe testul din enunț. Ori problema a fost foarte grea, ori nu ți-ai dat silința. Cred că a doua variantă este cea adevărată.
  • Dragomir: O soluție bună. Care ar fi foarte rezonabilă dacă nu ai folosi vectori. Ai locuri unde programezi aproximativ, de exemplu:
            v[i] = m / p;
            if (v[i] > 9)
                v[i] = v[i] % 10;

Deci numai dacă este mai mare ca nouă îi calculezi ultima cifră? Dacă este chiar cifră nu poți să faci același lucru? Desigur, codul elegant era:

            v[i] = m / p % 10;

Acestea sînt greșeli de începător.

  • Dumitrescu: Soluția de anul trecut. Cu exact aceleași greșeli. Declari un vector de 10 milioane de întregi, serios? Nu închizi fișiere. Soluție simplistă, preferi să repeți cod decît să generalizezi într-o buclă. Mai mult, pare că și copy/paste este prea greu, programul ar funcționa dacă te țineai de regulă, dar începînd cu if(i<1000) sari instrucțiunea v[j+1]=... Folosești un vector, cînd se poate fără.
  • Grecu: Soluția de anul trecut. Folosești inutil un vector. Ai cam vrut să scapi, nu să rezolvi tema elegant. Însă ești iertat pentru că ai dat o soluție de 100p la reorganizare2, care ar fi mers și aici.
  • Hossu: Bun, frumos! O rezolvare de anul trecut, dar care funcționează pentru reorganizare2, foarte bine. Sper că este a ta în totalitate.
  • Iordache: o soluție interesantă. Te-au folosit de numere mari, aduni unu și folosești cifrele numărului. Ești sigur că ajung 4 cifre în vectorul v[]?
  • Mocanu: Soluția de anul trecut. Ea e OK pentru clasa a cincea. La a șasea, ea e destul de încîlcită, cu repetiție de cod, iar algoritmul nu e tocmai cel mai simplu.
  • Mușat: Soluția de anul trecut. Cu exact aceleași greșeli. Nu închizi fișiere. Soluție simplistă, preferi să repeți cod decît să generalizezi într-o buclă.
  • Nicola: O soluție bună și eficientă, chiar dacă e tot cea de anul trecut. Ideea funcționează și pentru reorganizare2. Funcția maschează o ineficiență: tu recalculezi numărul de cifre de la zero la i, apoi crești i și iar recalculezi de la zero la i. Ai fi putut să adaugi doar diferența de la i la i+1. Cu toate acestea rămîne o soluție bună. Ar fi fost interesant să nu duplici cod, vezi soluția de la reorganizare2, de mai jos.
  • Petcu: Bun, bravo! Mă bucur că ai refăcut programul fără vectori. O soluție bună și ordonată. Singura obiecție la cod neelegant:
            if( j == ( n * ( n + 1 ) / 2 ) - n )//daca este prima cifra
                fprintf( fout, "%d ", kc % 10 );//afisam
            if( j == ( n * ( n + 1 ) / 2 ) - 1 )//daca este ultima cifra
                fprintf( fout, "%d", kc % 10 );//afisam

În primul rînd că cele două if-uri se exclud, deci trebuiau înlănțuite. În al doilea rînd că puteau fi combinate cu sau:

            if( j == ( n * ( n + 1 ) / 2 ) - n || j == ( n * ( n + 1 ) / 2 ) - 1 )//daca este prima sau ultima cifra
                fprintf( fout, "%d ", kc % 10 );//afisam

Întrebare: de ce nu ai folosit același program de la reorganizare2, dacă tot l-ai scris?

  • Rebengiuc: Bun, bravo! Soluție matematică, comună cu reorganizare2. Singurul lucru pe care puteai să-l mai încerci ar fi fost să nu repeți cod :)
  • Rughiniș: Soluția de anul trecut. Nu este rea, dar e puțin copilăroasă, cu "while(m>-1)" în loc de "while(m>=0)", "n=0-n;" în loc de "n=-n;", etc. Aș fi vrut să treci din nou prin ea și să o readuci la zi. Dar te iert pentru că ai rezolvat reorganizare2 :)
  • Stoian: O soluție bună. Păcat că folosești vectori. Ei nu sînt necesari.
  • Ștefănescu: O rezolvare bună, bravo. Atenție, ai avertismente de compilare.
  • Togan: O soluție bună și rapidă, care merge și la reorganizare2. Este cam încîlcită, dar ideea și algoritmul sînt bune.
  • Voicu: O soluție bună și rapidă, care merge și la reorganizare2. Ca eleganță, ți-ai creat singur un caz particular atunci cînd testezi dacă r este zero. Trebuia să numerotezi cifrele în șir de la zero, ca în majoritatea dăților cînd numerotarea de la zero este mai bună.

Grupa de după-amiază

  • Asgari: Soluția de anul trecut. Nu este rea, dar nici elegantă. Apar constante ciudate prin ea, folosești vectori. Pe de altă parte ai rezolvat reorganizare2, de ce nu ai folosit acea soluție, mai bună? Care la rîndul ei este foarte încîlcită și neelegantă, dar măcar are complexitate mult mai bună.
  • Cadîr: O soluție rezonabilă. Compui și recompui numărul, inversîndu-l, cînd puteai să răstorni cifrele în vector, direct.
  • Dobre: O soluție rezonabilă. Nu cred că aveai neapărată nevoie de acel vector mic. Ce este neelegant: pentru a doua cifră refaci complet calculele, cînd puteai să continui de unde ai rămas după prima cifră. Repeți cod. Mai rău, repetiția arată un pic altfel decît originalul, foarte ciudat. Însă felicitări pentru soluția la reorganizare2. De ce nu ai folosit-o și la reorganizare?
  • Fares: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Un pic încîlcită, dar se iartă, căci problema e grea :)
  • Ilie: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Ți-ai creat singur cazuri particulare, pentru că nu ai numerotat cifrele de la zero.
  • Ipate: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Mulțumesc pentru comentarii!
  • Marcu: O soluție bună, matematică, care funcționează și la reorganizare2. E cumva hilar că ai făcut un "for" ca să nu repeți cod, dar restul codului este plin de repetiții. Toate acele if-uri, precum și ramurile switch-ului, sînt compactabile într-un for. Dacă vrei să nu repeți cod uită-te în direcția evidentă mai întîi :) Ești iertată pentru ca ai rezolvat reorganizare2.
  • Nicu: Soluția de anul trecut. O soluție corectă, dar încîlcită, cu multe cazuri particulare nereale. Nu închizi fișiere. Dar ești iertat pentru că ai rezolvat reorganizare2. Tot o soluție încîlcită, dar măcar are complexitate bună. De ce nu ai trimis acea soluție și la reorganizare?
  • Stancu: Idee bună, implementare bună, nu ai depanat pînă la capăt. Dacă ți-ai fi construit teste de mînă sigur o reparai. Lene?
  • Tatomir: Soluția de anul trecut. Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Un pic încîlcită, dar se iartă, căci problema e grea :)
  • Teodorescu: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2.

Rezolvare

Problema reorganizare (ONI 2003, clasa a 6-a). Putem calcula în șirul de cifre a cîta cifră trebuie afișată. Deoarece sint n grupe și fiecare grupă k are k cifre, conform sumei lui Gauss rezultă că primele n-1 grupe vor avea k = n x (n - 1) / 2 cifre. Rezultă că pe noi ne interesează cifrele k + 1 și k + n.

În continuare vom parcurge cifrele, în ordine, pînă la k + n. Cum generăm șirul? Cea mai simplă metodă este să folosim un contor, nrc, pe care îl incrementăm. Valoarea contorului o vom copia în nr, pe care îl vom folosi pentru a extrage cifre din el. Cînd se termină cifrele numărului nr incrementăm contorul nrc și reinițializăm numărul nr cu valoarea contorului. Atenție la extragerea cifrelor. Deoarece cifrele vor fi extrase dinspre stînga vom avea nevoie să calculăm puterea lui 10 la care să împărțim numărul.

Iată programul bazat pe această idee:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, k, i, nr, nrc, p10, cifra;

  fin = fopen( "reorganizare.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  k = n * (n - 1) / 2; // avem nevoie de cifra k + 1 si k + n

  fout = fopen( "reorganizare.out", "w" );
  nr = nrc = 1;
  p10 = 1;
  for ( i = 1; i <= k + n; i++ ) {
    if ( p10 == 0 ) { // numarul curent s-a terminat, pregatim urmatorul
      nrc++;
      nr = nrc;
      p10 = 1000000;
      while ( p10 > nr )
        p10 /= 10;
    }
    cifra = nr / p10;
    nr = nr % p10;
    p10 /= 10;
    if ( i == k + 1 || i == k + n )
      fprintf( fout, "%d ", cifra );
  }
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Deoarece ea parcurge toate cifrele, una cîte una, pînă la cele ce trebuie afișate, iar numărul de cifre de parcurs este n * (n + 1) / 2 rezultă imediat o complexitate O(n2).

O idee avansată și mai eficientă ar fi ca, în loc să parcurgem șirul de cifre, să calculăm cu exactitate din ce numere fac parte cifrele ce trebuie afișate, și pe ce poziții se află ele. Pentru aceasta trebuie să aflăm formulele matematice de calcul. Nu vom detalia o astfel de soluție aici, ea este prezentată la problema reorganizare2.

Reorganizare2

Problema reorganizare2 este o modificare a problemei dată la ONI 2003, clasa a 6a, în care limita lui n este mult mai mare, un milion în loc de 250.

Forța brută este să generăm toate cifrele pînă la cele pe care le afișăm. Ea are complexitate O(n2). Deoarece n este maxim un milion, pătratul lui fiind o mie de miliarde, e clar că nu ne vom încadra în cele 0.2s. Ce putem face? Ca de obicei matematica este cea care ne ajută. Va trebui să găsim un mod de a calcula aceste cifre. Iată un astfel de mod mai jos (nu este singurul).

Ne propunem să calculăm rapid cifra de pe poziția x. Bazat pe aceasta vom calcula cele doua cifre cerute.

Observație 1: în șirul 1 2 3 4... 8 9 10 11... 98 99 100 101... 998 999 1000... avem:

  • 9 numere de o cifră - total 9 cifre
  • 90 numere de două cifre - total 180 cifre
  • 900 numere de trei cifre - total 2700 cifre
  • 9000 numere de patru cifre - total 36000 cifre

...

Putem, deci, avansa rapid prin grupe de numere de g cifre, stabilind numărul de cifre al numărului din care face parte cifra x.

Observație 2: dacă știm că x face parte dintr-un număr de g cifre putem stabili ușor acel număr, precum și a cîta cifră a lui este cifra de pe poziția x:

  • Primul număr din grupa de g cifre este 10g-1
  • Numărul din care face parte x este 10g-1 + x / g (după ce ajustăm x scăzînd din el numărul de cifre din grupele anterioare, de o cifră, două cifre, etc.)
  • Numărul cifrei în cadrul acelui număr este x % g (în numerotare de la zero)

Cu aceasta problema este rezolvată.

Iată o soluție posibilă, bazată pe aceste idei:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, g, cf[2];
  long long nc, nx, x, k;
  
  fin = fopen( "reorganizare2.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  x = k = ((long long)n) * (n - 1) / 2; // avem nevoie de cifra k + 1 si k + n
  for ( i = 0; i < 2; i++ ) { // repetam de doua ori pentru doua cifre
    // calcul cifra x (in numerotare de la zero)
    g = 1;
    nc = 9;
    while ( nc * g <= x ) { // aflam din ce grupa face parte cifra x
      x -= nc * g;
      g++;
      nc *= 10;
    }
    // acum x reprezinta a cita cifra in grupa curenta (numerotare de la 0)
    // aflam numarul din care face parte cifra x
    // grupa incepe la nc/9, numerele au g cifre fiecare
    // nc/9 = cea mai mare putere a lui 10 care incape in numere
    nx = nc / 9 + x / g; // nx = numarul din care face parte cifra x
    // x % g = a cita cifra in numar, deci taiem x cifre de la inceputul lui nx
    // sau g - x % g - 1 cifre de la finalul lui nx
    for ( x = g - x % g - 1; x > 0; x-- ) 
      nx /= 10;      // taiem ultima cifra din nx
    cf[i] = nx % 10; // cifra cautata, in cf[i] deoarece avem doua
    x = k + n - 1;   // pregatim cifra, numarul k+n-1 in numerotare de la zero
  }

  fout = fopen( "reorganizare2.out", "w" );
  fprintf( fout, "%d %d\n", cf[0], cf[1] );
  fclose( fout );
  
  return 0;
}

Ce complexitate are această soluție? Prima parte, găsirea numărului de cifre g va avansa puterea lui 10 pînă la numărul de cifre necesar, avînd, astfel, complexitate O(log x). În a doua parte vom analiza maxim numărul de cifre g, deci ea are tot complexitate O(log x), care va fi și complexitatea totală. Deoarece x este O(n2) rezultă complexitatea O(log n2), totuna cu O(2·log n) (din motive matematică de clasa a zecea pe care încă nu o cunoașteți) adică O(log n).

Rezolvări aici [1]

Lecție

Matrice - continuare

Continuăm cu exerciții de bază cu matrice.

Parcurgerea pe diagonale a unei matrice

Rezolvați problema diagonal:

Se citește o matrice pătrată de caractere. Să se afișeze două linii de caractere, fiecare linie conținînd toate caracterele matricei. Prima linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala principală. A doua linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala secundară. Diagonala principală este din coțul stînga sus în colțul dreapta jos. Diagonala secundară este din colțul dreapta sus, în colțul dreapta jos. Atenție! Fișierul de intrare conține numai matricea de caractere, fiecare linie terminîndu-se cu '\n'. Nu se dă n, dimensiunea matricei, trebuie să o deduceți. Exemplu:

Parcurgerea pe diagonale paralele cu diagonala principală
Parcurgerea pe diagonale paralele cu diagonala secundară
Prima linie afișată: minejoafkpbglchd
A doua linie afișată: abecfidgjmhknlop

Zoom x 2

Rezolvați problema zoomx2:

Se citește o matrice pătrată de caractere. Să se construiască o altă matrice în care fiecare caracter apare de două ori pe orizontală și de două ori pe verticală (zoom ori 2). Exemplu:

Matricea inițială
Matricea finală

Am vorbit despre două variante de implementare: una prin parcurgerea matricei originale, care pentru fiecare element completează patru elemente in matricea finală și a doua variantă care parcurge matricea finală și pentru fiecare element calculează corespondentul în matricea originală.

Căutare submatrice în matrice

Rezolvați problema căutare:

Se dau două matrice pătrate, matricea a de dimensiune m și matricea b de dimensiune n. Se știe că 1 ≤ n ≤ m ≤ 100. Să se spună de cîte ori se regăsește matricea b în matricea a. Exemplu:

Matricea a
Matricea b

În acest caz matricea b apare de 13 ori în matricea a.

Aplicație: problema joc1

Am vorbit despre problema joc1 (ONI 2011 clasa a 7-a), care are o implementare ușoară cu condiția să țineți toate matricele de căutat, inclusiv rotațiile lor, într-un vector de 12 matrice cu elemente zero și unu. Astfel, va trebui să declarați un tablou tridimensional inițializat. Necesită atenție la declararea acestui tablou, dar programul se simplifică.

Temă

  • Terminați, la arhivă, problemele făcute în clasă: diagonal, zoomx2, căutare (la arhivă, în afara concursului-temă).
  • Tema 10 clasa a 6a
    • Ținta dată la ONI 2014 clasa a 6a.
    • Cartier dată la ONI 2012 clasa a 6a.
    • Opțională, dar în cadrul temei, Joc1 dată la ONI 2011 clasa a 7a. Atenţie, se rezolvă elegant cu tablou tridimensional (vectori de matrice).
  • Opțional, la arhivă, foarte grea: cartier2

Rezolvări aici: [2]