Clasa a VI-a lecția 11 - 29 nov 2018

From Algopedia
Jump to: navigation, search

Comentarii temă

  • Felicitări celor ce s-au străduit și au obținut rezultate bune la temă.
  • Am remarcat că unii din voi trimiteți soluțiile mele la teme, ușor modificate. Sînt foarte măgulit de aceasta, dar tot copiere se cheamă. În situația aceasta se află și unii din cei avertizați.

Tema - rezolvări

Diagonal

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

Răspuns: Problema are mai multe subpuncte de discutat:

Citirea matricei

Cum citim o matrice pătrată de caractere căreia nu ni se dă dimensiunea? În două etape:

  • Prima etapă: pornim cu n = 0. Citim prima linie, caracter cu caracter, pînă ce întîlnim sfîrșitul de linie, '\n'. În același timp vom depozita caracterele citite în prima linie a matricei și vom incrementa n pentru fiecare caracter citit.
  • A doua etapă: citire normală. Acum îl știm pe n, mai avem de citit n-1 linii.

Parcurgerea pe diagonale principale

Există mai multe moduri de a efectua parcurgerea. Un mod relativ ușor de ținut minte este următorul: ne imaginăm că ne "plimbăm" prin elementele de start ale fiecărei diagonale. Pornim de la elementul de jos-stînga, anume a[n-1][0]. Apoi ne deplasăm în sus, către colțul de sus-stînga, adică elementul a[0][0]. Apoi schimbăm direcția, deplasîndu-ne către dreapta, spre elementul a[0][n-1]. Acestea sînt elementele de pornire ale diagonalelor dorite. Putem implementa această "plimbare" din două etape. Prima etapă este cea verticală, apoi cea orizontală. Vom avea, deci, două bucle for.

Pentru fiecare din elementele de start identificate mai sus vom identifica lungimea diagonalei. Pentru prima etapă lungimile diagonalelor vor fi n - lin, unde lin este linie pe care se află elementul de start. Pentru a doua etapă lungimea va fi n - col, unde col este coloana pe care se află elementul de start.

Avem acum coordonatele elementelor de start, precum si lungimile. Tot ce avem de făcut acum este ca, pentru fiecare diagonala, să executăm o buclă de la 0 la lungimea diagonalei, buclă în care vom calcula liniile și coloanele parcurse si vom afișa acele elemente. Urmăriți programul pentru exemplificare.

Parcurgerea pe diagonale secundare

O vom face similar. Vom identifica elementele de start ale diagonalelor, care sint elementele primei linii și ale ultimei coloane. Apoi, pentru fiecare element vom identifica lungimea diagonalei care pornește din acel element. În final, pe baza elementelor de start și a lungimilor calculate vom calcula liniile și coloanele parcurse pentru fiecare diagonală și vom afișa elementele respective.

Iată o implementare bazată pe aceste idei:

#include <stdio.h>

char a[100][100];

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

  // citire matrice patrata de caractere fara a sti dimensiunea
  fin = fopen( "diagonal.in", "r" );
  // citim intii prima linie pina la '\n', pentru a-l afla pe n
  n = 0;
  ch = fgetc( fin );
  while ( ch != '\n' ) {
    a[0][n] = ch;
    n++;
    ch = fgetc( fin );
  }
  // apoi citim celelalte n-1 linii
  for ( l = 1; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      a[l][c] = fgetc( fin );
    fgetc( fin );
  }
  fclose( fin );

  fout = fopen( "diagonal.out", "w" );
  // afisam diagonalele paralele cu diagonala principala
  // mai intii cele de sub ea
  for ( l = n - 1; l > 0; l-- )
    for ( c = 0; c < n - l; c++ )
      fputc( a[l+c][c], fout );
  // apoi cele de deasupra
  for ( c = 0; c < n; c++ )
    for ( l = 0; l < n - c; l++ )
      fputc( a[l][l+c], fout );
  fputc( '\n', fout );
  // afisam diagonalele paralele cu diagonala secundara
  // mai intii cele de deasupra ei
  for ( c = 0; c < n; c++ )
    for ( l = 0; l <= c; l++ )
      fputc( a[l][c-l], fout );
  // apoi cele de dedesubt
  for ( l = 1; l < n; l++ )
    for ( c = n - 1; c >= l; c-- )
      fputc( a[n-1+l-c][c], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Zoomx2

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ă

Avem 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ă.

Iată soluția bazată pe parcurgerea matricei finale, în care calculăm corespondentul în matricea inițială:

#include <stdio.h>

char a[50][50], b[100][100];

int main() {
  FILE *fin, *fout;
  int n, l, c;

  fin = fopen( "zoomx2.in", "r" );
  fscanf( fin, "%d ", &n ); // atentie la spatiul de dupa %d ! este necesar!
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      a[l][c] = fgetc( fin );
    fgetc( fin );
  }
  fclose( fin );

  n *= 2;
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ )
      b[l][c] = a[l/2][c/2];

  fout = fopen( "zoomx2.out", "w" );
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      fputc( b[l][c], fout );
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

Căutare

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.

Răspuns: căutarea unei matrice într-o altă matrice este similară cu căutarea unui element într-un vector. Și în acest caz putem folosi stegulețe. Ca și în cazul vectorului, ar fi inutil și ar complica codul, sau l-ar face mai ineficient. Nu le vom folosi.

Rezolvarea eficientă, demnă de voi, este următoarea: vom "potrivi" matricea b la toate pozițiile posibile în matricea a. Pentru fiecare poziție ne vom întreba dacă b se regăsește în a la acea poziție. Dacă da, vom incrementa un contor de apariții. Rămîne de clarificat cum facem testul de egalitate.

Vom proceda în felul următor: vom varia doi indici, linia l și coloana c, de la zero la n. Însă vom fom folosi o singură buclă, nu două. În acea buclă vom rămîne cîtă vreme mai avem elemente de testat și cîtă vreme elementele curente se potrivesc. Apoi vom incrementa coloana c. Dacă în urma incrementării ea depășește valoarea maximă, n-1, atunci o resetăm la zero și incrementăm linia l.

De unde știm în final, la ieșirea din buclă, dacă toate elementele au fost egale, sau ne-am oprit mai devreme? Uitîndu-ne la linia l. Dacă toate elementele au fost egale ea va ajunge la valoarea l, altfel nu. În acest fel nu avem nevoie de nici un steguleț, iar codul rămîne scurt, concis și clar.

Iată implementarea bazată pe aceste idei:

#include <stdio.h>

char a[100][100], b[100][100];

int main() {
  FILE *fin, *fout;
  int m, n, lin, col, l, c, nrap;

  fin = fopen( "cautare.in", "r" );
  fscanf( fin, "%d%d ", &m, &n ); // atentie la spatiul dupa %d, e important!
  // matricea a, in care cautam
  for ( l = 0; l < m; l++ ) {
    for ( c = 0; c < m; c++ )
      a[l][c] = fgetc( fin );
    fgetc( fin ); // citim in gol (aruncam) caracterul '\n'
  }

  // matricea b, sablonul pe care il cautam in matricea a
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      b[l][c] = fgetc( fin );
    fgetc( fin ); // citim in gol (aruncam) caracterul '\n'
  }
  fclose( fin );

  nrap = 0;
  for ( lin = 0; lin <= m - n; lin++ )
    for ( col = 0; col <= m - n; col++ ) {
      l = c = 0;
      // comparam elementele sablonului cu ale matricei pina cind
      // dam de o inegalitate sau pina ce se termina elementele sablonului
      while ( l < n && a[lin + l][col + c] == b[l][c] ) {
        c++;
        if ( c >= n ) {
          l++;
          c = 0;
        }
      }
      if ( l >= n ) // toate elementele au fost egale
        nrap++;
    }

  fout = fopen( "cautare.out", "w" );
  fprintf( fout, "%d\n", nrap );
  fclose( fout );

  return 0;
}

Problema Ținta

Problema ținta a fost dată la ONI 2014 clasa a 6a.

Această problemă are o tentă matematică. Ea necesită o observație fără de care rezolvarea devine mai grea: punctajul obținut nu se schimbă dacă ne deplasăm pe diagonale de tipul dreapta-sus - stînga-jos. Faceți voi demonstrația că este așa. De aici, dacă faceți desenul, rezultă că pentru punctul c) va trebui să afișăm n-2 elemente pe linia a doua și n-3 elemente pe penultima linie, de unde rezultă imediat răspunsul la punctul b) și anume sînt 2n-5 punctaje distincte.

Fără această observație crucială cum am putea rezolva problema? Observînd că punctajele sînt relativ mici. Ele sînt maxim de opt ori n2, adică opt milioane. Putem încerca să folosim un vector de frecvență al scorurilor, avînd grijă la gestiunea memoriei, căci am fi la limită. Nu voi urma această cale, sînteți liberi să o explorați voi.

Rezolvarea 1

O rezolvare destul de directă ar fi să construim matricea. Vom avea patru cazuri particulare: diagonale pare deasupra diagonalei secundare, diagonale impare deasupra diagonalei, diagonale pare sub diagonală și diagonale impare sub diagonală. Putem trata cazurile par/impar în mod similar, calculînd elementul de start și lungimea diagonalei și folosind o variabilă sens ce va fi -1 sau 1 pentru a ne da direcția de parcurgere.

Iată programul bazat pe această idee:

#include <stdio.h>

int a[1000][1000]; // matricea

int main() {
  FILE *fin, *fout;
  int n, i, l, c, ls, cs, sens, nr, p, u, s, ll, cc;

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

  // completam matricea cu numere
  sens = -1;
  nr = 1;
  // mai intii deasupra diagonalei secundare
  for ( l = 0; l < n; l++ ) {
    ls = l % 2 == 0 ? l : 0;
    cs = l % 2 == 0 ? 0 : l;
    for ( i = 0; i <= l; i++ )
      a[ls + sens * i][cs - sens * i] = nr++;
    sens = -sens;
  }
  // apoi sub diagonala secundara
  for ( l = n; l < 2 * n - 1; l++ ) {
    ls = l % 2 == 0 ? n - 1 : l - n + 1;
    cs = l % 2 == 0 ? l - n + 1 : n - 1;
    for ( i = 0; i < 2 * n - 1 - l; i++ )
      a[ls + sens * i][cs - sens * i] = nr++;
    sens = -sens;
  }
  
  fout = fopen( "tinta.out", "w" );
  // punctul a) afisam matricea
  for ( l = 0; l < n; l++ ) {
    fprintf( fout, "%d", a[l][0] );
    for ( c = 1; c < n; c++ )
      fprintf( fout, " %d", a[l][c] );
    fprintf( fout, "\n" );
  }
  // punctul b) afisam numarul de scoruri unice
  fprintf( fout, "%d\n", 2 * n - 5 );
  // punctul c) afisam acele scoruri
  p = l = 1;
  u = n - 1;
  for ( i = 0; i < 2; i++ ) {
    for ( c = p; c < u; c++ ) { 
      s = -a[l][c];
      for ( ll = -1; ll < 2; ll++ )
        for ( cc = -1; cc < 2; cc++ )
          s += a[l+ll][c+cc];
      fprintf( fout, "%d ", s );
    }
    l = n - 2;
    p = 2;
  }
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Această soluție are timpul O(n2) și memoria tot O(n2).

Rezolvarea 2

Rezolvarea doi este încă și mai matematică, bazîndu-se pe ideea de a găsi o formulă care pe baza liniei și coloanei să ne dea valoarea elementului din matrice. În acest fel nu vom avea nevoie să construim matricea, deoarece o putem afișa direct. Cum găsim această formulă? Vom proceda în trei etape.

Etapa 1

Vom simplifica matricea de construit pentru a fi cît mai regulată posibil: să considerăm că toate diagonalele merg de jos în sus. Ulterior vom "inversa" diagonalele impare. De asemenea vom căuta formula numai pentru elementele deasupra diagonalei. Pentru simplificare vom considera că liniile și coloanele sînt numerotate de la zero și că numerele completate încep și ele de la zero (vom ajusta ulterior cu unu). Pentru a găsi formula să observăm următoarele:

  • Elementele de pe diagonalele noastre au proprietatea că l + c = constant = numărul diagonalei.
  • Deoarece diagonalele cresc in lungime cu 1 rezultă că primul element al diagonalei (cel pe coloana 0) va fi o sumă a lui Gauss. Mai exact, a[l][0] = 1 + 2 + ... + l = l(l+1)/2
  • Pentru a obține celelalte elemente ale diagonalei va trebui să adunăm 1 pentru fiecare coloană la dreapta. Aceasta se face ușor adunînd chiar coloana. Suma lui Gauss se va face nu pînă la l ci pînă la suma s = l+c:

a[l][c] = s(s+1)/2 + c

Etapa 2

Ne propunem acum să inversăm. diagonalele impare, pentru a obține matricea dorită. În continuare vom calcula doar elementele de deasupra diagonalei. Observăm că diagonalele inversate pornesc cu cel mai mare număr și apoi scad. Ce valoare scade în paralel? Valoarea liniei elementelor. Deci formula va trebui să fie valoarea celui mai mic element al diagonalei la care adunăm valoarea liniei. Formula este, deci: a[l][c] = s(s+1)/2 + l. Cum combinăm cele două formule? Putem să testăm paritatea numărului diagonalei, dat de l + c. Putem însă, mai simplu, să adunăm atît l cît și c înmulțite cu restul împărțirii la doi ale lui l + c, respectiv l + c + 1:

a[l][c] = s(s+1)/2 + (s%2)*l + ((s+1)%2)*c

Avem acum formula completă pentru elementele aflate deasupra diagonalei secundare.

Etapa 3

Ne propunem acum să găsim formula pentru restul elementelor. Cel mai simplu mod de a face aceasta este sa "răsucim" matricea cu 180 de grade. În această matrice putem înlocui l cu n-1-l și c cu n-1-c. Apoi calculăm valoarea elementelor, iar în final o scădem din n*n-1 pentru a obține valoarea corectă. Nu voi detalia aici formulele.

Remarcăm că nu avem nevoie decît de un test în formula finală, și anume testul dacă elementul dorit se află deasupra diagonalei. Testăm acest lucru cu l+c < n.

Programul bazat pe aceste idei este unul avansat. Îl anexez mai jos pentru cei ce vor să îl studieze.

#include <stdio.h>

// calculeaza a[l][c]
int element( int l, int c, int n ) {
  int semn, s = l + c, s1, adun;
  if ( s < n ) {
    s1 = s;
    semn = 1;
    adun = 1;
  } else {
    l = n - 1 - l;
    c = n - 1 - c;
    s1 = l + c;
    semn = -1;
    adun = n * n;
  }
  return semn * ((s1 * (s1 + 1) / 2 + (s % 2) * l + ((s + 1) % 2) * c)) + adun;
}

// afiseaza o linie a matricei, elemente cu indicii primul <= c < ultimul
void afiseazaLinie( int l, int primul, int n, FILE *fout ) {
  int i, j, c, s;
  for ( c = primul; c < n - 1; c++ ) {
    s = -element( l, c, n );
    for ( i = -1; i < 2; i++ )
      for ( j = -1; j < 2; j++ )
        s += element(l+i, c+j, n);
    fprintf( fout, "%d ", s );
  }
}

int main() {
  FILE *fin, *fout;
  int n, l, c;

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

  fout = fopen( "tinta.out", "w" );
  for ( l = 0; l < n; l++ ) {         // afisam matricea, pe linii
    for ( c = 0; c < n; c++ )
      fprintf( fout, "%d ", element( l, c, n ) );
    fprintf( fout, "\n" );
  }
  fprintf( fout, "%d\n", 2 * n - 5 ); // afisam numarul de scoruri unice
  // afisam acele scoruri
  afiseazaLinie( 1, 1, n, fout );   // mai intii cele de pe a doua linie
  afiseazaLinie( n-2, 2, n, fout ); // apoi cele de pe penultima linie
  fprintf( fout, "\n" );            // final de linie
  fclose( fout );

  return 0;
}

Această soluție are timpul O(n2) iar memoria O(1), ceea ce o face superioară soluției 1.

Cartier

Problema 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.

Răspuns: Să lămurim pe rînd aspectele acestei probleme.

La punctul a) trebuie ca, pentru un bloc cu numărul de cuburi ncub, să calculăm înălțimea pentru care perimetrul este minim. O rezolvare care nu implică matematică este să generăm toți divizorii lui ncub și să luăm perechea (d, ncub / d) cu proprietatea că d + ncub / d este minim. Această soluție trebuie implementată cu grijă! Dacă vom genera toți divizorii lui ncub vom depăși timpul, deoarece ncub maxim este 13000, iar numărul maxim de blocuri este 5000. Înmulțindu-le obținem numărul de operații necesare, adică 65 de milioane, prea multe pentru o zecime de secundă. Soluția corectă este să calculăm numai divizorii pînă la {\sqrt  {n}}.

O soluție mai bună, bazată pe matematică, ne spune că suma dintre lungime și lățime este cu atît mai mică cu cît blocul este mai aproape de pătrat. Înseamnă că putem porni cu lățimea de la sqrt(n), scăzînd-o cu unu pînă ce ncub se divide cu ea. În acel moment am găsit lațimea optimă. Înălțimea o obținem împărțind ncub la lățime. La punctul b) vom însuma lățimile găsite.

Punctul c) este cel mai greu. Trebuie să găsim două numere în vector neprime între ele la distanță maximă. Putem rezolva acest punct în două moduri:

Forța brută presupune să ne uităm la toate perechile de indici (i, j) și să calculăm cmmdc(v[i], v[j]). Vom reține maximul din j - i + 1. Această soluție este O(n2 · log maxbloc) și va depăși timpul pe teste mari. Putem face mici optimizări, căutînd întîi elemente la distanță n, apoi elemente la distanță n-1, etc, oprindu-ne la prima pereche care are cmmdc mai mare ca unu. Însă soluția va avea în continuare aceeași complexitate și va pica teste.

O soluție mai eficientă va folosi doi vectori de frecvență ai divizorilor: prim și ultim. Vectorul prim[d] va memora prima poziție în secvență unde apare un element divizibil cu d. Vectorul ultim[d] va memora ultima poziție în secvență unde apare un element divizibil cu d. Pentru a calcula acești vectori vom calcula toți divizorii înălțimilor. Pentru fiecare divizor găsit pe o poziție i vom stoca i în prim[d] dacă prim[d] este zero. întotdeauna vom stoca i în ultim[d]. În final, după ce am terminat de calculat cei doi vectori, îi vom parcurge și vom calcula maximul dintre ultim[d] - prim[d] + 1. Acesta este rezultatul la punctul c).

Această soluție, implementată corect, căutînd divizorii unui număr numai pînă la radical, are complexitatea O(n\cdot {\sqrt  {maxbloc}}) și se încadrează în timp pentru cele mai mari teste.

#include <stdio.h>
#include <math.h>

int prim[13001], ultim[13001];

int main() {
  FILE *fin, *fout;
  int n, i, ncub, h, hmax, nhmax, s, d1, d2, lmax;

  fin= fopen( "cartier.in", "r" );
  hmax = 0;
  nhmax = 0;
  s = 0;
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%d", &ncub );
    // punctul a: inaltimea maxima a unui bloc
    h = sqrt( ncub );
    while ( ncub % h > 0 )
      h--;
    h = ncub / h;
    if ( h > hmax ) {
      hmax = h;
      nhmax = 1;
    } else if ( h == hmax )
      nhmax++;
    // punctul b: suma latimilor blocurilor
    s += ncub / h;
    // punctul c: calculam divizorii primi si-i depunem in 
    // vectorul de frecventa al divizorilor
    // calculam toti divizorii lui h
    for ( d1 = 2; d1 * d1 <= h; d1++ )
      if ( h % d1 == 0 ) {
        if ( prim[d1] == 0 )
          prim[d1] = i;
        ultim[d1] = i;
        d2 = h / d1;
        if ( prim[d2] == 0 )
          prim[d2] = i;
        ultim[d2] = i;
      }
    // il adaugam si pe el insusi
    if ( h > 1 ) {
      if ( prim[h] == 0 )
        prim[h] = i;
      ultim[h] = i;
    }
  }
  fclose( fin );

  lmax = 0;
  for ( d1 = 2; d1 <= 13000; d1++ )
    if ( ultim[d1] - prim[d1] > lmax )
      lmax = ultim[d1] - prim[d1];

  fout= fopen( "cartier.out", "w" );
  fprintf( fout, "%d\n%d\n%d\n", nhmax, s, lmax + 1 );
  fclose( fout );

  return 0;
}

Joc1

Problema Joc1 (ONI 2011 clasa a 7-a). Răspuns: această problemă este extrem de simplă dacă o implementați cum am discutat la cerc. Vom memora fiecare formă ca o matrice preinițializată de 3 x 3 elemente. De asemenea, vom memora cele 12 matrice într-un vector de matrice. Aceste vector de matrice este un tablou tridimensional! Și preinițializat! Sună complicat, dar în realitate nu este. Odată completat acest vector, care conține matrice cu elemente zero și unu, programul este banal: este o simplă căutare de matrice în matrice, ca cea făcută la cerc, cu diferența că vom avea o buclă în plus care ciclează prin forme. Iată implementarea:

#include <stdio.h>

char a[99][99];

// Vom memora cele 12 matrice de 3 x 3 grupate intr-un vector 'forme'. Vectorul
// va avea 12 elemente, iar fiecare element al sau va fi o matrice 3 x 3.
char forme[12][3][3] = {
  { { 1, 0, 0 },
    { 1, 0, 0 },
    { 1, 1, 1 } },
  { { 1, 1, 1 },
    { 1, 0, 0 },
    { 1, 0, 0 } },
  { { 1, 1, 1 },
    { 0, 0, 1 },
    { 0, 0, 1 } },
  { { 0, 0, 1 },
    { 0, 0, 1 },
    { 1, 1, 1 } },
  { { 1, 0, 0 },
    { 1, 1, 1 },
    { 1, 0, 0 } },
  { { 1, 1, 1 },
    { 0, 1, 0 },
    { 0, 1, 0 } },
  { { 0, 0, 1 },
    { 1, 1, 1 },
    { 0, 0, 1 } },
  { { 0, 1, 0 },
    { 0, 1, 0 },
    { 1, 1, 1 } },
  { { 0, 1, 1 },
    { 1, 1, 0 },
    { 0, 1, 0 } },
  { { 0, 1, 0 },
    { 1, 1, 1 },
    { 0, 0, 1 } },
  { { 0, 1, 0 },
    { 0, 1, 1 },
    { 1, 1, 0 } },
  { { 1, 0, 0 },
    { 1, 1, 1 },
    { 0, 1, 0 } }
};

int main() {
  FILE *fin, *fout;
  int m, n, l, c, lin, col, i, nrap;

  fin = fopen( "joc1.in", "r" );
  fscanf( fin, "%d%d ", &n, &m ); // atentie la spatiul dupa %d, e important!
  // matricea a, in care cautam
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < m; c++ )
      a[l][c] = fgetc( fin ) - '0';
    fgetc( fin ); // citim in gol (aruncam) caracterul '\n'
  }
  fclose( fin );

  nrap = 0;
  for ( lin = 0; lin <= n - 3; lin++ )
    for ( col = 0; col <= m - 3; col++ ) {
      for ( i = 0; i < 12; i++ ) { // pentru fiecare din cele 12 sabloane
        l = c = 0;
        // comparam elementele sablonului cu ale matricei pina cind
        // dam de o inegalitate sau pina ce se termina elementele sablonului
        while ( l < 3 && 
                ((a[lin + l][col + c] == 1) || 
                 (a[lin + l][col + c] == forme[i][l][c])) ) {
          c++;
          if ( c >= 3 ) {
            l++;
            c = 0;
          }
        }
        if ( l >= 3 ) // toate elementele au fost egale
          nrap++;
      }
    }

  fout = fopen( "joc1.out", "w" );
  fprintf( fout, "%d\n", nrap );
  fclose( fout );

  return 0;
}

Rezolvări aici: [1]

Lecție

Test matrice, apoi discuție despre problema ținta de la temă.

Grupa de dimineață

Grupa de după-amiază

Tema

Tema 11 clasa a 6a

  • em1 dată la testul de azi
  • em2 dată la testul de azi
  • codificare dată la concursul .campion 2007
  • medalion dată la ONI 2012 clasa a 6a

Rezolvări aici [2]