Clasa a VI-a lecția 9 - 15 nov 2018

From Algopedia
Jump to: navigation, search

Avertismente

În urma revizuirii activității din acest an școlar am decis să dau avertismente ultimatum următorilor copii: Aizic, Coman, Dragomir, Cojocaru, Dumitrescu, Stancu. Ce înseamnă acest lucru? Înseamnă că suma activității voastre constînd din teme, concursuri, atenție și activitate la curs precum și atitudinea generală, lasă de dorit. Înseamnă, de asemenea, că sînteți în pericol de a vă pierde calificarea la IQ Academy. Ce aveți de făcut? Trebuie să urmați strict instrucțiunile primite în comentariile la teme, precum și ceea ce vă comunic verbal la ore. Vreau să vă văd atenți la curs, vreau să văd absolut toate temele trimise și muncite, nu în bătaie de joc, un punctaj rezonabil la concursuri și să vă văd dornici să învățați. Este un moment bun să anunțați părinții despre aceasta, dacă nu sînt deja în temă.

Tema - rezolvări

Problema fib

Problema fib.

Comentarii generale

  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Cojocaru (sursă minimalistă).

Rezolvare

Problema fib este una "de manual" în care puteți aplica direct algoritmii de la curs. Iată o soluție posibilă:

#include <stdio.h>

#define MAXCF 6000

int n1 = 1, n2 = 1; // numerele de cifre ale numerelor
char f1[MAXCF] = { 1 }, f2[MAXCF] = { 1 }; // numerele mari

int main() {
  FILE *fin, *fout;
  int n, i, j, t;
  char aux;

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

  for ( i = 3; i <= n; i++ ) { // calculam al i-lea numar din sirul lui fibo
    // adunam f1[]+f2[] cu rezultatul in f1[]
    t = 0; // transport
    for ( j = 0; j < n2; j++ ) {
      t += f1[j] + f2[j];
      f1[j] = t % 10;
      t /= 10;
    }
    n1 = n2;
    if ( t > 0 ) {
      f1[n1] = t;
      n1++;
    }

    // interschimbam f1[] cu f2[]
    for ( j = 0; j < n1; j++ ) {
      aux = f1[j];
      f1[j] = f2[j];
      f2[j] = aux;
    }    
    t = n1;
    n1 = n2;
    n2 = t;
  }

  fout = fopen( "fib.out", "w" );
  for ( i = n2; i > 0; i-- )
    fputc( '0' + f2[i-1], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Ea nu este banal de calculat. Vom avea O(n) adunări de numere mari. Fiecare adunare necesită O(nr. cifre numere) operații. Trebuie, deci, să estimăm numărul de cifre al numerelor Fibonacci. Știm că numărul de cifre al lui x este O(x). Rămîne să estimăm numărul x, anume numărul al n-lea din șirul lui Fibonacci. Este deajuns să știm că el este de forma an. În acest caz numărul de cifre va fi O(n). Complexitatea algoritmului este O(n2).

Problema ANAF

Problema ANAF.

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Mușat, Nicola, Rebengiuc, Rughiniș, Fares, Ilie, Ipate, Tatomir.
  • Atenție: cînd numărul mare este zero el va avea zero cifre! Unii din voi au tratat zero drept caz particular, forțînd numărul de cifre la unu. Am discutat acest lucru la curs! Cazul particular este la afișare, nu la calcule. Mulți din voi au greșit aici.
  • Mulți din voi ați greșit operația modulo, cea la care nu ați putut copia totul din curs. Cam jenant, nu? Mai exact, ați uitat că numărul se poate micșora în urma operației, drept care trebuia să resetați la zero cifrele extra, din afara numărului.
  • Mulți dintre voi ați folosit un al doilea vector pentru a răsturna numărul de la intrare, ceea ce vă dublează necesarul de memorie. Este o practică foarte periculoasă. Numărul se putea răsturna în același vector în care l-ați citit.
  • Unii din voi ați declarat variabila auxiliară la răsturnarea numărului, după citire, de tip întreg. Ea trebuia să fie de tip caracter, nu? Programare neglijentă. "Merge și așa" nu este deviza IQ Academy!
  • Foarte puțini din voi ați folosit instrucțiunea switch pentru a decide ce operație trebuie făcută. Păcat, se potrivea perfect, nu?
  • Avertismente Voicu și Asgari pentru programul identic, pînă la greșeli. Este OK să vă consultați, nu este OK să vă pasați programe de la unul la altul ca să munciți mai puțin la temă.
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Cemârtan (bolnav), Cojocariu, Cojocaru (sursă minimalistă), Coman, Togan.

Comentarii individuale

Grupa de dimineață

  • Aizic: folosești v2[] degeaba, puteai sa răstorni v[]. Ți se garantează în enunț că împărțitorul nu este zero, deci ai testat inutil acest lucru. Afișarea numărului la final este urîtă: un număr mare nu are voie să înceapă cu cifre zero, deci testul cu variabila j este inutil. Ai făcut bine cele trei operații pe care le-ai luat din curs. Cînd a trebuit să scrii tu operația modulo, o foarte mică variație a împărțirii, ai greșit. Și nici nu ai încercat să corectezi. Albert, tu observi că nu corectezi niciodată temele? Atît cît ai luat la temă, așa le lași. Lucrezi minimal, cît să nu ai probleme, o atitudine incorectă.
  • Badea: șapte submisii? Din ciclul "pescuim pînă reușim". O soluție bună, bravo. Te-ai complicat la împărțire și modulo. Nu ai observat că ele au cod comun, cel de împărțire. Ai tratat special cazul cînd numărul mare ajunge zero, de ce? Nu e nevoie.
  • Benescu: Dacă folosești funcții folosește-le corect. Pasezi ca argument vectorul, dar nu și numărul lui de elemente. Ori le pasezi pe amîndouă, ori lasă-le pe ambele globale. Atenție la indentare, cînd ai if ... else if ... pui următorul if pe aceeași linie cu else pentru a nu mări indentarea. Atenție, cînd numărul mare este zero numărul lui de cifre este zero, nu unu. Programul este aproape corect. Pici multe teste deoarece la operațiunea de modulo, cînd numărul se poate micșora, nu ai grijă să setezi cifrele din afara numărului la zero.
  • Burac: maestre, știi care e diferența între o cifră și un număr? Este cea între 35p și 100p. Programul tău este aproape perfect. Din neatenție ai tratat numărul de operații ca cifră, în loc de număr. Pici cu brio toate testele cu mai mult de 9 operații. ANAF te urăște.
  • Calotă: te rog declară toate variabilele de același tip pe o singură linie. Îți place să repeți cuvîntul int? Programul tău este aproape bun. Greșești operațiunea de modulo. Uiți să setezi cifrele extra la zero.
  • Cemârtan: însănătoșire grabnică! Și să reiei temele din urmă cînd te faci bine.
  • Chivu: program aproape perfect, cu o eroare de neatenție la afișare: cînd numărul mare este zero nu vei afișa nimic. Vectorul v2[] e o rămășiță din versiuni anterioare. Atenție, un vector declarat în plus te poate costa la olimpiadă.
  • Cojocariu: nimic? Ce s-a întîmplat, te-am supărat cu ceva? (ar fi neobișnuit să nu).
  • Cojocaru: Amalia, tema ta este o bătaie de joc. Ai scris ceva rapid, apoi nici nu ai încercat să depanezi. Nu ai nevoie de v2[], poți să răstorni v[]. Trebuia să faci citirea unei operații în afara testelor. Ce rost are să repeți un fscanf cu patru variabile diferite, n1, n2, n3 și n4? Ai făcut adunarea diferit față de curs. Nu ar fi o problemă dacă ar fi corectă, dar nu e. Pe caracterul '/' ai scris codul de înmulțire. Chiar să greșești la copy/paste mi se pare exagerat. Iar apoi nici să nu te prinzi la depanare? E clar că nu ai lucrat la problemă. Iar la modulo ai copiat exact codul de împărțire, care îți calculează cîtul, nu restul.
  • Coman: nimic?
  • Dragomir: Programul tău are o formă bună, se vede că l-ai gîndit. Dar se vede și că l-ai abandonat fără să încerci să îl faci să meargă fie și parțial. Ce ai scris din prima, aia a rămas. Ai avertismente de compilare serioase, variabile neinițializate. Citești numărul mare de la intrare într-un întreg. Serios? Folosești aceeași variabilă de ciclu, i în bucla exterioară și în bucla de calcul. Greșeală evidentă dacă ai fi depanat programul. Operațiunea minus ('-') nu se cere în enunț, nu ai citit nici problema cu atenție. Denisa, lucrurile nu merg bine.
  • Dumitrescu: faci răsturnări ale numărului mare la fiecare operație. Nu era mai ușor să răstorni numărul mare de la început? Așa cum am vorbit la curs că se stochează un număr mare? Dar la adunare de ce nu răstorni? Cred că din cauza asta nici nu funcționează. Ai unele neclarități în legătură cu n, numărul de cifre, ba este numărul de cifre, ba este numărul de cifre plus unu (ceea ce nu e corect, după cum am vorbit la curs).
  • Grecu: rezolvare foarte bună, cu o mică mare neatenție: ai uitat să resetezi cifrele extra la operația modulo.
  • Hossu: programul este în regulă. Cu o mică problemă, rezolvi modulo prin scăderi repetate, ceea ce duce la depășirea timpului. Calculează-ți cu atenție complexitatea programului. De ce nu ai folosit tot împărțirea (div-ul tău) la care depuneai restul (t) în numărul mare.
  • Iordache: Programul tău ar funcționa dacă la operația modulo ai reseta cifrele extra din numărul vechi la zero. Ca observații, programare neglijentă: ai declarat vectorii cu 3 elemente în plus. Ai instrucțiuni if care trebuiau puse unul pe else-ul altuia, dar nu ai făcut asta. Folosești un vector suplimentar cînd puteai să răstorni numărul în vectorul principal. Ai lăsat un printf de debug în program.
  • Mocanu: Un pic de pescuit ne scutește de a ne crea singuri teste, nu-i așa? Cinci surse trimise. Programul final este corect, bravo. Dar: Mihai, nu poți să declari un vector de un miliard de elemente. Încă nu ai învățat asta? Vianuarena te iartă, Windows și olimpiada nu. Citirea numărului este de începător, greșeala tipică pe care am corectat-o de atîtea ori:
  a='1';
  i=0;
  while(a>='0' && a<='9'){
    a=fgetc(fin);
    if(a>='0' && a<='9'){
      v[i]=a-'0';
      i++;
    }
  }

Citești a numai pentru a îl arunca imediat la gunoi. Te rog să revezi citirea corectă a unui șir de caractere, este o greșeală inacceptabilă. Ai instrucțiuni if care trebuiau puse unul pe else-ul altuia, dar nu ai făcut asta. Ai implementat scăderea deși nu se cere, neatenție la enunț. La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter. Ai o programare foarte, foarte neglijentă. Ratezi un test deoarece ai declarat transportul t de tip long long.

  • Mușat: Program foarte corect, bravo! La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter.
  • Nicola: Program foarte bun, bravo! Singurul comentariu important: la modulo tu resetezi la zero întreg vectorul, cînd ai putea să resetezi doar pînă la mărimea numărului. Crești inutil complexitatea și riști, la olimpiadă.
  • Petcu: Un program solid, foarte bun! Cu o singură încîlceală de gîndire, te-ai complicat serios la operația modulo, exact cea pe care nu o puteai lua cu copy/paste din curs. Dar în curs îți spune că t este chiar restul împărțirii. Tu ai luat cîtul, l-ai înmulțit cu numărul mic și l-ai scăzut din numărul original. Era deajuns să scrii restul din t în numărul mare.
  • Rebengiuc: Program foarte bun, bravo! Comentarii simpatice :)
  • Rughiniș: Program foarte bun, bravo! Te rog să începi să folosești instrucțiunea for. Programele sînt mai mari acum și devin foarte greu de citit.
  • Stoian: Program bun, dar nu ai implementat operația modulo. Era cea la care trebuia să contribui puțin, la restul aveai deja codul în curs. S-a terminat combustibilul la problema a doua? Nu ai încercat să o termini? Probabil că da, dat fiind că nici nu ai încercat a treia problemă. Comentariu, este periculos sa citești un caracter așa: fscanf( fin, "%s", &c );. Modul de a citi un caracter este c = fgetc( fin );. Vezi lecția de șiruri de caractere de anul trecut.
  • Ștefănescu: o rezolvare foarte bună, bravo! Ai ratat un test pentru că nu ai tratat afișarea cazului special cînd numărul mare este zero. Atenție: nu declara vectorii în interiorul lui main()! Deși este corect, poți să pierzi teste la olimpiadă deoarece comisia limitează memoria stivă. Declară vectorii în afara lui main().
  • Togan: nimic? Nu-ți place ANAF cumva? Tu și noi toți.
  • Voicu: te-ai opintit puțin la ANAF! Program foarte bun, bravo! Ai lucrat cu Asgari? Codul vostru e aproape identic. Pe viitor ne supărăm. Ca observații de eleganță, ai tratat drept caz special numărul zero. De aceea codul crește, începi să faci distincție între restul zero, sau non-zero. Faci o treabă ineficientă, cînd restul este zero pui zerouri în tot vectorul. Era deajuns să le pui pe mărimea numărului. Genul ăsta de neglijență te poate costa TLE-uri la olimpiadă. La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter, neelegant.

Grupa de după-amiază

  • Asgari: Program foarte bun, bravo! Ai lucrat cu Voicu? Codul vostru e aproape identic. Așa încît citește comentariile lui, să nu le mai scriu de două ori. Pe viitor ne supărăm. Comentariu la problema fib: ai scris un program extrem de nestandard și neelegant.
  • Cadîr: Un program solid, foarte bun! Cu o singură încîlceală de gîndire, te-ai complicat serios la operația modulo, exact cea pe care nu o puteai lua cu copy/paste din curs. Dar în curs îți spune că t este chiar restul împărțirii. Tu ai luat cîtul, l-ai înmulțit cu numărul mic și l-ai scăzut din numărul original. Era deajuns să scrii restul din t în numărul mare. Atenție, ai declarat v2[100000]. Ce e un zero în plus între prieteni, nu? O greșeală ca asta te poate costa problema la olimpiadă. După case '*': nu e nevoie să deschizi acoladă.
  • Dobre: Un program foarte bun, bravo! Pici un test deoarece la afișare nu tratezi cazul special al numărului zero. La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter.
  • Fares: rezolvare foarte bună, bravo! La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter. Te complici cînd scazi '0' din cifre în timpul răsturnării. Mai bine scădeai chiar la citire, nu?
  • Ilie: rezolvare foarte bună, bravo! La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter. Ca observații de eleganță, ai tratat drept caz special numărul zero. De aceea codul crește, începi să faci distincție între restul zero, sau non-zero.
  • Ipate: rezolvare foarte bună, bravo! Ești singura care a luat 100p din prima, felicitări! Ca observații de eleganță: folosești un vector suplimentar nenecesar, puteai să răstorni chiar vectorul original. La olimpiadă astfel de greșeli te costă întreaga problemă, vei lua 0p.
  • Marcu: rezolvare aproape perfectă. Ai două greșeli, una mică și una mare. Cea mare este că ai uitat să resetezi cifrele la zero în afara numărului, după o operație modulo. Cea mică este că la afișare nu ai tratat cazul special cînd numărul este zero.
  • Nicu: rezolvare aproape bună. Ai văzut ce înseamnă un i în loc de j? Atenție, la răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter.
  • Stancu: sursa trimisă de tine nu funcționează nici măcar pe exemplul din enunț. Nu cred că ai încercat măcar să o depanezi. Numărul de elemente dintr-un vector este cu unu mai mare decît ultima poziție din vector, nu și la tine. Ce treabă are scăderea cu anunțul problemei, de ce ai scris cod pentru așa ceva? La împărțire și modulo ai scris greșit bucla for, trebuia să pornești de la coadă la cap. David, lucrurile nu merg bine. Deloc. Faci greșeli de bază, de genul copy/paste din curs.
  • Tatomir: Un program solid și gîndit. Însă un pic neelegant. La răsturnarea vectorului folosești o variabilă auxiliară de tip întreg, nu caracter. Codul tău la adunare și înmulțire scrie artificial zero cînd depășești numărul de cifre al numărului. Neelegant, am vorbit la curs că vom avea grijă ca acele cifre să fie zero. Ai tratat drept caz special numărul zero. De aceea codul crește, începi să faci distincție între restul zero, sau non-zero.
  • Teodorescu: soluția este bună, în ansamblu, bravo! Dar: ai o citire de caractere foarte neelegantă. Învață neapărat citirea corectă a unui șir de caractere. Vezi lecția de anul trecut, întreabă-mă dacă ai nedumeriri. Atenție la indentare! Nu facem excepții! Ai tratat drept caz special numărul zero. De aceea codul crește, începi să faci distincție între restul zero, sau non-zero.

Rezolvare

Problema ANAF este din nou una "de manual". Iată o soluție posibilă:

#include <stdio.h>

int nc;        // numarul de cifre al lui x
char x[10000]; // cifrele lui x

int main() {
  FILE *fin, *fout;
  int c, n, k, i, t, o;
  char aux;

  fin = fopen( "anaf.in", "r" );
  // citire numar x
  nc = 0;
  while ( (c = fgetc( fin )) != '\n' ) {
    x[nc] = c - '0';
    nc++;
  }
  // rasturnare numar x
  i = 0;
  t = nc - 1;
  while ( i < t ) {
    aux = x[i];
    x[i] = x[t];
    x[t] = aux;
    i++;
    t--;
  }
  // ajustare numar de cifre x
  while ( nc > 0 && x[nc-1] == 0 )
    nc--;
  
  fscanf( fin, "%d ", &n );    // citire numar de operatii cu spatiu dupa %d
  for ( o = 0; o < n; o++ ) {
    c = fgetc( fin );         // citire operator
    fscanf( fin, "%d ", &k ); // citire operand k, cu spatiu dupa %d
    switch ( c ) {
    case '+': // adunam k la x
      for ( i = 0; i < nc; i++ ) {
        k += x[i];
        x[i] = k % 10;
        k /= 10;
      }
      while ( k > 0 ) {
        x[nc] = k % 10;
        k /= 10;
        nc++;
      }
      break;
    case '*': // inmultim x cu k
      t = 0;
      for ( i = 0; i < nc; i++ ) {
        t += k * x[i];
        x[i] = t % 10;
        t /= 10;
      }
      while ( t > 0 ) {
        x[nc] = t % 10;
        t /= 10;
        nc++;
      }
      break;
    default: // impartim x la k
      t = 0;
      for ( i = nc - 1; i >= 0; i-- ) {
        t = t * 10 + x[i];
        x[i] = t / k;
        t %= k;
      }
      if ( c == '/' ) // impartire, x va contine citul impartirii
        // ajustam numarul de cifre
        while ( nc > 0 && x[nc-1] == 0 )
          nc--;
      else { // modulo, x va contine restul din t
        i = 0;
        while ( t > 0 ) {
          x[i] = t % 10;
          t /= 10;
          i++;
        }
        nc = i;
        // nu e nevoie sa setam pe zero cifrele din numarul vechi
        // toate operatiile merg doar pina la nc - numarul de cifre
      }
    }
  }
  fclose( fin );

  fout = fopen( "anaf.out", "w" );
  if ( nc == 0 )
    fprintf( fout, "0\n" );
  else {
    for ( i = nc; i > 0; i-- )
      fputc( '0' + x[i-1], fout );
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Fiecare operație este O(log X) (numărul de cifre al lui X), avem n operații, deci complexitatea soluției este O(n log X).

Problema cod

Problema cod.

Comentarii generale

  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Cemârtan (bolnav), Cojocaru (sursă minimalistă), Coman, Hossu, Stoian.

Rezolvare

Problema cod a fost dată la ONI 2016 clasa a 6a. Ea cere ca, dîndu-se numere mari la intrare, să numărăm cîte din ele sînt divizibile cu numerele de la 2 la 15. Cum rezolvăm această problemă?

Forță brută

Am putea rezolva problema folosind direct împărțiri între numere mari și numere mici. Vom calcula doar resturile împărțirilor tuturor numerelor la toate cele 14 numere (între 2 și 15 inclusiv). Ce complexitate are această soluție? Dacă notăm cu C numărul de cifre al numerelor (el fiind maxim 100) și cu D numărul de divizori la care facem împărțirile (el fiind 14) rezultă o complexitate de O(N·C·D). Făcînd înlocuirile, 100 mii ori 100 ori 14, vom avea circa 140 milioane de operații. Oare ne ajunge timpul? Să nu uităm că aceste operații sînt împărțiri, ar trebui să înmulțim cu aproximativ 30, obținînd 4.2 miliarde. Pare că nu s-ar încadra în cele 1.3s disponibile, însemnînd 3.23 miliarde de operații pe secundă. Cu toate acestea, avem aici o situație specială:

  • Testul maxim are circa 4.6 milioane caractere, sub cele circa 10 milioane pe care le-ar fi avut dacă toate valorile ar fi fost maximale. Aceasta ne împarte aproximativ la doi timpul - avem nevoie de circa 1.5 miliarde de operații pe secundă.
  • Programul necesită extrem de puțină memorie ceea ce înseamnă că putem face mult mai multe operații pe secundă decît normal.

De aceea programul se va încadra, la limită, în timp.

Iată un astfel de program, foarte scurt și simplu:

#include <stdio.h>
#include <ctype.h>

int rest[16]; // rest[i] = restul impartirii numarului la i

int main() {
  FILE *fin, *fout;
  int p, n, c, i, j, zero, ionel, george, nonp;

  fin = fopen( "cod.in", "r" );
  fscanf( fin, "%d%d ", &p, &n ); // citim si trecem la linia urmatoare
  nonp = ionel = george = 0;
  for ( i = 0; i < n; i++ ) {
    for ( j = 2; j < 16; j++ ) // resetam resturile la 0
      rest[j] = 0;

    while ( isdigit( c = fgetc( fin ) ) ) // citim numarul si il prelucram
      for ( j = 2; j < 16; j++ )          // recalculam noile resturi
        rest[j] = (rest[j] * 10 + c - '0') % j;

    zero = 1;
    for ( j = 2; j < 10; j++ )
      if ( rest[j] == 0 ) {
        ionel++;
        zero = 0;
      }
    for ( j = 10; j < 16; j++ )
      if ( rest[j] == 0 ) {
        george++;
        zero = 0;
      }

    nonp += zero;
  }
  fclose( fin );

  fout = fopen( "cod.out", "w" );
  fprintf( fout, "%d\n", p == 1 ? nonp : (p == 2 ? ionel : george) );
  fclose( fout );

  return 0;
}

Soluția comisiei

Soluția comisiei, deși are aceeași complexitate, încearcă să minimizeze numărul de împărțiri folosind criterii de divizibilitate. Ele sînt destul de simple pentru puterile lui 2 (2, 4, 8), puterile lui 3 (3, 9) și pentru 5. Cu aceste puteri vom acoperi toate numerele cerute de la 2 la 15, mai puțin cele divizibile cu 7, 11 și 13. Aici soluția comisiei devine, în opinia mea nerezonabilă, cerîndu-vă să știți niște criterii de divizibilitate obscure. Mai mult, ele nici nu par să reducă prea mult numărul de împărțiri, ele necesitînd o împărțire la cîteva cifre, însă adăugînd alte operații și complicînd programul.

Dusă pînă la capăt și implementată corect aceasta va fi cea mai rapidă soluție. Nu îmi este clar de ce nu este așa, probabil implementarea este imperfectă.

Soluția compromis

Cea mai simplă soluție care reține mare parte din viteza soluției optime este să calculăm efectiv împărțirile între numerele mari și cele trei numere rămase, 7, 11 și 13. Pentru celelalte numere fie avem criterii simple de divizibilitate, fie sînt produse de numere pentru care avem calculată divizibilitatea. Mai exact:

  • div cu 2: ultima cifră divizibilă cu 2
  • div cu 3: suma cifrelor divizibilă cu 3
  • div cu 4: numărul format din ultimele două cifre divizibil cu 4
  • div cu 5: ultima cifră divizibilă cu 5
  • div cu 6: divizibil cu 2 și cu 3
  • div cu 7: calcul rest împărțire număr mare la 7
  • div cu 8: numărul format din ultimele trei cifre divizibil cu 8
  • div cu 9: suma cifrelor divizibilă cu 9
  • div cu 10: divizibil cu 2 și cu 5 (sau ultima cifră '0')
  • div cu 11: calcul rest împărțire număr mare la 11
  • div cu 12: divizibil cu 3 și cu 4
  • div cu 13: calcul rest împărțire număr mare la 13
  • div cu 14: divizibil cu 2 și cu 7
  • div cu 15: divizibil cu 3 și cu 5

Iată un program care rezultă din aceste idei:

#include <stdio.h>
#include <ctype.h>

int rest[16];                   // rest[i] = 1 daca numarul se imparte la i
int cf3[3] = { '0', '0', '0' }; // ultimele trei cifre ale numarului

int main() {
  FILE *fin, *fout;
  int p, n, c, i, j, zero, ionel, george, nonp, mod1000, scf;

  fin = fopen( "cod.in", "r" );
  fscanf( fin, "%d%d ", &p, &n ); // citim si trecem la linia urmatoare
  nonp = ionel = george = 0;
  for ( i = 0; i < n; i++ ) {
    for ( j = 0; j < 16; j++ )
      rest[j] = 0; // numarul nu se imparte la nimic, initial
    
    cf3[0] = cf3[1] = cf3[2] = '0';
    scf = 0;
    while ( isdigit( c = fgetc( fin ) ) ) { // citim numarul si il prelucram
      cf3[2] = cf3[1]; // memoram ultimele 3 cifre
      cf3[1] = cf3[0];
      cf3[0] = c;
      scf += c - '0';  // suma cifrelor
      rest[ 7] = (10 * rest[ 7] + c - '0') %  7; // recalculam noile resturi
      rest[11] = (10 * rest[11] + c - '0') % 11;
      rest[13] = (10 * rest[13] + c - '0') % 13;
    }
    mod1000 = cf3[0] - '0' + 10 * (cf3[1] - '0') + 100 * (cf3[2] - '0');

    rest[ 7] = !rest[ 7]; // resetam resturile calculate nule la 1
    rest[11] = !rest[11];
    rest[13] = !rest[13];
    
    // divizibilitati cu 5
    if ( mod1000 % 5 == 0 ) // div cu 5
      rest[5] = 1;

    // divizibilitati cu 3 si 5
    if ( scf % 3 == 0 ) { // div cu 3
      rest[3] = 1;
      if ( scf % 9 == 0 ) // div cu 9
        rest[9] = 1;
      if ( rest[5] == 1 ) // div cu 15
        rest[15] = 1;
    }
    // divizibilitati cu 2, 3 si 5
    if ( mod1000 % 2 == 0 ) { // div cu 2
      rest[2] = 1;
      if ( mod1000 % 4 == 0 ) { // div cu 4
        rest[4] = 1;
        if ( rest[3] == 1 )     // div cu 12
          rest[12] = 1;
        if ( mod1000 % 8 == 0 ) // div cu 8
          rest[8] = 1;
      }
      if ( rest[3] == 1 ) // div cu 6
        rest[6] = 1;
      if ( rest[5] == 1 ) // div cu 10
        rest[10] = 1;
      if ( rest[7] == 1 ) // div cu 14
        rest[14] = 1;
    }

    zero = 0;
    for ( j = 2; j < 10; j++ ) {
      ionel += rest[j];
      zero += rest[j];
    }

    for ( j = 10; j < 16; j++ ) {
      george += rest[j];
      zero += rest[j];
    }

    if ( zero == 0 )
      nonp++;
  }
  fclose( fin );

  fout = fopen( "cod.out", "w" );
  fprintf( fout, "%d\n", p == 1 ? nonp : (p == 2 ? ionel : george) );
  fclose( fout );

  return 0;
}

Rezolvări aici [1]

Lecție

Matrice

Matricele sînt asemănătoare cu vectorii, dar cu două dimensiuni (coordonate, poziții) în loc de una. Vectorii se mai numesc și tablouri unidimensionale, iar matricele se mai numesc și tablouri bidimensionale.

Declarare matrice

Matricele se declară similar cu vectorii, însă cu o dimensiune în plus:

int a[100][500];

Primul număr, 100 în cazul nostru, reprezintă numărul de linii al matricei a. Al doilea număr, 500 în exemplul de mai sus, reprezintă numărul de coloane al matricei a, sau numărul de elemente al fiecărei linii. O matrice poate fi privită ca un vector de vectori. În exemplul de mai sus a poate fi privită ca un vector de 100 de elemente. Fiecare element al acestui vector este, la rîndul lui, un alt vector, de 500 de elemente. Numărul total de elemente al matricei a este 100 x 500, adică 50000 de elemente întregi.

Citire matrice

Cum citim o matrice? Asemănător cu un vector, vom citi mai întîi numărul de linii și numărul de coloane, apoi elementele. Elementele se citesc, în general, de-a lungul liniilor, fiecare linie fiind citită ca un vector:

fscanf( fin, "%d%d", &m, &n );
for ( i = 0; i < m; i++ )
  for ( j = 0; j < n; j++ )
    fscanf( fin, "%d", &a[i][j] );

Scriere matrice

Scrierea este asemănătoare cu citirea, cu mențiunea să avem grijă să tipărim un '\n' la finalul fiecărei linii:

for ( i = 0; i < m; i++ ) {
  for ( j = 0; j < n; j++ )
    fprintf( fout, "%d ", a[i][j] );
  fprintf( fout, "\n" );
}

Căutare element în matrice

i = j = 0;
while ( (i < m) && (a[i][j] != e) ) {
  j++;
  if ( j >= n ) {
    j = 0;
    i++;
  }
}

Transpunere matrice

Se dă o matrice pătrată, să se modifice astfel încît în final elementele ei să fie oglindite față de diagonala principală. Diagonala principală e cea care începe în colțul din stînga-sus și se termină în colțul din dreapta-jos. Această operațiune se mai numește si transpunere.

for ( i = 1; i < n; i++ )
  for ( j = 0; j < i; j++ ) {
    aux = a[i][j];
    a[i][j] = a[j][i];
    a[j][i] = aux;
  }

Aceeași problemă pentru diagonala secundară. Diagonala secundară e cea care începe în colțul din dreapta-sus și se termină în colțul din stînga-jos

for ( i = 0; i < (n - 1); i++ )
  for ( j = 0; j < (n - i); j++ ) {
    aux = a[i][j];
    a[i][j] = a[n - 1 - j][n - 1 - i];
    a[n - 1 - j][n - 1 - i] = aux;
  }

Tema

Tema 9, clasa a 6a

  • matrix de introducere în operații pe matrice
  • reorganizare dată la ONI 2003 clasa a 6a
  • reorganizare2 o actualizare pentru 2018 a problemei dată la ONI 2003 clasa a 6a

Rezolvări aici [2]