Difference between revisions of "Clasa a V-a lecția 28 - 22 feb 2020"

From Algopedia
Jump to navigationJump to search
 
(No difference)

Latest revision as of 08:53, 23 February 2020

Concurs - rezolvări

Problema triunghiurile de 5 bani

Problema triunghiurile de 5 bani a fost dată la olimpiada locală 2016 clasa a 5a. Ea cere, la bază, să se calculeze numărul de monede din n grămezi triunghiulare, aceasta fiind principalul calcul.

Sper că la nivelul la care ați ajuns pînă acum problema vi se pare ușoară. Singura ei dificultate constă în faptul că primul rezultat poate depăși tipul int. Să vedem două soluții, pe scurt.

Soluția unu - de clasa a 5a

Este, sper, destul de ușor de observat că fiecare triunghi se poate obține din triunghiul anterior adăugînd un rînd de monede. Mai mult, numărul de monede din acel rînd este egal chiar cu numărul triunghiului! Drept care rezultă imediat că fiecare triunghi este o sumă a lui Gauss. Cu alte cuvinte, numărul total de monede va fi:

s = gauss(1) + gauss(2) + ... + gauss(n) + n

Observați că am adăugat la final numărul n, conform enunțului.

Din acest moment problema devine strict una de calcul. O soluție posibilă pe baza acestor idei este:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i;
  long long s, x, y;

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

  // s = n + gauss(1) + gauss(2) + ... + gauss(n)
  s = n; // numarul de monede de 5 bani
  for ( i = 1; i <= n; i++ )
    s += i * (i + 1) / 2;
  x = s * 5;   // numarul de bani
  y = x % 100; // valoarea banilor ramasi
  x = x / 100; // citi lei intregi avem
  
  fout = fopen( "triunghiuri.out", "w" );
  fprintf( fout, "%lld %lld\n", x, y );
  fclose( fout );

  return 0;
}

Soluția doi - la nivel matematic peste clasa a 5a

Precum știm, un bun informatician este în mod necesar și un bun matematician. Iar un bun matematician se va uita la calculul folosit în această problemă:

s = gauss(1) + gauss(2) + ... + gauss(n) + n

și se va întreba 'oare dacă există o formulă pentru suma lui Gauss, oare nu există o formulă și pentru suma sumelor lui Gauss'. Apoi, va lua o hîrtie și un creion, își va sufleca mînecile și va porni la lucru :-) Să vedem ce va scrie el.

s = 1·2/2 + 2·3/2 + ... + n·(n+1)/2

Putem factoriza împărțirea la doi:

s = [1·2 + 2·3 + ... + n·(n+1)] / 2

Apoi vom scrie numerele astfel încît să ajungem la o sumă de pătrate:

s = [1·1+1 + 2·2+2 + 3·3+3 + ... + n·n+n] / 2

adică

s = [(12 + 22 + 32 + ... + n2) + (1 + 2 + 3 + ... + n)] / 2

Interesant! Am ajuns la două sume simpatice. Pe una din ele, cea din dreapta, o știm, este suma lui Gauss. Prima este o sumă similară cu cea a lui Gauss, doar că însumăm pătratele numerelor. Această a doua sumă este o cunoștință de nivel matematic ce depășește clasa a cincea (cred că se predă cu demonstrație abia prin clasa a noua). De aceea o vom lua ca atare:

12 + 22 + 32 + ... + n2 = n·(n+1)·(2n+1)/6

Dacă înlocuim cele două sume în formula de mai sus obținem:

s = [n·(n+1)·(2n+1)/6 + n·(n+1)/2] / 2

Aducem fracțiile la același numitor și obținem

s = [n·(n+1)·(2n+1)/6 + 3·n·(n+1)/6] / 2
s = [n·(n+1)·(2n+1) + 3·n·(n+1)] / 12

Dăm factor comun n·(n+1) și obținem

s = n·(n+1)·[(2n+1) + 3] / 12
s = n·(n+1)·(2n+4) / 12

Simplificăm cu doi:

s = n·(n+1)·(n+2) / 6

Și iată că am obținut formula finală a sumei sumelor lui Gauss.

În concluzie numărul de monezi se poate calcula cu o formulă relativ simplă și anume:

s = n * (n + 1) * (n + 2) / 6 + n;

Ingenios, nu-i așa? Modificînd programul anterior vom obține:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  long long n, s, x, y;

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

  // n = gauss(1) + gauss(2) + ... + gauss(n) + n                               
  s = n * (n + 1) * (n + 2) / 6 + n; // numarul de monede de 5 bani             
  x = s * 5;   // numarul de bani                                               
  y = x % 100; // valoarea banilor ramasi                                       
  x = x / 100; // citi lei intregi avem                                         

  fout = fopen( "triunghiuri.out", "w" );
  fprintf( fout, "%lld %lld\n", x, y );
  fclose( fout );

  return 0;
}

Elegant, nu-i așa?

Întrebare:

  • Dat fiind că valoarea variabilei n este maxim 10000, poate ea fi de tip int în acest program? De ce?

Problema cifre8

Problema cifre8 a fost dată la olimpiada locală 2016 clasa a 5a. Ea cere să se calculeze două proprietăți ale produsului a n numere, și anume: cîte cifre zero are el la final și care este ultima lui cifră diferită de zero.

Această problemă este una simplă matematic: efectuăm produsul și apoi numărăm zerourile de la coadă. Greutatea ei constă, din nou, în faptul că produsul a 100 de numere nu va încăpea într-o variabilă întreagă. Se pare că la olimpiada locală din 2016 a fost la mare preț înțelegerea ideii de depășire întreagă, mai curînd decît algoritmica :-)

Desigur, așa cum ne-am obișnuit, rezolvarea acestei probleme necesită cunoștințe de matematică superioare, dincolo de clasa a 5a. Mai exact, lucrul cu clase de resturi (grupuri, inele și corpuri) se predă în clasa a 12a, din cîte știu. Aceasta ne silește să știm, în avans, unele proprietăți ale operațiilor cu rest, care pot părea magie în clasa a cincea :-)

Am putea fi tentați să încercăm diverse metode incorecte:

  • Să calculăm produsul folosind o variabilă tip int. Această soluție va lua 20p.
  • Să calculăm produsul folosind o variabilă tip long long. Această soluție va lua 30p.
  • Să calculăm produsul și la fiecare înmulțire să îl împărțim la zece de cîte ori se poate, contorizînd zerourile. Această soluție va lua 40p. Este incorectă deoarece dacă nu avem zerouri multe vom depăși rapid întregul.
  • Să procedăm ca la soluția anterioară, dar împărțind fiecare număr la zece de cîte ori se poate înainte de a-l înmulți. Această soluție va lua 50p.

Să vedem acum o soluție corectă.

Numărul de zerouri de la coada produsului

Să începem cu prima parte a problemei: cum putem afla cu cîte zerouri se termină un produs de numere? Este destul de clar că dacă un număr se împarte la 10, atunci el se împarte și la divizorii lui, 2 și 5. Invers, dacă un număr se împarte la 2 și la 5 el se va împărți și la 10. Dacă un număr se împarte la 2 de p2 ori și la 5 de p5 ori, de cîte ori se va împărți el la 10? Fiecare 10 necesită o pereche de 2 și 5. Cîte perechi putem forma? Putem forma minimul dintre p2 și p5 perechi.

Putem deci contoriza de cîte ori se împarte fiecare număr al produsului la 2 și la 5. Minimul dintre aceste două va fi numărul de zerouri de la finalul numărului, căci de atîtea ori se va împărți la 10.

Ultima cifră nenulă

Care va fi ultima cifră nenulă a numărului? Este cifra care rămîne dacă am împărți numărul la 10 de atîtea ori cîte zerouri are în coadă, adică numărul calculat anterior. Dar nu putem face acest calcul direct, deoarece din nou vom depăși întregul. Ceea ce putem face este să împărțim numerele de la intrare la 2 și la 5 de cîte ori se poate, contorizînd împărțirile. Numărul rămas se va înmulți la produsul general. Deoarece avem nevoie doar de ultima cifră, vom opera doar cu cifre, înmulțind produsul cu ultima cifră a numărului rămas și apoi păstrînd doar ultima cifră a rezultatului.

La final vom obține o cifră. Este ea răspunsul? Nu încă! Noi am "curățat" produsul de orice 2 sau 5. Deoarece ele nu vor fi în număr egal, după ce "curățăm" zeciurile, adică perechi de 2 și 5, vom rămîne fie cu 2, fie cu 5 care trebuie readăugați la produs. Drept care vom face o ultimă înmulțire cu 2 sau 5 avînd grijă să păstrăm mereu ultima cifră.

Iată un program posibil:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, e, nr2, nr5, nr0, p;

  fin = fopen( "cifre8.in", "r" );
  fscanf( fin, "%d", &n );
  nr2 = nr5 = 0;
  p = 1;
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &e );
    // aflam de cite ori se imparte la 2 si la 5 si impartim la 2 si 5
    while ( e % 2 == 0 ) {
      e /= 2;
      nr2++;
    }
    while ( e % 5 == 0 ) {
      e /= 5;
      nr5++;
    }
    p = e % 10 * p % 10; // inmultim ultima cifra la produsul global
  }
  fclose( fin );

  if ( nr2 < nr5 ) {
    nr0 = nr2;
    for ( nr5 -= nr2; nr5 > 0; nr5-- )
      p = p * 5 % 10;
  } else {
    nr0 = nr5;
    for ( nr2 -= nr5; nr2 > 0; nr2-- )
      p = p * 2 % 10;
  }
  
  fout = fopen( "cifre8.out", "w" );
  fprintf( fout, "%d %d\n", nr0, p );
  fclose( fout );

  return 0;
}

Putem optimiza această soluție dacă observăm că nu trebuie să înmulțim toate 2 sau 5 rămase pentru a afla ultima cifră, dar nu vom discuta aici această optimizare, luați-o ca temă de gîndire.


Tema - rezolvări

Problema minnr

Problema minnr este foarte similară cu problema maxnr, doar că de data aceasta vom afișa cifrele în ordinea lor crescătoare. Trebuie să avem însă grijă deoarece nu putem să începem cu cifra 0! De aceea vom afișa mai întîi cea mai mică cifră diferită de zero din vectorul de frecvență. Apoi vom scădea unu de la acea poziție, ca să știm că am afișat-o. Abia apoi putem trece la afișarea întregului vector de la mic la mare fără să ne mai pese de cifrele 0. Iată o soluție posibilă:

#include <stdio.h>

int v[10];

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

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

  while ( n > 0 ) {
    cf = n % 10;
    v[cf]++;
    n = n / 10;
  }

  fout = fopen( "minnr.out", "w" );
  // cauta cea mai mica cifra diferita de zero
  cf = 1;
  while ( v[cf] == 0 )
    cf++;
  fprintf( fin, "%d", cf ); // afiseaza prima cifra
  v[cf]--;                  // scoate-o din numar

  // afiseaza restul cifrelor, in ordine crescatoare
  for ( cf = 0; cf < 10; cf++ )
    while ( v[cf] > 0 ) {
      fprintf( fout, "%d", cf );
      v[cf]--;
    }
  fclose( fout );

  return 0;
}


Problema cifre 3

Problema cifre 3 este un alt exemplu de problemă ce se rezolvă mai uşor folosind vectori de frecvenţă. Punctul a) al problemei se rezolvă ca problema cfdist. Vom afișa cifrele care apar în vectorul de frecvență al lui a și nu apar în vectorul de frecvență al lui b. Punctul b) se rezolvă afișînd în ordine descrescătoare cifrele care apar în ambii vectori de frecvență.

#include <stdio.h>

int v[10], w[10];

int main() {
  FILE *in, *out;
  int a, b, ca, cb, cf, afisat;

  in = fopen( "cifre3.in", "r" );
  fscanf( in, "%d%d", &a, &b );
  fclose( in );

  // calculam vectorul de frecventa al cifrelor lui a
  ca = a;
  while ( ca > 0 ) {
    cf = ca % 10;
    v[cf] = 1;
    ca = ca / 10;
  }

  // calculam vectorul de frecventa al cifrelor lui b
  cb = b;
  while ( cb > 0 ) {
    cf = cb % 10;
    w[cf] = 1;
    cb = cb / 10;
  }

  // punctul a, afisam cifrele care apar in a si nu in b
  out = fopen( "cifre3.out", "w" );
  afisat = 0;
  for ( cf = 0; cf < 10; cf++ )
    if ( v[cf] == 1 && w[cf] == 0 ) { // daca cifra apare in a dar nu in b
      fprintf( out, "%d ", cf );      // o afisam
      afisat = 1;                     // marcam ca am afisat ceva
    }
  if ( afisat == 0 )      // daca nu am afisat nimic
    fprintf( out, "-1" ); // afisam -1
  fprintf( out, "\n" );

  // punctul b, afisam cel mai mare numar care se poate forma cu cifrele
  // distincte comune
  // vom afisa toate cifrele comune, in ordine inversa
  afisat = 0;
  for ( cf = 9; cf >= 0; cf-- )
    if ( v[cf] == 1 && w[cf] == 1 ) { // daca cifra apare si in a si in b
      fprintf( out, "%d", cf );       // o afisam
      afisat = 1;                     // marcam ca am afisat ceva
    }
  if ( afisat == 0 )      // daca nu am afisat nimic
    fprintf( out, "-1" ); // afisam -1
  fprintf( out, "\n" );
  fclose( out );

  return 0;
}

Problema compus

Problema compus vă trece prin cîteva operații elementare cu vectori.

Iată o soluție posibilă:

#include <stdio.h>

int v[10000];

int main() {
  FILE *fin, *fout;
  int n, e, p, i, j, aux;

  fin = fopen( "compus.in", "r" );
  fscanf( fin, "%d%d%d", &n, &e, &p );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  // cautare elemente e
  i = 0;
  while ( v[i] != e )
    i++;

  // eliminare element pe pozitia i: mutam spre stinga elementele dupa i
  for ( j = i + 1; j < n; j++ )
    v[j-1] = v[j];
  n--; // nu uitati sa scadeti n, numarul de elemente este mai mic cu unu acum

  // adaugare element e pe pozitia p: mutam spre dreapta elementele dupa p
  for ( j = n - 1; j >= p; j-- )
    v[j+1] = v[j];
  v[p] = e;
  n++; // avem un element in plus acum

  // rasturnare vector
  i = 0;
  j = n - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }

  // rotire spre stinga cu o pozitie
  aux = v[0];
  for ( i = 1; i < n; i++ )
    v[i-1] = v[i];
  v[n-1] = aux;

  fout = fopen( "compus.out", "w" );
  for ( i = 0; i < n; i++ )
    fprintf( fout, "%d ", v[i] );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Problema felinare

Problema felinare a fost dată la ONI 2008 clasa a 5a. Ea admite două soluții, una pur informatică și una matematică.

Prima soluție și cea mai directă este să simulăm aprinderea și stingerea felinarelor pînă ce toate felinarele sînt din nou aprinse. Pentru aceasta vom parcurge vectorul cu doi indici consecutivi, i și i1, astfel încît i1 este în fața lui i cu o poziție. La fiecare pas i devine i1, iar i1 devine (i1+1)%n.

Cum calculăm noua valoare a felinarului? Modul direct este cu teste:

if ( f[i] == 1 ) {
  if ( f[i1] == 1 ) {
    f[i1] = 0;
    aprinse = aprinse - 1;
  } else {
    f[i1] = 1;
    aprinse = aprinse + 1;
  }
}

Această secvență de program actualizează atît felinarul pe poziția i1 cît și numărul de felinare aprinse la momentul curent. O altă soluție mai scurtă este să găsim o formulă de calcul a felinarului pe poziția i1. De asemenea putem găsi o formulă de calcul și pentru numărul de felinare aprinse. Iată varianta cu formule:

v = (f[i] + f[i1]) % 2;          // calculam noua valoare a felinarului f[i1]
aprinse = aprinse + v - f[i1];   // calculam cite felinare sint aprinse
f[i1] = v;                       // stocam noua valoare a felinarului in vector

Observați formulele și încercați să înțelegeți de ce sînt corecte.

Ca ultimă observație: numărul de felinare aprinse la un moment dat poate fi calculat ca suma elementelor din vector. Această metodă este foarte ineficientă. Este preferabil să adunăm sau să scădem 1 din variabila aprinse atunci cînd se modifică starea unui felinar.

Iată soluția completă bazată pe aceste idei:

#include <stdio.h>

int f[5000];

int main() {
  FILE *fin, *fout;
  int n, nrop, aprinse, i, i1, v;

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

  f[0] = 0;                 // primul felinar este 0
  for ( i = 1; i < n; i++ ) // celelalte sint 1
    f[i] = 1;
  nrop = 1;                 // numarul de operatii efectuate este 1
  aprinse = n - 1;          // numarul de felinare aprinse este 1
  i = 0;                    // pornim de la felinarul 1 (dar ne uitam la 0)
  while ( aprinse < n ) {   // cita vreme nu avem n felinare aprinse
    i1 = (i + 1) % n;       // calculam indicele imediat urmator lui i
    v = (f[i] + f[i1]) % 2; // calculam noua valoare a felinarului f[i1]
    aprinse = aprinse + v - f[i1]; // calculam cite felinare sint aprinse
    f[i1] = v;              // stocam noua valoare a felinarului in vector
    nrop++;                 // am mai executat o operatie
    i = i1;                 // i devine urmatorul lui, adica i1
  }

  fout = fopen( "felinare.out", "w" );
  fprintf( fout, "%d", nrop );
  fclose( fout );

  return 0;
}

A doua soluție, cea matematică, se obține observînd regulile pentru numărul de pași necesari reaprinderii tuturor felinarelor. Știm din enunțul problemei că n poate fi de forma 2k sau 2k+1. Să calculăm numărul de pași pentru valori de acest tip:

k 2k nr. operații 2k+1 nr. operații
1 2 3 3 7
2 4 15 5 21
3 8 63 9 73

Din acest tabel se poate observa regula pe care o voi prezenta mai jos, fără a o demonstra:

Iată rezolvarea bazată pe această soluție:

#include <stdio.h>

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

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

  if ( n % 2 == 0 )
    nrop = n * n - 1;     // cind n este de forma 2^k
  else
    nrop = n * n - n + 1; // cind n este de forma 2^k + 1

  fout = fopen( "felinare.out", "w" );
  fprintf( fout, "%d", nrop );
  fclose( fout );

  return 0;
}

Atenție: această rezolvare obține numai 90p pe campion, deoarece primul test este greșit. În acest test n este 6, el nefiind de forma 2k sau 2k+1.

Problema culori1

Problema culori1 a fost dată la ONI 2012, clasa a 5a.

Pentru punctul a) vom compara fiecare element din vector cu cel din-naintea lui și cel de după el, avînd grijă că primul și ultimul copil sînt cazuri particulare. Pentru a nu îi trata special vom avansa indicele copiilor modulo n.

Pentru punctul b) vom considera toate secvențele de lungime k, le vom calcula vectorul de frecvență și apoi vom căuta maximul. Cel mai mare maxim este răspunsul căutat.

Iată soluția bazată pe aceste idei:

#include <stdio.h>

int v[1000], f[101];

int main() {
  FILE *fin, *fout;
  int n, i, j, k, lafel, max;

  fin = fopen( "culori1.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  lafel = 0; // inca nu am vazut nici un element cu vecini egali cu el
  max = 0;   // initializam maximul la o valoare mica
  for ( i = 0; i < n; i++ ) { // deplasam vecinii la dreapta de n ori
    // daca cele trei culori consecutive pornind la v[i] sint egale
    if ( v[i] == v[(i+1) % n] && v[(i+1) % n] == v[(i+2) % n] ) 
      lafel++;                // marim numarul de tripleti la fel

    // punctul b), calculam vectorul de frecventa si aflam maximul
    for ( j = 1; j < 101; j++ ) // intii il resetam la zero
      f[j] = 0;
    for ( j = 0; j < k; j++ ) // apoi il calculam
      f[v[(j + i) % n]]++;
    for ( j = 1; j < 101; j++ ) // actualizam maximul
      if ( f[j] > max )
        max = f[j];
  }

  fout = fopen( "culori1.out", "w" );
  fprintf( fout, "%d\n%d\n", lafel, max );
  fclose( fout );

  return 0;
}

Ca optimizare a acestei metode putem observa că vectorul de frecvență poate fi calculat incremental (din aproape în aproape) atunci cînd trecem de la o secvență de k copii la următoarea. Mai exact, putem scădea unu la elementul care iese din secvență și aduna unu la elementul care intră în secvență. Astfel nu mai trebuie să recalculăm întregul vector de frecvență pentru fiecare din secvențe. Maximul va fi calculat doar pe baza elementelor care intră în secvență, fiind singurele care cresc de la un pas la altul.

Iată programul optimizat:

#include <stdio.h>

int v[1000], f[101];

int main() {
  FILE *fin, *fout;
  int n, i, k, lafel, max;

  fin = fopen( "culori1.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  lafel = 0; // inca nu am vazut nici un element cu vecini egali cu el
  for ( i = 0; i < n; i++ ) { // deplasam vecinii la dreapta de n ori
    // daca cele trei culori consecutive pornind la v[i] sint egale
    if ( v[i] == v[(i+1) % n] && v[(i+1) % n] == v[(i+2) % n] ) 
      lafel++;                // marim numarul de tripleti la fel
  }

  // initializam vectorul de frecvente cu primele k
  for ( i = 0; i < k; i++ )
    f[v[i]]++;
  max = 0;
  for ( i = 0; i < n; i++ ) { // deplasam secventa de n ori
    // actualizeaza vectorul de frecventa pentru noua secventa
    f[v[i]]--;            // scadem elementul care iese din secventa
    f[v[(i + k) % n]]++;  // adunam elementul care intra
    if ( f[v[(i + k) % n]] > max ) // actualizam maximul, daca este cazul
      max = f[v[(i + k) % n]];
  }

  fout = fopen( "culori1.out", "w" );
  fprintf( fout, "%d\n%d\n", lafel, max );
  fclose( fout );

  return 0;
}

Observație avansată: Nu este necesar să aflăm maximul din primul vector de frecvență, primul calculat. Vă las ca temă să vă gîndiți de ce.

Tema opțională - rezolvări

Problema cifre comune

Problema cifre comune este relativ ușor de rezolvat folosind doi vectori de frecvență, cîte unul pentru fiecare număr, pe care îi vom construi în mod corespunzător, apoi îi vom compara element cu element, adunînd unu la contorul de cifre atunci cînd ambele elemente sînt diferite de zero. Vom încerca să rezolvăm problema cu extra credit :). Pentru aceasta vom construi vectorul de frecvență al primului număr, m. El va avea numai elemente zero și unu. Apoi vom extrage pe rînd cifrele lui n. Dacă ele apar în vectorul de frecvență vom face două lucruri: vom aduna unu la contorul de cifre comune și vom șterge acea cifră din vectorul de frecvență, setînd acel element pe zero, pentru ca în viitor să nu o mai luăm din nou în considerare dacă cifra apare de mai multe ori în n. Iată o rezolvare bazată pe aceste idei:

#include <stdio.h>

int v[10];

int main() {
  FILE *fin, *fout;
  int m, n, cf, nrcf;

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

  // setam 1 pentru cifrele lui m
  while ( m > 0 ) {
    cf = m % 10;
    v[cf] = 1;
    m = m / 10;
  }

  nrcf = 0;
  // testam cifrele lui n, resetind cifrele deja gasite, pentru a nu le
  // gasi de mai multe ori
  while ( n > 0 ) {
    cf = n % 10;
    if ( v[cf] == 1 ) {
      nrcf++;
      v[cf] = 0;
    }
    n = n / 10;
  }

  fout = fopen( "cfcomune.out", "w" );
  fprintf( fout, "%d", nrcf );
  fclose( fout );

  return 0;
}


Problema minnrk

Problema minnrk este foarte asemănătoare cu problema minnr. Există două diferențe:

  • Numărul poate fi foarte mare, avînd maxim 100 de cifre. De aceea nu putem citi n ca pe un întreg, ci îl vom citi ca pe un șir de caractere.
  • Nu vom folosi toate cele n cifre ale numărului, ci numai k dintre ele. De aceea bucla finală de afișare trebuie să se oprească după k cifre afișate.

În prima parte a rezolvării vom citi caractere pînă ce vom da de caracterul spațiu. Aceste caractere sînt cifre. Pentru a extrage valoarea lor vom scădea caracterul '0' din ele și cu noua valoare vom aduna unu la vectorul caracteristic. După caracterul spațiu putem citi valoarea lui k ca pe un întreg, deoarece k este mic.

În a doua parte a rezolvării, odată ce avem vectorul de frecvență calculat, trebuie sa afișam, ca la minnr, cea mai mică cifră nenulă. Pentru aceasta vom face o căutare în vectorul de frecvență a primului element diferit de zero. Atenție! Nu avem nevoie de nici un steguleț, cum au rezolvat unii din voi. Deoarece știm ca există cel puțin o cifră diferită de zero în n (pentru că n > 0), putem căuta pînă la găsirea unui element diferit de zero, astfel:

// cauta cea mai mica cifra diferita de zero
cf = 1;
while ( v[cf] == 0 )
  cf++;

Așa se face căutarea unui element în vector, nu cu steguleț, sau alte metode ciudate. Am mai discutat despre acest lucru, vă rog să vi-l însușiți.

Odată găsită cifra de afișat, o afișăm și scădem unu din elementul respectiv, întocmai ca la minnr.

În a treia parte a rezolvării vom afișa primele k-1 cifre din vectorul de frecvență, în ordine crescătoare. Mulți dintre voi s-au complicat și la această parte. O soluție simplă procedează astfel: pornim cu cifra cf = 0. Variem un contor de la 1 la k. La fiecare iterație vom căuta primul element din vectorul de frecvență, începînd cu cf, care este diferit de zero. Nu avem cum să ieșim din vector, căci știm că sînt minim k cifre disponibile. Odată găsit acel element, afișam poziția cf și scădem unu din valoarea elementului, astfel:

// afiseaza restul cifrelor, in ordine crescatoare
cf = 0;
for ( i = 1; i < k; i++ ) {
  while ( v[cf] == 0 ) // caută primul element mai mare ca zero
    cf++;
  fputc( cf + '0', fout );
  v[cf]--;
}

În final, bazat pe ideile de mai sus, obținem soluția următoare:

#include <stdio.h>

int v[10];

int main() {
  FILE *fin, *fout;
  int i, k;
  char cf;

  fin = fopen( "minnrk.in", "r" );
  cf = fgetc( fin );
  while ( cf != ' ' ) {
    v[cf - '0']++;
    cf = fgetc( fin );
  }
  fscanf( fin, "%d", &k );
  fclose( fin );

  fout = fopen( "minnrk.out", "w" );
  // cauta cea mai mica cifra diferita de zero
  cf = 1;
  while ( v[cf] == 0 )
    cf++;
  fputc( cf + '0', fin ); // afiseaza prima cifra
  v[cf]--;                // scoate-o din numar

  // afiseaza restul cifrelor, in ordine crescatoare
  cf = 0;
  for ( i = 1; i < k; i++ ) {
    while ( v[cf] == 0 )
      cf++;
    fputc( cf + '0', fout );
    v[cf]--;
  }
  fclose( fout );

  return 0;
}

Problema rotk

Problema rotk vă cere să faceți mai multe rotații multiple de vectori fără a face rotații repetate cu unu.

Pentru fiecare rotație multiplă vom proceda astfel:

  1. Răstoarnă vectorul v.
  2. Răstoarnă subvectorul v[0..n-k-1]
  3. Răstoarnă subvectorul v[n-k..n-1]

Iată o soluție bazată pe această idee:

#include <stdio.h>

int v[200000];

int main() {
  FILE *fin, *fout;
  int n, n1, n2, k, k1, k2, i, j, aux;

  fin = fopen( "rotk.in", "r" );
  // citim prima secventa
  fscanf( fin, "%d", &n1 );     // lungime
  for ( i = 0; i < n1; i++ )
    fscanf( fin, "%d", &v[i] ); // cele n1 elemente
  fscanf( fin, "%d", &k1 );     // cu cit trebuie rotita

  // citim a doua secventa
  fscanf( fin, "%d", &n2 );        // lungime
  for ( i = 0; i < n2; i++ )
    fscanf( fin, "%d", &v[i+n1] ); // cele n2 elemente, in continuare
  fscanf( fin, "%d", &k2 );        // cu cit trebuie rotita

  fscanf( fin, "%d", &k );         // cu cit rotim secventa finala
  fclose( fin );

  n = n1 + n2;

  // rotim prima secventa cu k1
  // rasturnare v[0..n1-1]
  i = 0;
  j = n1 - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
  // rasturnare v[0..n1-k1-1]
  i = 0;
  j = n1 - k1 - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
  // rasturnare v[n1-k1..n1-1]
  i = n1 - k1;
  j = n1 - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }

  // rotim a doua secventa cu k2
  // rasturnare v[n1..n-1]
  i = n1;
  j = n - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
  // rasturnare v[n1..n-k2-1]
  i = n1;
  j = n - k2 - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
  // rasturnare v[n-k2..n-1]
  i = n - k2;
  j = n - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }

  // rotim secventa compusa cu k
  // rasturnare v[0..n-1]
  i = 0;
  j = n - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
  // rasturnare v[0..n-k-1]
  i = 0;
  j = n - k - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }
  // rasturnare v[n-k..n-1]
  i = n - k;
  j = n - 1;
  while ( i < j ) {
    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    i++;
    j--;
  }

  fout = fopen( "rotk.out", "w" );
  for ( i = 0; i < n; i++ )
    fprintf( fout, "%d ", v[i] );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Lecție

Vectori preinițializați

Să presupunem că vrem să rezolvăm următoarea problemă:

Aprinse

Dispunem de un calculator de buzunar care afișează cifrele în mod clasic, folosind 7 fante luminoase aprinse sau stinse. Astfel, cele zece cifre zecimale se reprezintă astfel:

Cifre afișaj electronic

Se cere ca, dat un număr de maximum 18 cifre la intrare să se afișeze numărul de fante aprinse necesare pentru a afișa acel număr pe ecranul calculatorului de buzunar.

Exemple: numărul 254 are 14 segmente aprinse (5 + 5 + 4), iar numărul 2083 are 23 de segmente (5 + 6 + 7 + 5).

Pentru a rezolva această problemă vom afla pe rînd cifrele numărului, și pentru fiecare cifră în parte vom afla numărul său de segmente, pe care îl vom aduna la o sumă globală (variabilă acumulator). Întrebarea este 'cum calculăm numărul de segmente al unei cifre date'?

Soluție fără vectori

Putem rezolva această problemă fără a folosi vectori. Pentru fiecare cifră vom avea nouă teste if pentru a decide ce număr adunăm:

s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  if ( cf == 0 )
    s += 6;
  else if ( cf == 1 )
    s += 2;
  else if ( cf == 2 )
    s += 5;
  ...
  else if ( cf == 8 )
    s += 7;
  else
    s += 6;
}
printf( "%d", s)

Putem scurta puțin această soluție grupînd cifrele după numărul lor de segmente:

s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  if ( cf == 0 || cf == 6 || cf == 9 )
    s += 6;
  else if ( cf == 1 )
    s += 2;
  else if ( cf == 2 || cf == 3 || cf == 5 )
    s += 5;
  else if ( cf == 4 )
    s += 4;
  else if ( cf == 7 )
    s += 3;
  else
    s += 7;
}
printf( "%d", s)

Există o soluție mai bună?

Soluție cu vector

Desigur, folosind vectori. Am putea să păstrăm pentru fiecare cifră numărul ei de segmente. Vom păstra aceste numere într-un vector nrseg[10], pe care îl vom inițializa la începutul programului. În acest fel putem afla ușor cîte segmente are o cifră: dacă cifra este cf, atunci numărul său de segmente este nrseg[cf].

Iată un program posibil:

int nrseg[10];
...
nrseg[0] = 6;
nrseg[1] = 2;
nrseg[2] = 5;
nrseg[3] = 5;
nrseg[4] = 4;
nrseg[5] = 5;
nrseg[6] = 6;
nrseg[7] = 3;
nrseg[8] = 7;
nrseg[9] = 6;

s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  s += nrseg[cf];
}
printf( "%d", s)

Precum observați, programul nu este cu mult mai scurt. Dar de data aceasta mare parte din program este inițializarea vectorului nrseg[10], instrucțiunile de atribuire. Calculul în sine ocupă doar șase linii, corpul instrucțiuni while este mult mai mic față de soluțiile anterioare.

Soluție cu vector preinițializat

Pentru astfel de situații, atunci cînd ne dorim să inițializăm un întreg vector cu multiple valori, limbajul C ne ajută să scriem ceva mai puțin. Putem atribui toate cele zece valori într-o singură linie! Această atribuire se face în aceeași linie în care declarăm vectorul. Astfel, în exemplul nostru, vom atribui cele zece valori astfel:

int nrseg[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

Acest tip de declarație poartă denumirea de vector preinițializat. Astfel, programul nostru devine:

int nrseg[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
...
s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  s += nrseg[cf];
}
printf( "%d", s)

Manipularea orelor și minutelor pe ceas

Deși orele și minutele sînt doar numere, anumite exerciții pot pune probleme.

Problemă: se dau doi timpi, t1 și t2, specificați ca ore și minute. Astfel, vom avea la intrare o1, m1 și o2, m2. Cîte ore și minute se află între acești doi timpi? Atenție! Dacă t2 este înaintea lui t1 se consideră că am trecut într-o nouă zi. Exemplu: dacă t1 este 10:35 și t2 este 18:20 atunci vom afișa 07:45. Dacă t1 este 22:25 și t2 este 20:05 vom afișa 21:40.

La prima vedere acest exercițiu pare încîlcit. Va trebui să comparăm cei doi timpi. Dacă t1 este înaintea lui t2 atunci va trebui să comparăm cîte ore avem între o1 și o2. Dar și aceasta va depinde de relația dintre m1 și m2. Dacă t1 este după t2 lucrurile se complică și mai mult: trebuie să aflăm cîte ore și minute avem pîna la finalul zilei, apoi să aflăm cîte ore și minute avem de la începutul zilei pînă la t2, iar în final trebuie să le adunăm. Multe cazuri particulare. Cum facem să simplificăm lucrurile?

Regulă: pentru a nu ne încurca, întotdeauna vom face conversia orelor la cea mai mică unitate de măsură, fie ea minut sau secundă. În final vom face conversia inversă, de la minute, la ore și minute.

În cazul problemei noastre, vom converti t1 și t2 la minute. Algoritmul este următorul:

1. calculează t1 = o1 * 60 + m1
2. calculează t2 = o2 * 60 + m2
3. calculează d = t2 - t1
4. dacă d < 0 atunci
     4.1 calculează d = 24 * 60 - d
5. calculează o3 și t3 pe baza lui d, astfel:
     5.1 o3 = d / 60
     5.2 m3 = d % 60
6. afișează o3 și m3

Concluzie: în problemele în care avem nevoie să lucrăm cu ore, minute și secunde, este foarte important să transformăm timpul într-un singur număr exprimat în cea mai mică unitate de timp implicată. În exemplul de mai sus această unitate este minutul. Uneori s-ar putea să fie secunda. După transformare vom face calculele cerute de problemă. În final vom transforma înapoi în ore, minute, posibil secunde, dacă problema necesită acest lucru.

Sfaturi pentru olimpiadă

Iată cîteva sugestii pentru olimpiadă.

Ce să faceți / ce să nu faceți

Ce să faceți

  • Odihnă: odihniți-vă cu o zi înainte. Relaxați-vă cu activitatea favorită. Mergeți la un film, jucați jocul vostru preferat, etc. Încercați să nu vă gîndiți la concurs.
  • Ceas: aveți un ceas la voi. Nu ceasul calculatorului, al telefonului sau al smartphone-ului. Fiți conștienți de trecerea timpului, nu vă treziți din visare cînd mai este un sfert de oră. Pentru aceasta un ceas așezat pe banca de lucru este ideal. Nu uitați: toate celelalte ceasuri pot fi incorecte, sau să moară.
  • Țineți socoteala timpului: notați ora începerii concursului pe foaie. Verificați la final că ați avut tot timpul promis. Dacă aveți probleme cu calculatorul și cereți ajutorul supraveghetorului notați timpul cînd ați fost întrerupți și apoi timpul cînd reveniți la un calculator funcțional. Aveți dreptul la o prelungire a timpului egală cu timpul pierdut.
  • Cereți-vă drepturile: dacă vă opresc mai devreme decît e cazul, sau dacă ați pierdut zece minute din cauza unui calculator care nu a funcționat și nu vi se dau, cereți respectuos să vi se extindă timpul cu acele minute. Supraveghetorii pot uneori să uite, olimpiada este stresantă și pentru ei. Dacă nu înțelegeți textul unei probleme, după ce l-ați citit cu mare atenție, puneți întrebări pentru clarificare (formulate astfel încît răspunsul să fie 'DA' sau 'NU').
  • Low hanging fruit: rezolvați problema mai ușoară prima. Citiți toate problemele la început și hotărîți-vă care este mai ușoară. Cu ea începeți. Puteți inclusiv să rezolvați subpunctele mai ușoare primele. De exemplu puteți să rezolvați problema 1 punctul a), apoi problema 2 punctul b).
  • Moral ridicat: intrați în sală încrezători în voi. Sînteți printre cei mai buni din țară, aveți puterea să vă clasați printre primii din țară. Propuneți-vă să luați punctaj maxim și reamintiți-vă că puteți acest lucru.
  • Probleme grele: atunci cînd constatați că problemele sînt grele nu vă speriați. Bucurați-vă! Este cea mai bună situație pentru voi. Aveți numai de cîștigat: fie știți să faceți problema, caz în care este perfect, căci problema fiind grea v-ați asigurat că veți fi mai sus ca ceilalți. Fie nu știți să faceți problema și atunci care este șansa ca cei mai slabi ca voi să știe să o facă? Temeți-vă de problemele ușoare, pe care știu toți să le facă. Voi le veți gîndi, ceilalți le vor picta la perfecție.
  • Atenție: fiți foarte atenți la detalii: la numele fișierelor de intrare/ieșire; la numele sub care trebuie să salvați programul C; la setările de proiect CodeBlocks de care am vorbit: -Wall și -O2; la locul unde ați salvat proiectul, și numele proiectului în caz că aveți nevoie să le copiați în altă parte.

Ce să nu faceți

  • Nu îngrășați porcul în ajun: nu faceți probleme în ultima clipă . Vă veți extenua inutil. În urma stresului s-ar putea să nu reușiți să le faceți, ceea ce vă va demoraliza. Aveți nevoie de moral ridicat la concurs.
  • Nu vă panicați: panica ucide creierul. Panica vă face să gîndiți mai încet și să doriți în subconștient să ieșiți din sală. Controlați-o. Nu uitați că o problemă grea, pe care nu știți să o faceți, vă avantajează, pentru că probabil nici ceilalți nu știu, pe cînd voi aveți o șansă să luați puncte pe ea.
  • Nu-i băgați în seamă pe cei ce se dau mari: unii elevi spun cu voce suficient de tare să fie auziți, în timpul concursului, lucruri de genul 'aaah, am făcut-o și pe asta, super' sau 'am rupt, sigur iau suta', etc. Este modul lor inconștient de a vă demoraliza. De obicei ei se clasează slab. Ignorați-i. De asemenea veți vedea că unii dintre concurenți părăsesc sala mai devreme cu o oră cu un aer fericit, eventual spunînd 'sigur mă calific' sau 'am făcut tot, yesss'. Ignorați-i. Și ei se clasează slab. Nu vă demoralizați indiferent cîți elevi ies din sală. Lupta voastră nu este cu ei, ci cu problemele și punctele.
  • Nu ieșiți mai devreme din sală: dacă nu ați terminat problemele continuați să vă gîndiți la o soluție. Dacă ați terminat problemele și vă plictisiți creați mai multe teste pe care să le testați. Nu uitați: nimănui nu-i pasă cît de repede ați ieșit. Nu luați puncte suplimentare pentru asta.
  • Nu modificați în ultima clipă un program care funcționează: riscați să nu aveți timp să-l testați și să luați zero puncte la acea problemă.
  • Nu vă îngrijorați de părerea noastră: noi, instructorii, știm bine care este valoarea voastră. Nu avem nevoie de un rezultat la olimpiadă să aflăm. Nu o să ne vedeți vreodată supărați pe voi pentru că nu ați luat punctaj bun. Dimpotrivă, orice veți face vom fi mîndri de voi pentru cît de departe ați ajuns în numai cîteva luni. Grija voastră trebuie să fie rezolvarea problemelor, nu noi. Noi sîntem de partea voastră. Chiar dacă la cerc sau la clasă, cînd sîntem între noi, vă certăm sau ne mai supărăm pe voi, în momentul cînd ați ieșit din școală să vă "luptați" cu olimpiada pentru noi, sîntem de aceeași parte a baricadei.

Diferenţa dintre olimpiadă şi viaţa reală

Nu uitaţi că olimpiada este un concurs de verificare a cunoştinţelor, nimic mai mult, nimic mai puţin. Ea nu este evaluarea supremă a unui elev, la fel cum nu este nici ceva de ignorat cu dispreţ. Este cel mai mare concurs de la clasa a 5a, drept pentru care îl vom trata cu respect. Dar nu ne vom spînzura de grindă, considerînd că viaţa s-a sfîrşit, dacă nu obţinem rezultatul dorit. Olimpiada nu ne defineşte ca oameni.

Acestea fiind spuse, dacă mergem la olimpiadă, ne dorim un scor cît mai bun. De aceea consider utilă următoarea analogie între arte marţiale si informatică:

  • În viaţa reală: în arte marţiale învăţăm pe viaţă. Procedee noi, ce trebuie aplicate cît mai corect, perfect dacă se poate. Filozofie, mod de comportament, respect faţă de artă şi luptă. Atunci cînd mişcarea nu este perfectă, instructorul vă va corecta. Bătaia este interzisă cu excepţia cazului cînd sînteţi în legitimă apărare. Este imoral şi foarte urît să cîştigaţi avantaje în viaţa reală bătîndu-i pe cei mai slabi. Artele marţiale au ca scop îmbunătăţirea organismului.
  • La olimpiadă: olimpiada este ca legitima apărare. Ca şi cînd sînteţi cu fratele mai mic după voi şi vă atacă golanii. În acel moment nu vă verifică nimeni cît de frumos aţi executat procedeul pentru a scăpa teferi. Tot ce contează este să învingeţi. Pentru aceasta vă veţi folosi de orice! Dacă găsiţi un bolovan, îl aruncaţi în adversar. O chiuvetă spartă, bună şi aceea! La fel şi la olimpiadă, tot ce contează sînt punctele. Nu cît de frumoasă este metoda folosită, nici cît de frumos aţi scris codul. Dacă puteţi lua puncte afişînd mereu "0", o faceţi. Această practică nu ar fi acceptată nici la cercul nostru şi nici în viaţa reală. Din păcate, însă, la olimpiadă nu se punctează stilul şi perfecţionismul, ci numai punctele.

Atenţie însă! Olimpiada este o excepţie, nu o regulă! Aşa cum în viaţa reală nu puteţi să smulgeţi chiuveta din perete pentru a o arunca în colegul de clasă, nici la cerc, la companii, sau unde se va întîmpla să rezolvaţi probleme de informatică, nu puteţi trişa, sau scrie cod ineficient.


Tema

Tema 28: să se rezolve următoarele probleme (program C trimis la vianuarena):

Opțional: Temă opțională 28: să se rezolve următoarele probleme (program C trimis la vianuarena):

Rezolvări aici [1]