Clasa a VI-a lecția 5 - 14 oct 2013

From Algopedia
Jump to: navigation, search

Contents

Anunț

Noul sistem de trimitere a temelor

Pentru o mai bună organizare și notare vom experimenta cu un nou mod de a trimite temele:

  • Pentru fiecare temă vom crea un concurs.
  • Un nou concurs va începe în fiecare luni la ora 19:30. El se va termina lunea următoare la ora 13:30. Temele trebuie rezolvate în cadrul acestui concurs, în intervalul lui activ.
  • Înscrierile se pot face pe toată perioada concursului-temă
  • Cei ce își doresc punctele de concurs (pentru clasamentul de concurs) trebuie să se înscrie lunea, înainte de 19:30. Punctele de concurs nu au nici o influență asupra punctajului obținut la cerc. Sînt doar pentru palmaresul vostru personal. Pentru cerc contează cîte puncte ați luat la temă, indiferent dacă v-ați înscris înainte sau după începerea concursului.
  • Concursul va fi cu penalizare. Ce înseamnă acest lucru?
    • Pentru prima trimitere a temei primiți punctajul conform evaluării.
    • Pentru a doua trimitere a temei veți primi punctajul conform evaluării minus 5%.
    • Pentru fiecare trimitere ulterioară veți primi cîte 5% mai puțin.
    • Nu veți scădea sub 50% din punctajul meritat.
    • Ca întotdeauna, punctajul luat în considerare pentru o problemă este punctajul obținut la ultima trimitere a sursei C.

Avantaje

Avantajele acestui sistem:

  • Vom ști exact cine a trimis temele la timp și cine le-a corectat ulterior.
  • Vom încuraja rezolvarea și testarea completă a problemelor înainte de a trimite sursa la vianuarena, ceea ce este mai aproape de stilul olimpiadelor. Cei ce nu își testează temele, cei ce nu creează propriile teste, cei ce nu își gîndesc soluția adînc, vor pierde puncte.
  • Vom putea penaliza pe cei care pescuiesc. A pescui: a trimite o sursă incompletă în scopul de a afla cîte puncte obține. Cei care pescuiesc vor fi penalizați.
  • Vom putea afișa un clasament al temei curente și al tuturor temelor pînă în prezent.

Cum vă afectează?

Cum vă afectează pe voi această modificare?

  • Pentru a vedea problemele va trebui să vă înscrieți la concursul temă publicat pe algopedia.
  • Pentru ca tema să vă fie punctată va trebui să o trimiteți pînă la data și ora limită (luni, ora 13:30). Da, aceasta înseamnă că inclusiv cercul 2 va trebui să trimită tema mai repede (a fost cerința expresă a Isabelei Coman).
  • Va trebui să vă testați cu mare grijă temele și să vă creați propriile voastre teste. Fiecare trimitere începînd cu a doua vă scade puncte suplimetare.
  • Va trebui să vă gîndiți bine dacă merită să mai trimiteți încă o sursă. Exemplu: dacă am trimis o sursă care a luat 90p, iar apoi trimit una care ia tot 90p, voi lua în final 85p din cauza penalizării.
  • Va trebui să judecați mai bine problemele. Acesta este scopul principal al acestei schimbări.
  • Dacă vă doriți și punctele de concurs acordate de vianuarena (cele de clasament) va trebui să aveți grijă să vă înscrieți înainte de ora de începere a concursului.

Tema - rezolvări

Matrix

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 aul 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

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;
}

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 această soluție, dar vă încurajez să încercați voi să o găsiți.

Rezolvări aici [1]

Lecție

Matrice - continuare

Continuăm cu exerciții de bază cu matrice, de rezolvat în clasă.

Parcurgerea pe diagonale a unei matrice

Rezolvați problema diagonal la vianuarena:

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 la vianuarena:

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 la vianuarena:

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 joc

Am vorbit despre problema joc (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 problemele făcute în clasă: diagonal, zoomx2, căutare (din arhivă, în afara concursului-temă).
  • Înscrieți-vă la concursul tema 5 care conține următoarele probleme:
    • Cartier - ONI 2012 clasa a 6-a. Atenție! Știu că am mai făcut această problemă, dar de data aceasta scopul este să o rezolvăm optim! Vreau să luați 100 de puncte! Ea a fost modificată: i-am adăugat un test pe care nu îl veți trece decît dacă o rezolvați eficient.
    • Joc1 (ONI 2011 clasa a 7-a)

Rezolvări aici: [2]