Clasa a VI-a lecția 8 - 8 nov 2018

From Algopedia
Jump to: navigation, search

Tema - comentarii

Nu am avut timp să corectez rezolvările voastre. M-am uitat însă pe multe din ele și acestea sînt comentariile generale:

  • Majoritatea dintre voi tratați cu seriozitate cursul și vă străduiți să rezolvați temele.
  • Cîțiva dintre voi nu se străduie și se vede. Trimiteți surse făcute de mîntuială, doar pentru a nu vă da avertismente că nu faceți tema. Un exemplu este Remus Rughiniș, care la problema john a trimis o singură sursă în care scrie fin=fopen("john.in","w");. Este un program neglijent și evident nedepanat, dacă deschide fișierul de intrare în mod scriere, nici nu pare că ai încercat să îl depanezi. În aceeași situație se află Nicu Cemârtan care nu a lucrat nimic suplimentar trimițînd doar sursa la problema leo pe care aproape o terminase în concurs, Mihai Coman care în afară de ceea ce a lucrat în clasă la problema leo nu a mai făcut aproape nimic, Albert Aizic care nici nu a încercat să aducă sursa de la concurs la leo dincolo de 36p, lăsînd-o identică, David Stancu care chiar și după multe discuții nu a înțeles ciurul lui Eratostene, Denisa Dragomir care trimite surse repezite, neatente, în care ciurul este declarat de 100 de milioane de elemente deși enunțul spune un milion - greșeli de începător, cum să încapă un vector de 100 milioane de long long (altă inutilitate, int era suficient) cînd el va ocupa 800 milioane de octeți, iar problema ne oferă 6 milioane.
  • Sînt nevoit cu părere de rău să dau un avertisment serios celor de mai sus. Sînteți codașii temelor, nu lucrați suficient și se simte, rămîneți în urmă. Faceți greșeli de neatenție, grabă, repezeală. Înțeleg surse cu greșeli finuțe, de indici, de timp, etc. Dar să nu vă calculați memoria, să folosiți long long aiurea, să deschideți fișiere de intrare în mod citire sau să închideți de două ori același fișier, acestea sînt greșeli din cauza faptului că nu lucrați.

Vă reamintesc: voi ați vrut să fiți aici. IQ Academy nu înseamnă să greșim zerouri în plus la declararea vectorilor. Puneți mîna și lucrați.

Concurs - rezolvări

Problema leo

Problema leo, dată la concurs.

Iată o soluție posibilă bazată pe ciurul lui Eratostene și numărare de cifre 1 în baza 2:

#include <stdio.h>

#define MAXN 1000000
#define MAXP2 0x80000

int sd[MAXN+1];

int main() {
  FILE *fin, *fout;
  int n, i, d, x, b1, b2, c, rez;

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

  if ( c == 1 ) { // cerinta 1
    rez = MAXP2;
    while ( rez > n )
      rez /= 2;
  } else { // cerintele 2 si 3
    // calculam suma divizorilor cu ciurul lui Eratostene
    for ( i = 1; i <= n; i++ )
      for ( d = i; d <= n; d += i )
        sd[d] += i;

    rez = 0;
    if ( c == 2 ) { // cerinta 2, numere abundente
      for ( i = 1; i <= n; i++ )
        if ( sd[i] > 2 * i )
          rez++;
    } else { // cerinta 3, reprezentari in baza doi cu acelasi numar de cifre 1
      for ( i = 1; i <= n; i++ ) {
        // cite cifre binare 1 are i
        b1 = 0;
        x = i;
        while ( x > 0 ) {
          if ( x % 2 == 1 )
            b1++;
          x /= 2;
        }
        // cite cifre binare 1 are sd[i]
        b2 = 0;
        x = sd[i];
        while ( x > 0 ) {
          if ( x % 2 == 1 )
            b2++;
          x /= 2;
        }

        if ( b1 == b2 )
          rez++;
      }
    }
  }
  
  fout = fopen( "leo.out", "w" );
  fprintf( fout, "%d\n", rez );
  fclose( fout );

  return 0;
}

Problema john

Problema john, dată la concurs.

Iată o soluție posibilă bazată pe ciurul lui Eratostene și rasturnare număr în baza 2:

#include <stdio.h>

#define MAXN 1000000
#define MAXP2 0x80000

int sd[MAXN+1];

int main() {
  FILE *fin, *fout;
  int n, i, d, x, c, rez, p2;
  
  fin = fopen( "john.in", "r" );
  fscanf( fin, "%d%d", &c, &n );
  fclose( fin );

  if ( c == 1 ) {
    // cerinta 1
    rez = MAXP2;
    while ( rez >= n )
      rez /= 2;
    p2 = rez / 2;
    while ( rez + p2 > n )
      p2 /= 2;
    rez += p2;
  } else {
    // calculam suma divizorilor cu ciurul lui Eratostene
    for ( i = 1; i <= n; i++ )
      for ( d = 2 * i; d <= n; d += i )
        sd[d] += i;

    rez = 0;
    if ( c == 2 ) {
      // cerinta 2, perechi de numere prietene
      for ( i = 1; i <= n; i++ )
        if ( sd[i] < i && sd[sd[i]] == i )
          rez++;
    } else {
      // cerinta 3, suma divizorilor proprii palindrom in baza doi
      for ( i = 1; i <= n; i++ ) {
        // este sd[i] palindrom?
        x = 0;
        d = sd[i];
        while ( d > 0 ) {
          x = 2 * x + d % 2;
          d /= 2;
        }
        if ( x == sd[i] )
          rez++;
      }
    }
  }
  
  fout = fopen( "john.out", "w" );
  fprintf( fout, "%d\n", rez );
  fclose( fout );

  return 0;
}

Tema - rezolvări

Numere binare

Problema numere binare.

Răspuns:

Forța brută

Prima idee este să numărăm în baza zece pînă la n și, pentru fiecare număr, să verificăm că este binar (are cifre numai unu și zero). Deoarece n poate fi un miliard, această soluție va pica testele mari, fiind O(n) ca timp.

Optimizare 1

O primă idee de optimizare este să numărăm numai numerele care au cifre zero și unu, numarînd în baza doi. Vom avea un contor ce reprezintă numărul în baza doi. Pentru fiecare valoare vom calcula numărul în baza zece format din cifrele în baza doi ale contorului. Dacă este mai mic sau egal cu n îl contorizăm. Continuăm procesul pînă cînd numărul format pe baza contorului depășește n.

Ce complexitate are această soluție? Deoarece n este maxim un miliard, sau 109 rezultă că numărul maxim pînă la care va ajunge contorul în baza doi va fi 29, sau 512. Nu voi detalia calculele exacte deoarece numărul de operații este atît de mic încît este clar că soluția se va încadra în timp.

Optimizare 2

Deși varianta de mai sus se încadrează în timp ea este în continuare risipitoare. Există o variantă mult mai simplă și mai scurtă. Să observăm că în varianta precedentă noi contorizăm fiecare număr binar pînă la cel maxim. Cu alte cuvinte numărul binar maxim este chiar numărul de numere căutat. Și atunci se pune întrebarea: oare nu putem calcula direct acel număr? De exemplu, dacă n este un miliard (unu cu nouă zerouri) nu putem cumva calcula direct 1000000000(2) = 512(10) ca fiind cel mai mare număr binar care corespunde? În acest exemplu numărul de numere este 512.

Cum calculăm acest număr pe cazul general? Să luăm un alt exemplu: 10204. Este clar că cel mai mare număr zecimal format numai cu cifre zero și unu, care este mai mic ca 10204 va fi 10111, deci vom avea numărul de numere ca fiind 10111(2) = 23(10).

Care este regula? Vom crea numărul în baza doi pornind de la stînga la dreapta. Parcurgem cifrele zecimale ale lui n. Dacă cifra curentă este binară (mai mică decît 2) o adăugăm pur și simplu la numărul binar. În momentul cînd dăm peste prima cifră nebinară putem completa restul numărului cu cifre 1. În exemplul de mai sus, n este 10204 și vom lua primele două cifre ca atare, iar ultimele trei se înlocuiesc cu 1. Obținem astfel 10111.

Iată programul bazat pe această idee:

#include <stdio.h>

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

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

  nb = 0; // calculam cel mai mare nr binar care scris in baza 10 este < n
  p10 = 1000000000; // n maxim este un milion, deci si puterea p10
  // vom avansa in numarul n pina la prima cifra mai mare sau egala cu 2
  // construind numarul binar cu exact aceleasi cifre
  while ( p10 > 0 && n / p10 < 2 ) { // prima cifra e mai mica ca 2?
    nb = nb * 2 + n / p10; // adaug-o la numarul binar
    n %= p10;  // taiem prima cifra a lui n
    p10 /= 10; // micsoram puterea lui 10
  }
  // de acum inainte putem adauga cifre 1 la coada, caci nu vom depasi
  // numarul n
  while ( n > 0 ) {  // adaugam atitia 1 cite cifre mai sint in n
    nb = nb * 2 + 1;
    n /= 10;
  }

  fout = fopen( "nrbin.out", "w" );
  fprintf( fout, "%d\n", nb ); // nb este numarul cerut
  fclose( fout );

  return 0;
}

Cîte calcule face acest program? El va parcurge o dată cifrele lui n, deci O(log n). Această soluție va face circa 9 calcule! Interesant!

Tema opțională - rezolvări

Problema Submulţimi 2

Problema submulţimi 2.

Răspuns: problema cere, la bază, să generăm toate submulţimile unei mulţimi, exerciţiu studiat la cerc. În loc să afişăm acele submulţimi trebuie să calculăm suma unor numere formate cu cifrele din acele submulţimi, cifre în baza n-1. Drept care, pentru fiecare număr binar generat (care reprezintă un vector caracteristic al mulţimii), va trebui să calculăm cifrele sale binare (să îl descompunem în baza doi) şi, pentru fiecare cifră 1, să adunăm cifra corespunzătoare din submulţime înmulţită cu puterea corectă a bazei de numeraţie, care este chiar n.

Desigur că toate calculele vor fi făcute modulo 982451653, aşa cum se cere în enunţ. Atenţie! Cu toate că numerele noastre sînt întregi mai mici ca un miliard, la momentul cînd înmulţim cifra în baza n cu puterea lui n vom depăşi limita unui întreg. Abia apoi vom calcula restul împărţirii la 982451653. Drept pentru care această operaţie trebuie făcută pe tipul long long.

Iată un program posibil:

#include <stdio.h>

#define BIG 982451653

int main() {
  FILE *fin, *fout;
  int n, ns, i, c, cc, s;
  long long nasoc, pn;

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

  // calculam numarul de submultimi ns = 2^n
  ns = 1;
  for ( c = 0; c < n; c++ )
    ns *= 2;
  // generam toate submultimile
  s = 0;
  for ( c = 2; c < ns; c++ ) { // numaram "in binar" pina la 2^n
    cc = c;
    pn = 1;
    nasoc = 0;
    i = 0;
    while ( cc > 0 ) {
      if ( cc % 2 == 1 ) { // pentru cifra binara de la coada
        nasoc = (nasoc + i * pn) % BIG; // adaugam cifra i la numarul asociat
        pn = (pn * n) % BIG; // crestem puterea lui n (numarul e in baza n)
      }
      cc /= 2; // trecem la urmatoarea cifra
      i++;
    }
    s = (s + nasoc) % BIG; // adunam numarul asociat la suma
  }

  fout = fopen( "submultimi2.out", "w" );
  fprintf( fout, "%d\n", s );
  fclose( fout );

  return 0;
}

Joc2

Problema joc2 dată la ONI 2010 clasa a 6-a.

Răspuns: soluția acestei probleme este relativ ușoară ca idee. Ceea ce o face posibil grea sînt detaliile de implementare.

Ideea soluției este clară: trebuie să obținem culorile într-un șir ordonat după numărul de apariții al fiecărei culori. Vom afișa primele [{\sqrt  {n}}]^{2} culori din acel șir, [{\sqrt  {n}}] linii a cîte [{\sqrt  {n}}] elemente. Cum implementăm această soluție?

O primă idee ar fi forța brută. Calculăm un vector de frecvență al culorilor. Apoi sortăm acest vector, ținînd minte cifrele din care provin frecvențele. Cum? Folosind un al doilea vector. Astfel vom avea frecv[i] numărul de apariții al culorii i și culoare[i] care va fi chiar i, inițial. Cînd sortăm vectorul frecv avem grijă să purtăm după noi și elementele vectorului culoare. În fapt vom sorta perechile (frecv, culoare) după coloana frecv. În final vom parcurge elementele în ordine descrescătoare și vom afișa din ele atît cît este necesar.

Această idee funcționează și este chiar soluția comisiei de olimpiadă. Aș vrea însă să menționez o alternativă. Țineți minte: întotdeauna cînd puteți e bine să evitați sortarea. Este scumpă ca timp și complică codul. Cum facem să nu sortăm? Folosind un al doilea vector de frecvență: vectorul de frecvență al frecvențelor!

Enunțul problemei spune că nu există două culori care să apară de același număr de ori. Perfect! Rezultă că putem construi un vector apar care pentru fiecare frecvență diferită de zero păstrează cifra care are acea frecvență. Mai exact, apar[i] este cifra care apare de i ori. Acest vector se calculeaza foarte ușor, ca orice vector de frecvență: vom parcurge vectorul frecv și pentru fiecare frecv[i] diferit de zero vom atribui apar[frecv[i]] = i (de fapt îi vom atribui i+1 pentru a distinge între zerourile inițiale ale vectorului și cifra zero).

Apoi vom parcurge vectorul apar de la maxim (60000) către minim și vom afișa cifrele corespunzătoare. Trebuie să avem grijă la implementare pentru a afișa '\n' la fiecare [{\sqrt  {n}}] cifre și a ne opri cînd am afișat cele [{\sqrt  {n}}]^{2} elemente.

Iată programul:

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

int frecv[10];
int apar[60001];

int main() {
  FILE *fin, *fout;
  int n, i, cf, ncul, lat, nrcf, afisate;

  fin = fopen( "joc2.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &cf );
    frecv[cf]++;
  }
  fclose( fin );

  ncul = 0;
  for ( cf = 0; cf < 10; cf++ ) // ordonam cifrele intr-un vector de
    if ( frecv[cf] > 0 ) {      // frecventa a frecventelor
      ncul++;
      apar[frecv[cf]] = cf+1;   // apar[f] este cifra care apare de f ori + 1
    }

  fout = fopen( "joc2.out", "w" );
  lat = sqrt( n );              // latura patratului ce trebuie afisat
  fprintf( fout, "%d\n%d\n", ncul, lat ); // afisam nr culori si latura patr.

  i = 60000;
  afisate = 0;
  while ( afisate < lat * lat ) {
    while ( apar[i] == 0 )    // descrestem frecventa pina gasim cifre
      i--;
    nrcf = i;
    while ( nrcf > 0 && afisate < lat * lat ) {
      fprintf( fout, "%d", apar[i] - 1 );
      afisate++;
      if ( afisate % lat == 0 )
        fprintf( fout, "\n" );
      nrcf--;
    }
    i--;
  }
  fclose( fout );

  return 0;
}

Rezolvări aici [1]

Lecție - numere mari

Unele probleme necesită lucrul cu numere mai mari decît ne permite tipul long long (cu aproximație 18 cifre zecimale, mai exact 264). Ce facem în acest caz? Stocăm aceste numere în vectori, cîte o cifră în fiecare element al vectorului. În continuare voi prezenta cîteva probleme clasice cu astfel de numere.

Reprezentare

Numerele mari se reprezintă într-un vector, ultima lor cifra pe prima poziție a vectorului, penultima pe a doua poziție, și așa mai departe. De exemplu, numărul 24537 se reprezintă astfel:

Reprezentarea în vector a unui număr mare

Observați că am reprezentat vectorul invers, de la dreapta la stînga, pentru ușurința citirii numărului. De ce reprezentăm cifrele numărului de la coadă la cap? Deoarece atunci cînd numerele cresc sau se micșorează cifrele lor nu trebuie deplasate în vector pentru a rămîne aliniate la începutul vectorului.

Observăm că vectorul v are ca elemente cifre, adică întregi cuprinși între 0 și 9. Pentru a folosi cît mai puțină memorie vom folosi cel mai mic întreg existent în limbajul C și anume tipul caracter. Să nu uităm că tipul caracter poate fi văzut atît ca și caracter cît și ca un întreg pe opt biți, cuprins între -128 și 127. Această reprezentare a numerelor mari se numește reprezentarea în zecimal despachetat:

char v[100];

Pentru cei curioși există și reprezentarea zecimal împachetat, în care reprezentăm două cifre zecimale pe caracter, respectiv o cifră pe primii 4 biți și o cifră pe ultimii patru biți. În această lecție nu vom vorbi despre această reprezentare.

De asemenea, pentru un număr mare trebuie să ținem minte și numărul său de cifre. În exemplul nostru acesta este 5. Printre olimpici circulă o versiune de numere mari în care numărul de cifre este memorat chiar în primul element al vectorului, v[0]. Aceasta nu este o idee bună din mai multe motive:

  • Dacă numărul mare are mai mult de 255 de cifre vom depăși tipul unsigned char.
  • Amestecă un număr de cifre cu cifrele însele, punînd la grămadă mere cu dovlecei.
  • Codul devine mai greu citibil.

Ca ultimă mențiune, trebuie să avem grijă ca cifrele nefolosite din vector să fie setate la zero. Acest lucru este foarte important atunci cînd numărul poate să crească, cum ar fi la adunare, sau înmulțire.

Afișare

Cum afișăm un număr mare? Afișînd toate cifrele sale de la final de vector spre început. Avem însă un caz particular: numărul zero. Convenția de reprezentare a unui număr mare este ca prima lui cifră (cea mai semnificativă) să fie nenulă. În cazul lui zero acest lucru nu se poate. De aceea numărul mare zero va fi reprezentat ca avînd zero cifre. De aceea, la afișare nu vom afișa nimic, deoarece vom încerca să afișăm zero cifre. Acesta este cazul particular la afișare, dacă numărul mare are zero cifre vom afișa zero. Iată codul de afișare a unui număr mare:

  if ( n == 0 )
    fprintf( fout, "0\n" );
  else {
    for ( i = n; i > 0; i-- )
      fputc( '0' + v[i-1], fout );
    fputc( '\n', fout );
  }

Adunarea unui număr mic la unul mare

Fie v un număr mare cu n cifre. Dorim să adunăm la el un număr "mic", a. Pentru aceasta vom proceda similar cu procedura de adunare "de mînă": vom aduna a la prima cifră a numărului, vom stoca pe prima poziție ultima cifră a acestui număr, apoi vom calcula transportul prin împărțire la zece. Acest transport se adună la a doua cifră, stocînd ultima cifră a rezultatului pe a doua poziție și calculînd noul transport prin împărțire la zece. Diferența față de adunarea "de mînă" este că transportul poate fi mai mare decît 9. Iată secvența de cod care adună numărul mare (n, v) cu numărul a:

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

Scăderea unui număr mic din unul mare

Scăderea unui număr mic din unul mare este similară cu adunarea. Transportul va fi negativ. Trebuie însă să fim atenți la un lucru: operația % (modulo) în C nu se comportă ca la matematică. La matematică restul împărțirii a două numere este pozitiv sau zero. În C restul împărțirii unui număr negativ la unul pozitiv este negativ sau zero. De aceea codul trebuie modificat față de adunare pentru a calcula restul pozitiv al împărțirii la zece. De asemenea trebuie să avem grijă să scădem numărul de cifre, dacă este cazul. Vom păstra în nn poziția ultimei cifre diferite de zero. Iată secvența de cod care scade numărul mic a din numărul mare (n, v):

  a = -a;
  i = 0;
  while ( a < 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    if ( v[i] < 0 ) {
      v[i] += 10;
      a--;
    }
    i++;
  }
  // ajustam numarul de cifre, deoarece primele cifre pot fi zero
  while ( n > 0 && v[n-1] == 0 )
    n--;

Atenție: programul de mai sus presupune că numărul mic este mai mic sau egal cu numărul mare.

Adunarea a două numere mari

Adunarea a două numere mari este similară cu adunarea unui număr mare cu unul mic. Vom folosi un transport și vom aduna cifră cu cifră cele două numere mari. În final vom testa dacă mai avem transport. Dacă avem el este maxim o cifră (demonstrați). Iată secvența de cod care adună numărul mare (n2, v2) la (n1, v1) depunînd rezultatul tot în (n1, v1):

  n1 = n1 < n2 ? n2 : n1;
  t = 0;
  for ( i = 0; i < n1; i++ ) {
    t = t + v1[i] + v2[i];
    v1[i] = t % 10;
    t /= 10;
  }
  if ( t > 0 ) {
    v1[i] = t;
    n1++;
  }

Scăderea a două numere mari

Scăderea a două numere mari este similară cu scăderea unui număr mare din unul mic. Vom folosi un transport negativ și vom scădea cifră cu cifră cele două numere mari. După ce se termină cifrele numărului de scăzut vom continua scăderea pînă ce transportul devine zero. Ca și la scăderea unui număr mic va trebui să avem grijă să scădem numărul de cifre dacă este cazul. Iată secvența de cod care scade numărul mare (n2, v2) din numărul mare (n1, v1):

  t = i = 0;
  while ( i < n2 || t < 0 ) {
    t = t + v1[i] - v2[i];
    v1[i] = t % 10;
    t /= 10;
    if ( v1[i] < 0 ) {
      v1[i] += 10;
      t--;
    }
    i++;
  }
  // ajustam numarul de cifre, deoarece primele cifre pot fi zero
  while ( n1 > 0 && v1[n1-1] == 0 )
    n1--;

Atenție: programul de mai sus presupune că numărul (n2, v2) este mai mic sau egal cu numărul (n1, v1).

Înmulțirea unui număr mare cu unul mic

Înmulțirea unui număr mare cu unul mic este similară cu adunarea unui număr mare cu unul mic. Vom folosi un transport la care adunăm cifra curentă înmulțită cu numărul mic. Ultima cifră a transportului se stochează în cifra curentă, iar transportul se împarte la zece, apoi trecem la cifra următoare. După ce se termină cifrele numărului mare vom continua procedura pînă ce transportul devine zero. Trebuie să avem grijă să actualizăm numărul de cifre dacă este cazul. Iată secvența de cod care înmulțește numărul mic a cu numărul mare (n, v):

  t = i = 0;
  while ( i < n || t > 0 ) {
    t = t + a * v[i];
    v[i] = t % 10;
    t /= 10;
    i++;
  }

  if ( i > n )
    n = i;

Împărțirea unui număr mare la unul mic

Împărțirea unui număr mare la unul mic se face invers față de celelalte operații de pînă acum. Vom parcurge numărul mare de la cea mai semnificativă cifră (cifra cu indicen - 1) către cifra de indice zero (prima din vector). Vom avea un rest curent; vom adăuga fiecare cifră a numărului mare la coada restului, înmulțind restul cu zece și adunînd cifra. Împărțind restul curent la numărul mic obținem încă o cifră din cît, pe care o putem suprascrie peste cifra din numărul mare. La final vom avea cîtul în numărul mare, iar ultimul rest este chiar restul împărțirii. Este posibil ca cîtul să aibă mai puține cifre decît numărul original, drept care va trebui să reducem numărul de cifre căutînd prima sa cifră nenulă. Iată secvența de cod care împarte numărul mare (n, v) la numărul mic a:

  t = 0;
  for ( i = n - 1; i >= 0; i-- ) {
    t = t * 10 + v[i];
    v[i] = t / a;
    t %= a;
  }
  // ajustam numarul de cifre, deoarece primele cifre pot fi zero
  while ( n > 0 && v[n-1] == 0 )
    n--;

Temă

Tema 8, clasa a 6a

  • fib problemă de adunare a două numere mari
  • ANAF problemă de operații între numere mari și numere mici
  • cod dată la ONI 2016 clasa a 6a

Rezolvări aici [2]