Clasa a V-a lecția 29 - 1 mar 2018

From Algopedia
Jump to navigationJump to search

Comentarii tema 28

  1. Topul pescarilor la jimjam: Ipate 16 surse, Nicola 13 surse, Togan 13 surse, Mocanu 12 surse, Aizic 10 surse, Benescu 10 surse, Dobre 10 surse, Chivu 9 surse, Petcu 9 surse, Asgari 8 surse, Iordache 7 surse, Grecu 6 surse, Cadîr 5 surse, Dumitrescu 5 surse, Rebengiuc 5 surse,
  2. Topul indentatorilor de cartier: Cadîr în categoria: 'indentăm artistic, după suflet'. Cojocaru, în categoria 'o sursă da, una ba'.
  3. Topul copiatorilor: Asgari, Petcu și Voicu cîștigă competiția de surse copiate la varena, reușind să copieze nici mai mult nici mai puțin decît de la... de la Cristian Frâncu! Motto-ul lor este copiem doar de la cei mai buni! Pe locul doi se află Tatomir, cu motto-ul tata este cel mai tare!
  4. Mulți dintre voi au simțit nevoia să folosească tipul long long la problema jimjam. Nu era necesar. De aceea nu este bine să învățați materia în avans, veți folosi greșit acele cunoștințe.
  5. Unii din voi au folosit vectori la numere10. Nu erau necesari.
  6. Problema numere10 cere să se calculeze numărul de divizori ai unui număr. Este o problemă care se rezolvă eficient testînd divizorii doar pînă la radical din n. Am mai discutat acest lucru cu alte ocazii. Există și rezolvarea bazată pe descompunerea în factori primi pe care o vom discuta.

Tema - rezolvări

Rezolvări aici [1]

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.

Lecţie

Deoarece lecția a fost foarte lungă și bateria camerei video s-a descărcat discuția soluțiilor la problema interval2 nu apare pe film.

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-03-01-lectie-info-29-720p.mp4</html5media>


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)

Unele probleme se rezolvă ceva mai ușor folosind astfel de vectori. Acesta este și cazul problemei speciale pe care o aveți la temă.

Problemele date la Info Oltenia clasele 5-6

Problema brățara

Problema brățara a fost dată la Info Oltenia 2018, clasele 5-6.

#include <stdio.h>

int poz[100]; // poz[i] = pozitia margelei care incepe cu i

int main() {
  FILE *fin, *fout;
  int n, c, i, nrb, ucf, cap, lmax, start, p, u;

  fin = fopen( "bratara.in", "r" );
  fscanf( fin, "%d%d", &c, &n );
  nrb = 0;   // numarul de bratari ce nu pot fi extinse (punctul 1)
  ucf = 100; // ultimele doua cifre ale margelei anterioare
  cap = 0;   // pozitia capului (inceputlui) bratarii curente
  lmax = 1;  // lungimea bratarii circulare maxime, initial ceva imposibil
  start = 0; // pozitia de start a bratarii circulare maxime
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%d", &p );
    u = p % 100;       // ultimele doua cifre
    while ( p >= 100 ) // calculam primele doua cifre
      p /= 10;
    
    if ( p != ucf ) {    // nu se potriveste cu margeaua din-nainte?
      if ( i - cap > 1 ) // bratara s-a incheiat, are macar doua margele?
        nrb++; // numaram inca o bratara ce nu poate fi extinsa (punctul 1)
      cap = i; // retinem noul inceput pentru bratara care tocmai incepe (cap)
    }
    if ( poz[p] < cap ) // daca e prima margea care incepe cu p in noua bratara
      poz[p] = i;       // retinem pozitia ei, i

    if ( poz[u] >= cap ) { // daca avem o margea din urma care incepe cu u
      // am gasit o bratara circulara, testam daca e mai mare decit ce avem deja
      if ( i - poz[u] + 1 > lmax ) { // lungimea e mai mare decit maximul?
        lmax = i - poz[u] + 1;       // retinem lungimea
        start = poz[u];              // si pozitia ei de inceput
      }
    }
    
    ucf = u;
  }
  // testam ultima bratara - caz special la punctul 1
  if ( cap < n - 1 ) // daca avem cel putin doua margele in ultima bratara
    nrb++;
  fclose( fin );

  fout = fopen( "bratara.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%d\n", nrb );
  else if ( lmax == 1 ) // nu am gasit nici o bratara circulara
    fprintf( fout, "-1\n" );
  else
    fprintf( fout, "%d %d %d\n", lmax, start, start + lmax - 1 );
  fclose( fout );

  return 0;
}

Problema interval2

Problema interval2 a fost dată la Info Oltenia 2018, clasele 5-6.

Soluția comisiei

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int q, T, i, a, b;
  long long A, r, p, u;

  fin = fopen( "interval2.in", "r" );
  fout = fopen( "interval2.out", "w" );
  fscanf( fin, "%d%d%d", &a, &b, &q );
  for ( i = 0; i < q; i++ ) {
    fscanf( fin, "%d%lld", &T, &A );
    if ( T == 1 )        // cite numere divizibile cu A in intervalul [a, b]
      r = b / A - (a - 1) / A;
    else if ( T == 2 ) { // cite perechi de numere div. cu A in interv. [a, b]
      r = b / A - (a - 1) / A;
      r = r * (r - 1) / 2;
    } else { // cite perechi de numere in [a, b] cu produsul > A
      r = 0;
      p = (A + b) / b; // p e cel mai mic nr. p cu care putem forma o pereche
      if ( p < a )     // il ajustam sa faca parte din interval
        p = a;
      for ( ; p < b; p++ ) {
        u = (A + p) / p; // cautam cel mai mic u a.i. p * u > A 
        if ( u <= p )
          u = p + 1;
        r += b - u + 1;  // formam perechi (p u), (p u+1) ... (p b)
      }
    }
    fprintf( fout, "%lld\n", r );
  }

  fclose( fin );
  fclose( fout );

  return 0;
}

Soluție îmbunătățită

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int q, T, i, a, b;
  long long A, r, p, u;

  fin = fopen( "interval2.in", "r" );
  fout = fopen( "interval2.out", "w" );
  fscanf( fin, "%d%d%d", &a, &b, &q );
  for ( i = 0; i < q; i++ ) {
    fscanf( fin, "%d%lld", &T, &A );
    if ( T == 1 )        // cite numere divizibile cu A in intervalul [a, b]
      r = b / A - (a - 1) / A;
    else if ( T == 2 ) { // cite perechi de numere div. cu A in interv. [a, b]
      r = b / A - (a - 1) / A;
      r = r * (r - 1) / 2;
    } else { // cite perechi de numere in [a, b] cu produsul > A
      r = 0;
      p = (A + b) / b; // cautam cel mai mic p a.i. p * b > A
      if ( p < a )     // daca este in afara intervalului, il ajustam
        p = a;
      if ( p < b ) {
        u = b;
        while ( p < u ) { // cita vreme nu sint consecutive
          r += u - p; // formam perechi (p u), (p+1 u) ... (u-1 u)
          u--;
          if ( p * u <= A ) // trebuie sa marim p?
            p++;
        }
      }
    }
    fprintf( fout, "%lld\n", r );
  }

  fclose( fin );
  fclose( fout );

  return 0;
}

Soluție optimizată

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

int main() {
  FILE *fin, *fout;
  int q, T, i, a, b;
  long long A, r, p, u;

  fin = fopen( "interval2.in", "r" );
  fout = fopen( "interval2.out", "w" );
  fscanf( fin, "%d%d%d", &a, &b, &q );
  for ( i = 0; i < q; i++ ) {
    fscanf( fin, "%d%lld", &T, &A );
    if ( T == 1 )        // cite numere divizibile cu A in intervalul [a, b]
      r = b / A - (a - 1) / A;
    else if ( T == 2 ) { // cite perechi de numere div. cu A in interv. [a, b]
      r = b / A - (a - 1) / A;
      r = r * (r - 1) / 2;
    } else { // cite perechi de numere in [a, b] cu produsul > A
      p = sqrtl( A ); // cautam cel mai mic p a.i. p * (p + 1) > A
      if ( p * (p + 1) <= A ) // p este cumva prea mic?
        p++;
      if ( p <= a ) {  // toate perechile sint OK
        r = b - a + 1; // numarul de numere in [a, b]
        r = r * (r - 1) / 2; // numarul de perechi din [a, b]
      } else if ( p >= b  )  // nici o pereche nu este OK
        r = 0;
      else { // p este in intervalul (a, b) deschis la ambele capete
        // putem forma toate perechile din [p+1, p+2, ..., b]
        r = (b - p - 1) * (b - p) / 2;
        u = p + 1;
        while ( p >= a && u <= b ) {
          r += b - u + 1; // formam perechi (p u) (p u+1) ... (p b)
          p--;
          u++;
          while ( p * u <= A && u <= b ) // marim u atit cit e nevoie
            u++;
        }
      }
    }
    fprintf( fout, "%lld\n", r );
  }

  fclose( fin );
  fclose( fout );

  return 0;
}

Temă

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

  • speciale dată la OJI 2015 clasa a 5a
  • cuarț dată la OJI 2015 clasa a 5a

Rezolvări aici [2]

Succes la olimpiadă!

Mult succes la olimpiadă! Nu uitaţi că sînteţi cei mai buni şi că ne sînteţi dragi indiferent de rezultatul de duminică.