Clasa a VI-a lecția 29 - 4 apr 2019

Anunțuri

Reluăm concursul de duminică

Duminică 7 aprilie la ora 15:00 vom avea un concurs de pregătire olimpiadă ce va dura patru ore. Problemele de concurs se vor transfera la temă.

Tema 28 - rezolvări

Rezolvări aici: [1]

Lecție

Aceasta este filmarea lecției de dimineață: <html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2019-04-04-clasa-6-lectie-info-29-dimineata-720p.mp4</html5media>

Aceasta este filmarea lecției de după-amiază: <html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2019-04-04-clasa-6-lectie-info-29-dupa-amiaza-720p.mp4</html5media>

Calcul radical din long long

Știm deja funcția sqrt() pe care o putem folosi pentru a calcula radicalul unui număr întreg. Similar, dacă dorim să calculăm radicalul unui număr de tip long long sau unsigned long long avem funcția sqrtl(). Este posibil să aveți nevoie de ea la temă.

În continuare lecția constă din discuții ale problemelor de la temă, precum și a problemei cifru1 rămasă de la lecția trecută.

Problema cifru1

Problema cifru1 a fost dată la ONI 2007 clasa a 6^a. Este o problemă a cărei greutate nu este de natură algoritmică. Greutatea ei constă în implementarea instrucțiunilor din enunț.

Problema poate avea multe abordări. Dar o soluție care nu repetă cod va folosi parcurgerea ramelor bazată pe vectori de direcție. Problema se reduce astfel la calculul maximului laturii unei rame și rotația acelei rame. Pentru aceasta putem copia rama într-un vector auxiliar, pe măsură ce o parcurgem. Cînd memorăm ce latură este maximă memorăm și începutul acelei laturi în vectorul auxiliar. Apoi copiem vectorul auxiliar suprascriind rama. Vom parcurge rama normal, în paralel cu vectorul pe care îl vom parcurge circular începînd cu latura maximală.

Iată o soluție (65 linii):

#include <stdio.h>

int dlin[4] = { 0, 1, 0, -1 }; // diferenta pe linie in functie de directie
int dcol[4] = { 1, 0, -1, 0 }; // diferenta pe coloana in functie de directie
int tablou[100][100];          // matricea tabloului de butoane
int aux[400];                  // vector auxiliar pentru copierea unei rame

int main() {
  FILE *fin, *fout;
  int n, i, j, l, c, rama, mij, dir, suma, smax, jmax, sumatotala;

  fin = fopen( "cifru1.in", "r" );
  fscanf( fin, "%d", &n );
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ )
      fscanf( fin, "%d", &tablou[l][c] );
  fclose( fin );

  sumatotala = 0;
  mij = n / 2;                           // cite rame avem
  for ( rama = 0; rama < mij; rama++ ) { // parcurgem fiecare rama
    smax = -1;              // suma maxima din cele patru laturi ale ramei
    l = c = rama;           // primul element al ramei
    j = 0;                  // am stocat 0 elemente din rama curenta in aux[]
    for ( dir = 0; dir < 4; dir++ ) { // parcurgem cele patru laturi ale ramei
      suma = tablou[l][c]; // suma laturii curente, initializare cu primul elem
      for ( i = 1; i < n - 2 * rama; i++ ) { // pentru celelalte elemente
        l += dlin[dir];        // avansam pe elementul curent
        c += dcol[dir]; 
        suma += tablou[l][c];  // il adunam la suma
        aux[j] = tablou[l][c]; // si il copiem in vectorul auxiliar
        j++;
      }
      if ( suma > smax ) {  // daca laturii este mai mare
        smax = suma;        // o pastram
        jmax = j - n + 2 * rama + 1; // si tinem minte inceputul laturii
      }
    }
    
    sumatotala += smax; // adunam suma maxima la suma totala
    // copiem aux inapoi in matrice, rotit; parcurgem rama copiind de la jmax
    l = c = rama;
    j = jmax; // indicele primului punct din latura maxima copiata in aux[]
    for ( dir = 0; dir < 4; dir++ ) { // parcurgem cele patru laturi ale ramei
      for ( i = 1; i < n - 2 * rama; i++ ) { // pentru celelalte elemente
        l += dlin[dir];   // avansam pe elementul urmator in rama
        c += dcol[dir];
        tablou[l][c] = aux[j];
        j++;
      }
      j %= (4 * n - 8 * rama - 4); // deplasare circulara in  vectorul aux[]
    }
  }

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

  return 0;
}

Temă

Tema 29 clasa a 6^a

• agent 007 dată la Olimpiada locală 2015, clasa a 6^a
• debarcare dată la ONI 2003 clasa a 7^a
• numere9 dată (într-o formă simplificată) la OJI 2017 clasa clasa a 5^a
• flori6 a fost dată la OJI 2006 clasa a 9^a

Atenție! La această temă se vor adăuga problemele de la concursul ce va urma duminică:

Concurs clasa a 6^a

Rezolvări aici: [2]