Clasa a VI-a lecția 33 - 18 apr 2019

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Comentarii generale

Mă bucur să văd că vă descurcați din ce în ce mai bine. Felicitări! Ce am remarcat:

  • Scorurile atît la concurs cît și la temă au fost bune.
  • În ordinea crescătoare a greutății problemele pare că au fost: sume1, popas, reconstituire2, roboțel.
  • Mulți dintre voi se îmbunătățesc, scriind cod mai clar, mai citibil, mai concis. Bravo!
  • Ați început să folosiți mai des vectori de frecvență și bordare, unii dintre voi încercați să nu duplicați cod. Aici mai aveți de lucru, dar sînteți pe calea cea bună.
  • Ați început să denumiți variabilele cu nume sugestive și să puneți comentarii pentru a face codul citibil. Bravo! Mi-aș dori ca toți să faceți acest lucru.

Problema roboțel

Comentarii generale

  • De departe cea mai grea problemă de la temă. Este o problemă care codată neglijent devine "tractor".
  • Aproximativ jumate dintre voi ați avut probleme în a trece toate testele.
  • Majoritatea ați găsit perechile blocante cu un algoritm care la prima vedere pare neoptim. La o analiză mai atentă el este optim. Există, însă, un algoritm care este optim și este mai ușor de analizat la clasa a șasea. Am remarcat soluția lui Teodorescu și a lui Hossu. Vom vorbi despre aceasta mai jos.
  • Unii din voi nu s-au descurcat la oprirea robotului într-o pereche blocantă. Este o parte mai grea.

Rezolvare

Problema roboțel a fost dată la ONI 2016, clasa a 6a. Este o problemă de simulare ce are aspecte deosebite. Desigur că vom folosi clasicii vectori de direcție, bordare, vectori de codificare si decodificare a directiei numerice versus punct cardinal.

Partea deosebită constă în determinarea perechilor blocante. Cum vom proceda? O variantă simplă ar fi ca pentru fiecare literă de pe tablă să căutăm în direcția indicată de acea literă să vedem dacă întîlnim opusul ei. Pe exemplul din enunț, dacă avem litera 'N' la linia 4 și coloana 1 ne vom deplasa în sus, scăzînd linia, pînă ce ieșim din matrice sau întîlnim o literă. Deoarece litera întîlnită va fi 'S', la coordonatele (0 1), am găsit o pereche blocantă. Astfel vom găsi toate perechile blocante de două ori, pornind dintr-un capăt și din celălalt capăt, deci numărul contorizat va trebui împărțit la doi în final. De asemenea vom avea grijă să marcăm căsuțele unde încep perechi blocante, pentru a putea executa mișcarea roboțelului la punctul 2.

Ce complexitate are această soluție? Vom parcurge toate elementele tablei, deci R2 operații. Iar pentru fiecare din elemente vom parcurge alte maxim R elemente, rezultînd o complexitate de O(R3), care se va încadra lejer în timp. În realitate, aceasta este o complexitate care nu se poate atinge. De ce? Pentru că deși căutarea unei perechi blocante poate fi O(R), elementele parcurse în cadrul unei perechi blocante nu pot fi parcurse din nou. Ceea ce înseamnă că parcurgem matricea de cel mult două ori, o dată pentru perechile blocante orizontale și o dată pentru perechile verticale. Complexitatea reală este, în fapt, O(R2) și este optimă.

Există și o altă soluție optimă care este mai ușor de analizat. O prezint mai jos deoarece tehnica prezintă interes și pentru alte probleme.

Vom reține pentru fiecare linie ultimul 'E' întîlnit și pentru fiecare coloană ultimul 'S' întîlnit. Parcurgem matricea pe linii și cînd întîlnim un caracter 'V' ne întrebăm care este ultimul 'E' întîlnit pe acea linie. Cînd întîlnim un caracter 'N' ne întrebăm care este ultimul caracter 'S' întîlnit. Această soluție este tot O(R2).

Cînd găsim o pereche blocantă reținem pentru acele coordonate tipul perechii blocante și lungimea drumului pînă la celălalt capăt al perechii. Aceasta ne va ajuta pentru testul de oprire al robotului.

Iată o soluție posibilă, didactică (109 linii de cod):

#include <stdio.h>

#define N 0
#define E 1
#define S 2
#define V 3
#define MAXR 200

int dl[4] = { -1, 0, 1, 0 }; // directia pe linii
int dc[4] = { 0, 1, 0, -1 }; // directia pe coloane
int dir[128]; // dir[ch] = directia imprimata de caracterul ch
int chdir[4] = { 'N', 'E', 'S', 'V' }; // chdir[i] = char ce da directia i
int drum[4];      // solutia, drum[i] = numarul de deplasari in directia i
int us[MAXR + 2]; // us[c] = ultimul 'S' vazut pe coloana c

char tab[MAXR + 2][MAXR + 2]; // tabla robotului
int per[MAXR + 2][MAXR + 2];  // perechile blocante

int main() {
  FILE *fin, *fout;
  int i, p, r, k, l, c, ue, d;

  for ( i = 0; i < 4; i++ ) // setam directiile pentru fiecare caracter posibil
    dir[chdir[i]] = i;
  
  fin = fopen( "robotel.in", "r" );
  fscanf( fin, "%d%d%d", &p, &r, &k );
  for ( l = 0; l <= r+1; l++ ) // bordam marginile
    per[l][0] = per[0][l] = per[l][r+1] = per[r+1][l] = -1;
  for ( i = 0; i < k; i++ ) {
    fscanf( fin, "%d%d ", &l, &c ); // linia si coloana semnalizatorului
    tab[l][c] = fgetc( fin );       // memoram semnalizatorul pe tabla
  }
  fclose( fin );

  // 1: determina perechile blocante in per[][]
  for ( l = 1; l <= r; l++ ) {
    ue = 0;
    for ( c = 1; c <= r; c++ ) {
      switch ( tab[l][c] ) {
      case 'E':
        ue = c;    // memoram coloana ultimului 'E' intilnit
        us[c] = 0; // nu avem nici un S in sus
        break;
      case 'S':
        ue = 0;    // nu avem nici un E spre stinga
        us[c] = l; // memoram linia ultimului 'S' intilnit
        break;
      case 'V':
        if ( ue > 0 ) { // memoram o pereche pe orizontala
          per[l][ue] = E * 256 + c - ue; // c - ue patrate spre est
          per[l][c] = V * 256 + c - ue;  // c - ue patrate spre vest
        }
        ue = 0;    // nu avem nici un E spre stinga
        us[c] = 0; // nu avem nici un S in sus
        break;
      case 'N':
        if ( us[c] > 0 ) { // memoram o pereche pe verticala
          per[us[c]][c] = S * 256 + l - us[c];// l - us patrate spre sud
          per[l][c] = N * 256 + l - us[c]; // l - us patrate spre nord
        }
        ue = 0;    // nu avem nici un E spre stinga
        us[c] = 0; // nu avem nici un S in sus
      }
    }
  }

  fout = fopen( "robotel.out", "w" );
  if ( p == 1 ) { // afisam perechile blocante
    p = 0;        // nu am afisat nici o pereche inca
    for ( l = 1; l <= r; l++ ) {
      for ( c = 1; c <= r; c++ )
        switch ( per[l][c] / 256 ) {
        case E:
          p = 1; // am afisat o pereche
          fprintf( fout, "%d %d %d %d\n", l, c, l, c + per[l][c] % 256 );
          break;
        case S:
          p = 1; // am afisat o pereche
          fprintf( fout, "%d %d %d %d\n", l, c, l + per[l][c] % 256, c );
        }
    }
    if ( p == 0 )
      fprintf( fout, "0\n" );
  } else {     // simulam deplasarea robotului
    l = c = 1; // pozitia initiala a robotului
    d = E;     // directia initiala a robotului
    while ( per[l][c] == 0 ) { // nu am ajuns in punct de final
      if ( tab[l][c] > 0 )     // daca e nevoie sa schimbam directia
        d = dir[tab[l][c]];    // o schimbam
      l += dl[d];              // avansam
      c += dc[d];
      drum[d]++; // am mers inca o casuta in directia d
    }

    if ( per[l][c] > 0 ) // am ajuns la o pereche blocanta
      drum[dir[tab[l][c]]] += per[l][c] % 256; // drumul pina la casuta pereche
    else
      drum[d]--; // iesirea din tabla nu se pune

    fprintf( fout, "%d", drum[0] );
    for ( d = 1; d < 4; d++ )
      fprintf( fout, " %d", drum[d] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Citirea este O(K).
  • Determinarea perechilor blocante este O(R2).
  • Afișarea perechilor blocante este O(R2).
  • Simularea robotului este O(lungime drum), dar, deoarece se garantează că roboțelul se oprește el nu poate parcurge mai mult de O(R2) căsuțe.

Deoarece K ≤ R2 rezultă complexitatea totală de O(R2).

Memoria ocupată este tot O(R2), mai exact circa 200KB. ea poate fi redusă folosind mai strîns întregii celor două matrice. Matricea per[][] poate fi unsigned char modificînd puțin algoritmul.

Iată o soluție bazată pe soluția anterioară, care factorizează puțin codul și folosește ceva mai puțină memorie, circa 80KB (92 linii de cod):

#include <stdio.h>

#define N 0
#define E 1
#define S 2
#define V 3
#define MAXR 200
#define BORD (MAXR+1)

int dl[4] = { -1, 0, 1, 0 }; // directia pe linii
int dc[4] = { 0, 1, 0, -1 }; // directia pe coloane
int ecoef[4] = { 0, 1, 0, 0 }; // cind dam de est stocam coloana
int scoef[4] = { 0, 0, 1, 0 }; // cind dam de sud stocam linia
int chdir[4] = { 'N', 'E', 'S', 'V' }; // chdir[i] = char ce indica directia i
int dir[128];     // dir[ch] = directia imprimata de caracterul ch
int drum[4];      // solutia, drum[i] = numarul de deplasari in directia i
int us[MAXR + 2]; // us[c] = ultimul 'S' vazut pe coloana c

unsigned char tab[MAXR + 2][MAXR + 2]; // tabla robotului
unsigned char per[MAXR + 2][MAXR + 2]; // lungimile perechilor blocante

int main() {
  FILE *fin, *fout;
  int i, p, r, k, l, c, ue, d;

  for ( i = 0; i < 4; i++ ) // setam directiile pentru fiecare caracter posibil
    dir[chdir[i]] = i;
  
  fin = fopen( "robotel.in", "r" );
  fscanf( fin, "%d%d%d", &p, &r, &k );
  for ( l = 0; l <= r+1; l++ ) // bordam marginile
    per[l][0] = per[0][l] = per[l][r+1] = per[r+1][l] = BORD;
  for ( i = 0; i < k; i++ ) {
    fscanf( fin, "%d%d ", &l, &c ); // linia si coloana semnalizatorului
    tab[l][c] = fgetc( fin );       // memoram semnalizatorul pe tabla
  }
  fclose( fin );

  // cerinta 1: determina perechile blocante in per[][]
  for ( l = 1; l <= r; l++ ) {
    ue = 0;
    for ( c = 1; c <= r; c++ )
      if ( tab[l][c] > 0 ) {
        if ( tab[l][c] == 'V' && ue > 0 )   // stocam perechea blocanta
          per[l][ue] = per[l][c] = c - ue;  // c - ue patrate spre est/vest
        else if ( tab[l][c] == 'N' && us[c] > 0 ) // stocam perechea bloc.
          per[us[c]][c] = per[l][c] = l - us[c];// l - us patrate spre sud/nord
        ue = ecoef[dir[tab[l][c]]] * c;    // memoram coloana ultimului 'E'
        us[c] = scoef[dir[tab[l][c]]] * l; // memoram linia ultimului 'S'
      }
  }

  fout = fopen( "robotel.out", "w" );
  if ( p == 1 ) { // afisam perechile blocante
    p = 0;        // nu am afisat nici o pereche inca
    for ( l = 1; l <= r; l++ ) {
      for ( c = 1; c <= r; c++ )
        if ( per[l][c] > 0 ) { // avem o pereche blocanta
          p = 1; // avem perechi blocante
          if ( tab[l][c] == 'E' )
            fprintf( fout, "%d %d %d %d\n", l, c, l, c + per[l][c] );
          else if ( tab[l][c] == 'S' )
            fprintf( fout, "%d %d %d %d\n", l, c, l + per[l][c], c );
        }
    }
    if ( p == 0 )            // daca nu am afisat nici o pereche blocanta
      fprintf( fout, "0\n" ); // afiseaza '0'
  } else {     // cerinta 2: simulam deplasarea robotului
    l = c = 1; // pozitia initiala a robotului
    d = E;     // directia initiala a robotului
    while ( per[l][c] == 0 ) { // nu am ajuns in punct de final
      if ( tab[l][c] > 0 )     // daca e nevoie sa schimbam directia
        d = dir[tab[l][c]];    // o schimbam
      l += dl[d];              // avansam
      c += dc[d];
      drum[d]++; // am mers inca o casuta in directia d
    }

    if ( per[l][c] == BORD ) // am iesit de pe tabla
      drum[d]--;             // iesirea din tabla nu se pune
    else                     // am ajuns la o pereche blocanta
      drum[dir[tab[l][c]]] += per[l][c]; // adunam drumul pina la casuta opusa

    fprintf( fout, "%d", drum[0] );
    for ( d = 1; d < 4; d++ )
      fprintf( fout, " %d", drum[d] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Problema sume1

Comentarii generale

  • Problemă rezolvată de aproape toată lumea, bun!
  • Ați găsit soluții diverse, interesant.
  • Unii din voi ați folosit o matrice.
  • Unii ați scris mult cod, alții puțin.
  • Problema se putea rezolva în 16 linii reale (fără linii goale) și fără vectori sau matrice. Nu cred că am văzut nici o soluție atît de scurtă, dar am văzut cîteva soluții apropiate (Calotă, Ipate, Voicu, Ilie, poate și alții).
  • Teodorescu cîștigă lupta pentru cea mai lungă sursă, circa 75 linii. Pe locul doi sînt Iordache și Togan cu aproximativ 50 de linii.

Rezolvare

Problema sume1 a fost dată la ONI 2004, clasa a 8a. Ea este o problemă de logică și matematică, în care trebuie să găsiți regula de așezare a numerelor de la 1 la n2 într-un pătrat astfel încît sumele pe linii să fie aceleași.

Problema poate părea grea la prima vedere. Ce de obicei, studierea exemplului din enunț cu hîrtie și creion ajută foarte mult. Vom aplica următoarele principii cunoscute:

  • Matematica duce la o soluție mai bună.
  • Introducerea unei ordini ajută.

Deoarece ordinea elementelor în linie nu contează și nici ordinea liniilor, să introducem o ordine: să ordonăm elementele fiecărei linii din exemplu și apoi să ordonăm liniile. Vom obține:

1 6 11 16

2  7 12 13
3  8  9 14
4  5 10 15

Regula devine, astfel, evidentă: numerele vor fi completate pe coloană, avînd grijă să rotim coloanele în sus cînd avansăm la o nouă coloană.

În fapt, elementele matricei au o regulă matematică relativ simplă. Putem deduce acea regulă în doi pași:

  1. În primă fază putem considera matricea ca fiind completată pe coloane, fără rotații:
    1  5  9 13
    2  6 10 14
    3  7 11 15
    4  8 12 16
    Regula unui element este ușor de observat: El,c = c·n + l + 1 (considerînd liniile și coloanele numerotare de la zero).
  2. În faza a doua trebuie să ținem cont de rotație. Ea va adăuga la fiecare element valoarea l % n pentru coloana zero, (l + 1) % n pentru coloana 1, (l + 2) % n pentru coloana 2, și așa mai departe. Formula finală va fi, deci: El,c = 1 + c·n + (l + c) % n

Iată o soluție posibilă (20 linii de cod):

#include <stdio.h>

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

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

  fout = fopen( "sume1.out", "w" );
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      fprintf( fout, "%d ", 1 + c * n + (l + c) % n );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

În mod evident O(n2) ca timp și O(1) ca memorie.

Problema popas

Comentarii generale

  • Problema poate fi muncitorească, în funcție de cum o abordați.
  • Cam jumate din voi nu ați reușit să treceți toate testele.
  • Mulți dintre voi ați scris un cod încîlcit, cu stegulețe.
  • Cu toate acestea codul multora din voi arată atenție cazurile posibile și o anumită ordine în gîndire. Bravo!

Rezolvare

Problema popas a fost dată la OJI 2004, clasa a 8a. Ea este o problemă relativ simplă, dar cu o dificultate destul de mare la implementare deoarece există multe puncte unde putem greși.

Rezolvarea presupune:

  • Sortarea crescătoare a tuturor izvoarelor traseelor (preferabil cu vectori de frecvență).
  • Parcurgerea tuturor traseelor calculînd numărul de popasuri minim necesar.

Modalități de parcurgere a unui izvor - precum am mai discutat, putem avea două abordări în parcurgerea unui traseu. Acest lucru se întîmplă cînd căutăm subsecvențe într-o secvență. În cazul nostru căutăm subsecvențe de drum fără popas. Astfel, avem două posibilități, putînd folosi:

  • O buclă exterioară și una interioară (vezi prima soluție prezentată).
  • O buclă exterioară și un test (if) interior (vezi a doua soluție).

Ambele variante sînt la fel de bune. În general recomand varianta a doua, ea ducînd la un cod mai simplu.

Atenție la următoarele greșeli:

  • Enunțul nu interzice mai multe izvoare în același loc.
  • Izvoarele nu sînt date în ordinea distanței.
  • Dacă sortăm izvoarele folosind un vector de frecvență (cum este cel mai rapid și mai simplu, eliminînd și duplicatele) trebuie să avem grijă să resetăm la zero vectorul de frecvență înaintea fiecărei sortări.
  • Enunțul specifică faptul că trebuie să ajungem pînă pe culme, la un km de ultimul izvor. Trebuie deci introdus un izvor fals la final.

Iată o soluție posibilă ce memorează traseele ca distanțe ordonate ale izvoarelor (73 linii de cod):

#include <stdio.h>

#define MAX_TRASEE 100
#define MAX_IZVOARE 20
#define MAX_DIST 360

int nt[MAX_TRASEE];
int r[MAX_TRASEE];
int dist[MAX_TRASEE][MAX_IZVOARE + 2]; // + culmea + santinela (element zero)
char frecv[MAX_DIST + 1];

int main() {
  FILE *fin, *fout;
  int k, l, c, d, t, u, popmin, tmin, nrpop, pop;

  fin = fopen( "popas.in", "r" );
  fscanf( fin, "%d", &k );
  for ( l = 0; l < k; l++ ) {
    fscanf( fin, "%d%d", &nt[l], &r[l] ); // nr traseu si nr izvoare
    // resetam la zero distantele izvoarelor
    for ( d = 1; d <= MAX_DIST; d++ )
      frecv[d] = 0;
    // construim vectorul de frecventa al distantelor - pentru sortare
    for ( c = 0; c < r[l]; c++ ) {
      fscanf( fin, "%d", &d );
      frecv[d] = 1;
    }
    // sortam distantele si le depunem in dist[l]
    r[l] = 1; // recalculam numarul de izvoare, ele se pot suprapune
    for ( d = 1; d <= MAX_DIST; d++ )
      if ( frecv[d] > 0 ) {
        dist[l][r[l]] = d;
        r[l]++;
      }
    dist[l][r[l]] = dist[l][r[l] - 1] + 1; // adaugam si culmea
  }
  fscanf( fin, "%d%d", &t, &u ); // cit dureaza termosul, cit merge fara apa
  fclose( fin );

  t += u; // ne intereseaza cit pot merge maxim, deci suma t + u
  // parcurgem fiecare traseu, de la coada la cap, cautind minimul de umpleri
  popmin = MAX_IZVOARE + 1; // numarul minim de popasuri
  tmin = -1;                // numarul traseului minim
  for ( l = k - 1; l >= 0; l-- ) { // vrem ultimul traseu, parcurgem invers
    // parcurgem traseul l si calculam cite popasuri sint necesare
    c = 1;     // pornim cu primul izvor
    u = 0;     // kilometrul ultimei umpleri de termos
    nrpop = 0; // numarul de popasuri
    do {
      pop = u; // tinem minte ultima umplere
      while ( c <= r[l] &&          // cita vreme mai avem izvoare pe traseul l
              dist[l][c] - u <= t ) // si pot ajunge la izvorul al c-ulea
        c++;                        // avansam izvorul
      nrpop++;              // inca un popas
      u = dist[l][c - 1];   // mutam ultima alimentare in izvorul anterior, c-1
    } while ( c <= r[l]     // cita vreme mai avem izvoare
              && u > pop ); // si la pasul anterior am avansat macar un izvor
    if ( c > r[l] &&        // daca am ajuns pe culme
         nrpop < popmin ) { // si daca numarul de popasuri este mai mic
      popmin = nrpop;       // retinem numarul de popasuri al traseului l
      tmin = nt[l];         // si numarul traseului l
    }
  }

  fout = fopen( "popas.out", "w" );
  if ( tmin > 0 )
    fprintf( fout, "%d %d\n", popmin - 1, tmin );
  else
    fprintf( fout, "0\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Este ușor de văzut că ea este O(k·(r + max(di)). Memoria folosită este circa 10000 octeți.

Iată o altă soluție posibilă ce memorează traseele ca vectori de frecvență ale distanțelor izvoarelor (68 linii de cod):

#include <stdio.h>

#define MAX_TRASEE 100
#define MAX_IZVOARE 20
#define MAX_DIST 360

int nt[MAX_TRASEE];
char dist[MAX_TRASEE][MAX_DIST + 2]; // culmea e la un km de la ultimul izvor

int main() {
  FILE *fin, *fout;
  int k, l, d, t, u, pmin, tmin, np, max;

  fin = fopen( "popas.in", "r" );
  fscanf( fin, "%d", &k );
  for ( l = 0; l < k; l++ ) {
    fscanf( fin, "%d%d", &nt[l], &np ); // nr traseu si nr izvoare
    // citim izvoarele intr-un vector de frecventa al distantelor
    max = 0;
    for ( u = 0; u < np; u++ ) {
      fscanf( fin, "%d", &d );
      dist[l][d] = 1; // la kilometrul d avem izvor pe traseul l
      if ( d > max )  // retinem ultimul izvor in max
        max = d;
    }
    dist[l][max + 1] = 2;        // marcam cu 2 culmea in vectorul de frecventa
  }
  fscanf( fin, "%d%d", &t, &u ); // cit dureaza termosul, cit merge fara apa
  fclose( fin );

  t += u; // ne intereseaza cit pot merge maxim, deci suma t + u
  // parcurgem fiecare traseu, de la coada la cap, cautind minimul de umpleri
  pmin = MAX_IZVOARE + 1; // numarul minim de popasuri
  tmin = -1;              // numarul traseului minim
  for ( l = k - 1; l >= 0; l-- ) { // vrem ultimul traseu, parcurgem invers
    // parcurgem traseul l si calculam cite popasuri sint necesare
    d = 1;   // pornim de la inceput
    max = t; // cati km pot merge cu termosul
    np = 0;  // numarul de popasuri
    u = 0;   // ultimul izvor intilnit
    while ( dist[l][d] < 2   // cita vreme nu am ajuns pe culme
            && max > 0 ) {   // si mai avem apa in termos
      if ( dist[l][d] == 1 ) // la kilometrul d avem izvor?
        u = d;               // retinem ultimul izvor intilnit
      max--;                 // termosul se goleste
      if ( max == 0 ) {      // s-a golit termosul, cautam ultimul izvor
        max = t - (d - u);   // umplem cu t, dar am consumat deja d - u
        np++;                // am mai facut un popas
      }
      d++;                   // avansam un km
    }

    if ( dist[l][d] == 2 &&  // daca am ajuns pe culme
         np < pmin ) {       // si daca numarul de popasuri este mai mic
      pmin = np;             // retinem numarul de popasuri al traseului l
      tmin = nt[l];          // si numarul traseului l
    }
  }

  fout = fopen( "popas.out", "w" );
  if ( tmin > 0 )
    fprintf( fout, "%d %d\n", pmin, tmin );
  else
    fprintf( fout, "0\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Și ea este tot O(k·(r + max(di)). Memoria folosită este ceva mai mare, circa 36600 octeți.

Problema reconstituire2

Comentarii generale

  • Marea majoritate nu doar ați rezolvat problema, ci ați luat 100p, felicitări!
  • Cei ce nu au luat 100p sînt cei ce nu au încercat: Rughiniș, Iordache, Cojocariu, Nicola, care nu au trimis nici o sursă, plus alți doi sau trei nefericiți care au reușit cumva să ia zero puncte.
  • Foarte puțini dintre voi ați pus corect condiția de oprire, ca prima poziție unde vectorii de frecvență diferă să fie în afara vectorilor (i >= 10)
  • Ceilalți, majoritatea, vă refugiați prea ușor în brațele stegulețelor. Ele duc la o lene a minții și la o gîndire încîlcită, încercați să le evitați. Aici nu erau necesare. Cine: Ștefănescu, Ipate, Cadîr, Stancu, Burac, Togan, Petcu, Marcu, Grecu, Tatomir, Teodorescu, Chivu, Nicu, Badea, Dobre, Asgari (care a mai și scris o căutare ineficientă), Fares (care nu a folosit stegulețe, dar nici nu s-a oprit la rezultat, urît).
  • Nu am văzut la voi încercări de a elimina codul asemănător. Factorizați vă rog!
  • Problema are o rezolvare elegantă de circa 35 de linii.
  • Vă rog nu scrieți cod așa:
        for ( nr = i; nr > 0; nr /= 10 )
           fp[nr%10]++;

Bucla nu are număr cunoscut de pași, corect era să folosim while (Calotă).

  • Unii din voi introduceți cazuri particulare în algoritm, care nu există. Astfel obțineți un program lung și predispus bugurilor. Acest lucru se întîmplă deoarece vă aruncați în programare cu o idee neclară; apoi, pe măsură ce observați probleme în abordare, peticiți codul. Foarte rău! Pentru a scăpa de aceast mod de lucru trebuie să vă faceți cazuri de test pe hîrtie și să clarificați algoritmul înainte de a intra în Code::Blocks. Am remarcat acest lucru la Petcu, Togan și Tatomir, dar mai sînt și alții.

Rezolvare

Problema reconstituire2 este o problemă relativ simplă. Dificultatea ei constă, după părerea mea, tocmai în simplitatea soluției. La prima vedere sîntem tentați să căutăm o soluție matematică. Matematica ajută pentru optimizarea soluției, dar, în mod neașteptat, o soluție directă se încadrează în timp.

Anume, observăm că dacă avem un vector de frecvență al numerelor de la P la P + K - 1, atunci putem calcula relativ ușor vectorul de frecvență al numerelor de la P + 1 la P + K: tot ce avem de făcut este să scădem din vectorul de frecvență cifrele lui P și să adăugăm cifrele lui P + K.

Astfel, un algoritm simplu este:

  1. Citește de la intrare K și vectorul de frecvență al cifrelor, F1
  2. Pentru fiecare "fereastră" de K numere consecutive:
    1. Calculează vectorul de frecvență F2 al cifrelor numerelor din fereastră
  3. Oprește-te atunci cînd F1 == F2, element cu element

O soluție elegantă va adăuga detalii de implementare:

  • Va folosi un singur vector de frecvență.
  • Nu va repeta cod pentru comparația vectorilor.
  • Nu va repeta cod pentru scăderea primului număr din fereastră și adunarea ultimului număr din fereastră.
  • Va folosi o santinelă pentru comparația vectorului de frecvență cu zero.

Iată o soluție posibilă (37 linii de cod):

#include <stdio.h>

int f[11];

int main() {
  FILE *fin, *fout;
  int k, p, cp, i, s;

  fin = fopen( "reconstituire2.in", "r" );
  fscanf( fin, "%d", &k );
  for ( p = 0; p < 10; p++ )
    fscanf( fin, "%d", &f[p] );
  fclose( fin );

  f[10] = 1;  // santinela
  p = -k + 1; // pornim cu fereastra -k+1 .. 0
  do { // adunam cifrele lui p si scadem cifrele lui p + k
    for ( i = 0; i < 2; i++ )
      if ( (cp = p + i * k) > 0 ) { // daca cp nu este negativ, il adunam
        s = 1 - 2 * i;     // s = -1 sau 1, daca adunam sau scadem cifrele
        while ( cp > 0 ) {
          f[cp % 10] += s;
          cp /= 10;
        }
      }
    p++;
    i = 0;
    while ( f[i] == 0 )
      i++;
  } while ( i < 10 );
  
  fout = fopen( "reconstituire2.out", "w" );
  fprintf( fout, "%d\n", p );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Deoarece numerele au cel mult șase cifre și deoarece la fiecare iterație vom parcurge cifrele a două astfel de numere, vom avea O(log MAXN) operații per iterație. Tot la fiecare iterație vom compara un vector de 10 elemente cu zero, deci O(Σ) operații. De cîte ori se poate executa bucla? De maxim MAXN ori. Deci, complexitatea totală este de O(MAXN·(log MAXN + Σ)). Înlocuind cu valori maxime (MAXN este maxim un milion) obținem circa 6 milioane de împărțiri și 10 milioane de comparații, ceea ce înseamnă cam 200 milioane de operații.

Soluția pare la limită, timpul fiind de 0.3s. Dar să nu uităm că memoria folosită este ca și zero, anume O(Σ). În aceste cazuri numărul de operații pe secundă crește foarte mult, de pînă la zece ori și de aceea, în realitate, soluția se încadrează lejer în timp.

Soluția poate fi optimizată: putem evita împărțirile dacă lucrăm cu numere mari.

Rezolvări aici: [1]

Lecție

Am discutat despre problemele de la temă.

Acesta este filmul lecției de dimineață:

Deoarece bateria camerei de filmat s-a terminat înainte de finalul de lecție am filmat ultima parte a lecției de după amiază:

Problema descmult

Problema descmult este foarte grea pentru clasa a 6a. Ea are o parte de matematică care duce la rezultate neașteptate și o soluție foarte rapidă. În același timp problema admite mai multe soluții care se încadrează în timp, deoarece timpul este destul de mare.

Nu v-am dat această problemă în timpul unui concurs, ci la temă, deoarece aș vrea să încercați să găsiți o soluție cît mai bună.

Atenție: sursele oficiale nu sînt neapărat optime, nu încercați să le copiați ideea.

Temă

Tema 33 clasa a 6a

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

Concurs clasa a 6a

Acest concurs este ultimul înainte de olimpiada națională. De aceea el va avea același mod de desfășurare: nu veţi putea vedea rezultatele evaluării surselor trimise decît după încheierea concursului. Puteţi trimite oricîte surse, fără penalizare, însă doar ultima sursă trimisă la o problemă se ia în considerare pentru acea problemă.

Rezolvări aici: [2]