Clasa a VI-a lecția 22 - 28 feb 2019

From Algopedia
Jump to: navigation, search

Anunț

Ce reguli ale cercului nostru încalcă următorul program?

#include <fstream>

using namespace std;
const int nmax=1000005;
ifstream in("cmmp.in");
ofstream out("cmmp.out");

int cifre(long long n){
    int cnt=1;
    n/=10;
    while(n){
        n/=10;
        cnt++;
    }
    return cnt;
}

long long rasp[nmax];
int v[11];
long long k;

void fa(long long num){
    long long x=cifre(num),i,nr,j,num1=num;
    for(i=x; i>=1; i--){
        v[i]=num1%10;
        num1/=10;
    }
    for(i=1; i<=x; i++){
        nr=0;
        for(j=i; j<=x; j++){
            nr=nr*10+v[j];
            if(nr>nmax)
                break;
            if(rasp[nr]==-1)
                rasp[nr]=num;
        }
    }
}

int main()

{
    long long n,x,i;
    in>>n;
    for(i=1; i<=1000000; i++)
        rasp[i]=-1;
    for(k=1; k<=170000; k++)
        fa((long long)(k*k));
    for(i=1; i<=n; i++){
        in>>x;
        out<<rasp[x]<<' ';
    }
    return 0;

}
  • for cu un break în el, să ieșim cînd ne convine.
  • Variabile inițializate la declarare.
  • Programare aproximativă - vectori declarați cu cinci în plus (în fapt codul este atît de neglijent încît declară vectorul de zece ori mai mare, plus încă 5, să fie).
  • Citiri C++.
  • Amestec groaznic de funcții, cu declarații de variabile.
  • Cod negîndit de sus pînă jos, cu funcții inutile care fac programul mai ineficient. De exemplu, programul parcurge cifrele numărului de două ori, prima oară pentru numărarea lor, a doua oară pentru depunere în vector, ceea ce duce la dublarea numărului de împărțiri.
  • Lene de gîndire - cifrele numărului sînt invers în vector, deși am vorbit despre numere mari.
  • Aberații de genul (long long)(k*k) atunci cînd k este deja long long și cînd oricum, și dacă nu era, conversia nu ar fi funcționat deoarece înmulțirea se face înaintea conversiei.
  • În general un cod oribil, neîngrijit, doar pentru a lua suta la varena.

Spiritul cercului este important

Programul de mai sus nu a fost scris pentru a fi văzut de mine. Dar a fost scris de unul dintre noi. Pot să accept unele poluări de cod, în graba concursului, cum ar fi citire/scriere în C++, cod neîngrijit, poate chiar și declarare de vectori cu 5 elemente în plus. Nu pot însă să accept, nici măcar în graba concursului, să încălcați principiile de bază ale programării structurate, folosind instrucțiunea break. Codul de mai sus ne spune că acel copil se simte, în fapt, mai confortabil scriind așa. Deci așa codează în mod uzual. Cineva care își insușește cerințele cercului nu are cum să scrie asemenea cod, nici măcar în grabă.

Dacă așa doriți să codați, nu aveți nevoie de IQ Academy. Vă puteți duce la toți dopatorii șefi, care dau cu for-ul și cărora puțin le pasă despre claritatea codului lor și implicit a algoritmului lor. Deci vă voi invita să plecați.

Tema - rezolvări

  • Avertismente lui:
    • Cojocariu, care a trimis o rezolvare forță brută la numere24, o rezolvare de zero puncte la problema turnuri, la care se puteau lua lejer 40p, soluția din concurs la gazon, neterminată și nici o soluție la peridia. Cojocariu, nu sînt deloc mulțumit.
    • Iordache, care a trimis o rezolvare doar la numere24 și aceea de 12p. Iordache, temele nu sînt opționale.
    • Cadîr, care nu a trimis nimic la peridia, iar la gazon a trimis aceeași rezolvare ca și în concurs, de 26p, nevrînd să gîndească extra. Cadîr, mobilizează-te te rog, dacă vrei să ramîi cu noi!

Problema numere24

Problema numere24 a fost dată la OJI 2018 clasa a 6a. Primele două cerințe sînt banale. Ele sînt date pentru că problema a fost dată la OJI, pentru ca concurenții să ia puncte:

  • punctul 1 cere să calculăm al nlea număr divizibil cu 10. Deoarece numerele divizibile cu 10 sînt 0, 10, 20, 30, ... rezultă evident că al nlea număr divizibil cu 10 este 10 · (n - 1). Grijă la depășiri, calculul trebuie făcut în long long.
  • punctul 2 cere să detectăm dacă 3 numere sînt divizibile cu zece, sau, în caz contrar, dacă sînt palindrom. Banal.

Punctul 3 este singurul interesant. El ne cere să afișăm cîte numere de k cifre există care nu se termină în zero și se socotesc de două ori dacă nu sînt palindrom. Prima idee este, sper clară: să încercăm să găsim o formulă. Să vedem:

  • Numărul de numere de k cifre este 9·10k-1
  • Numărul de numere de k cifre divizibile cu 10 este de zece ori mai mic, deci 9·10k-2
  • Rezultă că numărul de numere de k cifre nedivizibile cu 10 este 9·10k-1 - 9·10k-2 adică 90·10k-2 - 9·10k-2 adică 81·10k-2
  • Numărul de palindromuri de k cifre se calculează observînd că putem varia doar jumate din cifre, cealaltă jumate fiind inversa primei jumătăți. Vom avea, deci, 9·10(k-1)/2 palindromuri. Observăm că ele nu se pot termina în zero, deoarece răsturnatul lor nu ar avea k cifre. Deci toate aceste palindromuri se iau în considerare.
  • Pentru a calcula numărul cerut de numere de k cifre din șir vom dubla numerele nepalindrom și vom lua în considerare numerele palindrom doar o dată. Este tot una cu a dubla toate numerele de k cifre nedivizibile cu zece și a scădea numărul de numere palindrom.
  • Rezultă deci formula finală n = 2·81·10k-2-9·10(k-1)/2

În concluzie, numărul dorit este n = 162·10k-2-9·10(k-1)/2.

Cum calculăm acest număr? În primul rînd observăm că el depășește chiar și tipul long long, deci nu îl putem calcula direct. Apoi observăm că pentru k suficient de mare el este 16200...0 din care scădem 900...0. Dar al doilea număr are mult mai puține zero la coadă decît primul număr, are aproximativ jumate din ele. Deci problema se reduce la a scădea 9 din 16200...0, care este un număr de forma 16199...91. Rămîne doar să calculăm cîte cifre 9 avem. Rezultă că numărul nostru este format astfel:

  • 161
  • 9 de n/2 - 2 ori
  • 1
  • 0 de (n-1) / 2 ori

Desigur că acest lucru funcționează numai de la un k în sus, mai exact 4. Pentru primele 3 valori va trebui să calculăm "de mînă" rezultatul.

Iată un program bazat pe aceste idei:

#include <stdio.h>

int rez[3] = { 9, 153, 1530 };

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

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

  fout = fopen( "numere24.out", "w" );
  switch ( c ) {
  case 1: // cerinta 1, al n-ulea numar divizibil cu 10
    fprintf( fout, "%lld", (n - 1) * 10LL );
    break;
  case 2: // cerinta 2, detectie numere palindrom
    for ( i = 0; i < 3; i++ ) {
      n /= 10;
      if ( n % 10 == 0 )
        fprintf( fout, "0 " ); // divizibil cu 10, nu apare niciodata
      else {
        c = 0;
        nc = n;
        while ( nc > 0 ) {
          c = c * 10 + nc % 10;
          nc /= 10;
        }
        if ( c == n )
          fprintf( fout, "1 " ); // palindrom, apare o data
        else
          fprintf( fout, "2 " ); // nepalindrom, apare de doua ori
      }
    }
    break;
  default: // cerinta 3, numarul valorilor de n cifre din sir
    // nr. cerut este 162 * 10^(n-2) - 9 * 10^((n-1)/2)
    // pentru n >= 4 numarul arata astfel:
    // - 161
    // - 9 de n/2 - 2 ori
    // - 1 o data
    // - 0 de (n-1)/2 ori
    if ( n < 4 ) // avem cazuri particulare pentru n < 4 - folosim formula
      fprintf( fout, "%d", rez[n - 1] );
    else {
      fprintf( fout, "161" );
      for ( i = 0; i < n / 2 - 2; i++ )
        fprintf( fout, "9" );
      fprintf( fout, "1" );
      for ( i = 0; i < (n - 1) / 2; i++ )
        fprintf( fout, "0" );
    }
  }
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are el? Primele două puncte au complexitate O(log n), iar al treilea punct este O(k).

Ce concluzie tragem din rezolvarea acestei probleme? Că matematica este esențială, problema devenind banală.

Problema turnuri

Comentarii generale

  1. Felicitări celor ce au reușit o soluție de excepție: Mocanu, Nicola, Fares, Tatomir.
  2. Mențiuni speciale: Hossu, care a combinat drăguț căutările celor două puncte într-o singură parcurgere. Ilie, care a reușit o factorizare foarte drăguță la cerința doi, folosind o matrice de două linii.
  3. Faptul că problema are două cerințe nu înseamnă că trebuie să scrieți două programe! Citirea este destul de lungă, de ce să o scrieți de două ori? De asemenea, dacă avem de căutat un șir de cuburi care începe fie cu galben fie cu albastru nu înseamnă că repetăm codul pentru cele două cazuri. Cine: Badea, Benescu, Chivu, Grecu, Mocanu, Mușat, Petcu, Rebengiuc, Ștefănescu, Togan, Asgari, Dobre, Ipate, Tatomir.
  4. Unii din voi folosiți o sortare aiurită, pe care am mai văzut-o la olimpici. Este ineficientă. Nu o folosiți doar pentru că este mai simplu de memorat. Vreți simplu, nu ați găsit un loc bun la IQ Academy. Cine: Benescu, Burac, Petcu.
  5. Unii dintre voi mă ajută cu comentarii. Vă mulțumesc! Cine: Grecu, Petcu, Rughiniș, Stoian, Voicu, Marcu, Nicu, Tatomir.
  6. Unii dintre voi ați greșit la punctul unu. Care este un punct lejer de lucru cu secvențe, de clasa a cincea, care nici nu necesită vectori. Grav, trebuie să vă pună pe gînduri!
  7. Unii dintre voi nu v-ați prins că înălțimile turnurilor pot depăși întregul. Atenție, este o eroare ușoară care vă poate pierde multe puncte (aici pierdeați doar 6).
  8. Mulți dintre voi fie ați sortat cuburile, fie ați făcut ceva similar cu sortarea. Ea nu era necesară, puteați folosi un vector de frecvență.
  9. Corectați avertismentele de variabile neinițializate! Ele sînt erori, de cele mai multe ori. Le văd foarte des în programele voastre, de multe ori sînt motive pentru care pierdeți puncte.
  10. Avertismente celor ce nu au trimis nici o soluție la această problemă: Iordache.

Comentarii individuale

Grupa de dimineață

  • Badea (100p-95p): Program rezonabil, idee bună, implementare cu mult cod care se repetă. Ai trimis două programe de 100p. Primul cu un sort aiurit, al doilea cu select sort. Fără sortări aiurite la temă, te rog! Vezi comentariul 4. Declari un vector ag[] pe care nu îl folosești. Duplici mult cod la citire, la sortare și la calculul turnului cel mai lung posibil, comentariul 3.
  • Benescu (94p): Program rezonabil la prima cerință, dar foarte încîlcit la a doua, probabil că de aceea nu acoperi toate cazurile. M-ar fi ajutat mult un comentariu cu metoda folosită, bănuiesc că încerci să adaugi cuburi, pe rînd, căutînd mereu cel mai mare cub mai mic ca cel curent si de culoare diferită de cel curent, caz în care algoritmul este corect. Duplici cod la citire, comentariul 3.
  • Burac (100p): Algoritm bun, cod foarte încîlcit cu repetiții și stegulețe. Punctul unu puțin încîlcit la condiția de așezare. Ai nevoie de doar două teste, ca cubul curent să fie mai mic decît cel anterior și culorile să difere. Tu faci o codare a culorilor care nu pare a folosi la nimic. La punctul doi faci o sortare aiurită, vezi comentariul 4. Nu folosi sortări aiurite, te rog. Dacă scrii cod încîlcit scrie te rog un comentariu cu metoda folosită, altfel nu pot decît să o bănuiesc. Văd stegulețe, nu sînt necesare.
  • Calotă (80p-43p) : Program bine scris, ordonat, algoritmul la prima parte e bun, la partea a doua e greșit. Ar fi fost bine să îmi pui un comentariu cu metoda. De ce declari cîte o variabilă pe linie?
  • Chivu (100p): Primul punct este rezonabil și ordonat. Comentariul 3, repeți cod la citire. Nu declara neglijent variabilele, tc (numărul de turnuri) nu are de ce să fie long long. Punctul doi este foarte bine, bravo.
  • Cojocariu (10p): Peridia nimic, gazon rezolvarea din concurs. Temă făcută la minima rezistență. Te joci cu focul. La turnuri, codul tău nu funcționează nici pe exemplul din enunț. Codul conține printf-uri de depanare. Primul punct era banal, dar nu l-ai depanat. Nu te-ai prins că înălțimea poate depăși întregul. Logica primului punct e greșită, nu se poate intra niciodată pe ultimul else. Punctul doi pare rezonabil, dar nu l-ai depanat deloc. Cojocariu, ajung la capătul răbdării. Ești pe drumul sigur de a pierde calificarea la IQ Academy.
  • Grecu (94p): Mulțumesc pentru comentarii! Program corect, care ar fi putut lua 100p. Motivul pentru care ratezi cîteva teste este pentru că nu te-ai prins că înălțimile turnurilor pot depăși întregul. Atenție la tipurile de întregi! Îți va trebui și la clasa a cincea! Ai mult cod repetat, la citire, sortare și căutare soluție punctul 2, vezi comentariul 3.
  • Hossu (0p-83p): Un program bun! Cod destul de ordonat, fără repetiții grave (deși ai spre final două ramuri de if cu conținut identic). Însă ai combinat bine codul astfel încît să nu repeți citirea, iar căutarea funcționează pentru ambele puncte, interesant. Denumești maxv o variabilă care e de fapt un minim, nu face așa ceva te rog, e foarte greu de citit. Unul din motivele pentru care ratezi teste este că înălțimea unui turn poate depăși întregul. Atenție mai mare te rog, e o greșeală banală ce te poate costa mult la olimpiadă!
  • Iordache (0p): nimic? Ce s-a întîmplat? Nu ai făcut trei dintre problemele de la temă, iar la prima n-ai făcut mare lucru.
  • Mocanu (100p): O soluție foarte bună, bravo! Ai folosit un vector de frecvență, bravo din nou. Trebuie însă să mai lucrezi la încîlceală și la scurtarea codului, vezi soluția de mai jos. Repeți cod, vezi comentariul 3.
  • Mușat (22p-41p): Un program bun ca idee, dar pe care nu l-ai depanat pînă la capăt și cu multe repetiții de cod, vezi comentariul 3. Prima parte este bine, o ratezi din cauză că înălțimea turnului poate depăși întregul. Atenție la erori de gîgă! A doua parte este încîlcită și cu același cod repetat de două ori. Dacă puneai măcar niște comentarii aș fi încercat să ți-l depanez. Nu uita că duplicarea de cod te duce la pierdere masivă de puncte.
  • Nicola (44p-95p): Idee foarte bună la ambele puncte. Ai folosit vectori de frecvență, simplu și eficient. Ai grijă, nu te complica degeaba! Codul de căutare în vectorul de frecvență poate fi scris mult mai direct și mai simplu, vezi rezolvarea de mai jos.
  • Petcu (100p): Mulțumesc pentru comentarii! Rezolvare foarte bună la primul punct, ordonată și clară. Dar nu aveai nevoie de vectori, nu-i așa? Repeți citirea, vezi comentariul 3. La punctul doi ideea este bună, sortare și apoi verificare cîte grupe de culoare avem (deși nu ai scris asta clar în comentarii). Dar sortarea este una aiurită, vezi comentariul 4. Foarte ineficientă, este doar ușor de reținut, te rog nu o folosi. Ar fi bine să-i spui și lui Victor să nu o mai predea.
  • Rebengiuc (92p): Un program bun, ordonat, bravo! Ambele puncte rezolvate frumos, la punctul doi ai folosit vectori de frecvență, bravo! Nu deschide fișierele înainte să declari variabilele și nu inițializa variabile la declarare (fișierele). Repeți citirea, vezi comentariul 3. La punctul unu scrii cola + colb == BLUE + YELLOW cînd puteai scrie mai simplu cola != colb. Nu complica codul de dragul unei formule inutile :-) La punctul doi ideea de vectori de frecvență este bună, dar era suficient și mai simplu facă foloseai doar unul. Le fel, formulele sînt nenecesare, complică citirea codului. Cred că la primul punct ratezi teste pentru că nu testezi hmax pe ambele ramuri. Mai exact, un turn de un singur cub foarte mare (latura 500k) poate fi mai înalt decît un turn cu mai multe turnuri unul peste altul.
  • Rughiniș (10p-89p): Mulțumesc pentru comentarii! Programul tău ar fi luat 100p dacă te prindeai că înălțimile turnurilor pot depăși întregul. Repeți cod la citire, vezi comentariul 3. Punctul unu e rezolvat OK, dar cu complicații. Nici nu aveai nevoie de vectori. Punctul doi este corect, bravo! Idee bună, implementare fără prea mari repetiții, în afara sortării.
  • Stoian (72p): Mulțumesc pentru comentarii! La punctul unu ratezi testele 14 și 15 deoarece nu te-ai prins că înălțimile turnurilor pot depăși întregul. Greșeală banală care te-a costat multe puncte. Tot la punctul unu, la final de șir testezi înălțimea maximă, în afara buclei. Dar în loc să testezi val, tu testezi a. Atenție! Ai ratat multe teste la punctul 2 pentru că ai ignorat un avertisment de compilare, greșeală banală care te-a costat multe puncte: cînd sortezi, în interiorul buclei după i, inițializezi variabilele max și poz, dar nu și cc. Vei lua toate testele de punctul doi cu această modificare minoră. Atenție mai mare te rog! Variabila max este de fapt un minim, nu induce în eroare cititorul, este foarte grav. Cu modificările menționate mai sus vei lua 100p.
  • Ștefănescu (12p-30p): Punctul unu este rezolvat corect, codul este clar și ordonat. Dar ai uitat două lucruri minore: nu testezi ultimul turn pentru înălțime maximă, la ieșirea din buclă. Și doi, cînd pornești un nou turn setezi h = 0;. Corect era h = lat;. Atenție mare la lucruri mărunte, pierzi puncte prea ușor! Nu declara variabile simple (fișiere) în afara lui main dacă nu ai nevoie. Ai lăsat printf-uri de depanare în cod, foarte periculos, poți lua TLE, ca acum. Repeți cod la citire, vezi comentariul 3. Ideea punctului 2 este bună, sortare și căutare interclasată. Dar implementarea e defectuoasă, intri în buclă infinită la interclasare. Am încercat să depanezi, dar neavînd comentarii îmi ia prea mult să înțeleg ce ai vrut să faci. Te rog să depanezi tu, folosind testele descărcabile.
  • Togan: (94p): Ideea este foarte bună. Ai fi luat 100p cu ea dacă te prindeai că înălțimea turnurilor poate depăși întregul, greșeală de gîgă și de neatenție. Problema e alta: Togan, codul tău este foarte, dar foarte urît, pînă la necitibil! Scrii fără să gîndești! Încă ai probleme la nivel de clasa a cincea, să pui if-urile exclusive unul pe else-ul celuilalt! Vectorii sînt vraiște, ai un vector de frecvență declarat ca long long cînd putea fi char, nebunie! La primul punct folosești vectori cînd nu sînt necesari. La al doilea punct folosești doi vectori de frecvență cînd era deajuns unul. Repeți cod la citire, vezi comentariul 3.
  • Voicu (40p-95p): Mulțumesc pentru comentarii! Idee bună, cod ordonat, bravo! Repeți citirea, ai multe repetiții și la punctul 2, vezi comentariul 3. Folosești sortare, nu este rău, dar se poate și fără.

Grupa de după-amiază

  • Asgari (100p): Armin, tu scrii în comentarii: "Daca doriti refac codul cu sortare prin selectie, dar mi s-a parut mai interesant asa :)". Să vedem: deși folosești o funcție de bibliotecă pentru sortare, lucru pe care știi că îl interzic, măcar cîștigi ceva? Din borderoul de evaluare rezultă că codul tău este mai lung, mai lent și folosește mai multă memorie decît un cod care nu apelează funcția de sortare. Zici că e mai interesant? În ce fel? În faptul că este mai prost din toate punctele de vedere? Vrei ceva interesant? Scrie o soluție care nu folosește deloc sortare! Dar pentru asta trebuie să gîndești, nu poți să fii un simplu utilizator. Greu, nu? Acestea fiind zise, comentarii la cod:
    • Ai folosit struct în mod incorect, cum era de așteptat: o variabilă int și una char vor ocupa, în fapt, cît două int, dacă le pui în struct. Este exact motivul pentru care nu vă recomand să folosiți struct.
    • Membrii struct-ului sînt denumiți total necorespunzător, x și y, ei fiind de fapt o latură și o culoare.
    • li de tip List *, nu este deloc o listă, ci un vector. Cod care induce în eroare.
    • Funcția de comparație se putea scrie la fel de bine cu ceea ce cunoaștem și ceva mai clar: return (a < b) ? -1 : (a > b);
    • Repeți citirea. Este unul din motivele pentru care codul iese mai lung. Vezi comentariul 3.
    • La prima cerință ai un while care este de fapt un for pentru i de la 1 la n-1.
    • Scrii ++cnt, suma = b; cînd v-am interzis virgula, vorbind în mod explicit despre asta. Lene tipică de olimpic.
    • Dacă vrei să optimizezi acel cod, dacă gîndești în loc să utilizezi, în loc să scrii:
        if( b < a && color != next_color )
          suma += b;
        else
          ++cnt, suma = b;

Poți să observi că una din ramuri poate fi vidă dacă factorizăm adunarea la suma:

        if( b > a || color == next_color ) {
          ++cnt;
          suma = 0;
        }
        suma += b;

Armin: algoritmul tău este bun (dar nu cel mai bun), iar implementarea este rezonabilă. Dar insiști să faci pe șmecherul. În loc să ne impresionezi cu gîndirea și cu un algoritm și o implementare perfectă, folosești lucruri avansate pe care nu le cunoști bine, în vreme ce codul tău arată că nu știi tehnicile de bază și că nu gîndești bine algoritmul.

  • Cadîr (72p-68p): Ai rezolvat punctul greu, dar nu pe cel ușor! Simpatic :-) Programul este ordonat și clar, bun. Nu repeți citirea, în fapt nu ai repetiții, foarte bine! Folosești corect sortarea prin selecție, bine, dar se poate și fără sortare. Ratezi teste din două motive:
    • Ai declarat h ca long long, dar nu și max. Scăpare din neatenție, foarte gravă!
    • Cînd pornești un nou cub, cînd nu poți așeza cubul pe cel din-nainte, scrii h = 0;. Corect era h = hcub[i];, deoarece avem un turn cu acea înălțime, nu de înălțime zero.
  • Dobre (72p-84p): O soluție bună, destul de ordonată și disciplinată. Folosești corect sortarea. Ai o mică repetiție la citire, vezi comentariul 3. Ratezi cîteva teste pentru că nu ai observat că înălțimea turnului poate depăși întregul. O neatenție gravă, la olimpiadă poți să pierzi enorm de multe puncte din cauza asta!
  • Fares (70p-80p): O soluție bună, solidă, cu cod rezonabil. Te-ai complicat în cîteva locuri. Cea mai mare complicație este faptul că, deși ai avut ideea corectă la punctul doi, vectori de frecvență, ai folosit doi, în loc de unul, iar ei sînt de tip întreg, cînd puteau să fie tip caracter. În partea a doua ai scris mult cod aproape identic. Tu voiai să găsești cel mai lung lanț de cuburi ce alternează ca culoare și ai scris cod aproape identic pentru două cazuri, cînd lanțul începe cu galben sau cu albastru.
  • Ilie (100p): Un program ordonat și clar, care nu repetă cod. La punctul doi ai factorizat codul foarte drăguț, evitînd repetiția codului. Din păcate algoritmul nu este optim: în locul căutării cuburilor de la punctul doi puteai folosi un vector de frecvență, după laturile cubului.
  • Ipate (94p-95p): Un program scurt și clar, în care metoda folosită se înțelege foarte bine. Cea mai mare obiecție este la punctul 2, unde algoritmul nu este optim: în locul sortării puteai folosi un vector de frecvență. În rest mai ai mici imperfecțiuni:
    • Dat fiind că nu te interesează ca culorile să fie codificate cu 1 și 2 ci doar să fie diferite între ele puteai, la punctul doi, la citire, să scrii pur și simplu h[i][1] = fgetc( fin );
    • La punctul doi la final calculezi un inalt care este inutil, nu e folosit nicăieri
    • Ai o mică repetiție de citire, între cele două puncte, vezi comentariul 3
  • Marcu (72p): Mulțumesc pentru comentarii! O soluție scurtă, clară, ordonată, care se poate înțelege foarte repede. Ai rezolvat punctul 2, cel greu, dar nu punctul unu, simpatic! :-) Obiecția minoră este la punctul unu, unde ai uitat lucruri mărunte: atunci cînd nu poți așeza cubul pe masă trebuie să resetezi h: h=l[i];. Iar la finalul secvenței de cuburi trebuie să mai testezi o dată înălțimea, să nu fie maximă. Iar înălțimea, precum și maximul, pot depăși întregul, deci trebuie declarate long long. Mărunțișurile acestea ți-au furat multe puncte, trebuie neapărat să fii mai atentă! Cu aceste trei modificări vei lua 100p. Însă obiecția majoră este la punctul 2, unde algoritmul nu este optim: în locul sortării puteai folosi un vector de frecvență. O altă mică imperfecțiune, la punctul doi scrii if(l[i]<l[i-1] && c[i]!=c[i-1])//daca se poate plasa cubul k pe k-1, dar deoarece cuburile sînt sortate prima condiție este inutilă, este mereu adevărată.
  • Nicu (p): Mulțumesc pentru comentarii! O soluție scurtă, clară, ordonată și ușor de înțeles. La punctul doi ai folosit sortarea prin selecție foarte corect. Se poate, însă, și fără, folosind un vector de frecvență. Ca mici obiecții de eleganță, la punctul unu, while-ul este de fapt un for. La fel și la punctul doi. Un program bun, bravo!
  • Stancu (40p-38p): Ai rezolvat punctul unu foarte corect și ordonat. Este un program ușor de citit. Ai luat tot punctajul pentru acest punct. Inclusiv te-ai prins, cum ai scris și tu în comentariu, că înălțimea unui turn poate depăși întregul. Păcat că nu ai încercat mai serios să rezolvi și punctul 2
  • Tatomir (100p): Mulțumesc pentru comentarii! O rezolvare scurtă, clară, concisă, ușor de citit și cu algoritm optim, bravo! Mici neeleganțe ce ar fi bine să le corectezi:
    • Repeți codul de citire, care este destul de semnificativ. Vezi comentariul 3.
    • Declari vectorul de frecvență de întregi, cînd putea fi de caractere, o risipă mare cînd e vorba de 500000 de elemente.
    • Refolosești maxx la punctul doi, ceea ce nu e bine deoarece el este de tip long long, iar pentru punctul doi e suficient un întreg.
    • Ai complicat codul codînd culorile ca -1 și 1. Puteai să le stochezi ca atare în vector, apoi căutai elemente diferite de ultima culoare, pe care o actualizai la fiecare cub adăugat la șir.
  • Teodorescu (86p-90p): Program destul de clar și ușor de citit. Nu repeți cod, bun. Ar fi fost bun un comentariu în legătură cu metoda folosită la punctul doi. La punctul unu folosești degeaba un vector extra, cel de înălțimi. Nu aveai nevoie de el. La punctul doi ai rezolvat cu o metodă pătratică, nu este optim, vezi te rog soluția de mai jos, cu un vector de frecvență.

Rezolvare

Problema turnuri a fost dată la OJI 2018 clasa a 6a. Ea are două cerințe.

Prima cerință este mai greu de înțeles decît de rezolvat. În fapt, ea cere lungimea celei mai mari secvențe de cuburi aflate unul lîngă altul pe bandă care se pot așeza fiecare pe cel din-naintea lui. Vom căuta deci cuburi descrescătoare ca laturi și de culori alternante. Un algoritm de clasa a cincea la început, ce nu necesită vectori.

A doua cerință este interesantă: ea cere să reordonăm cuburile astfel încît secvența de la punctul unu să fie maximală.

Cum rezolvăm acest punct? Vom aplica două reguli generale de rezolvare a oricărei probleme:

  • Dacă introducem o ordine în obiectele de la intrare de obicei problema se simplifică.
  • Trebuie să observăm toți operatorii (mutările) pe care le putem face.

Să începem cu prima regulă: să sortăm descrescător cuburile după latură. Sortarea este unică, deoarece cuburile au laturi diferite. Să ne gîndim acum la soluție: este clar că cuburile din soluție se vor afla în aceeași ordine atît în soluție cît și între cuburile ordonate. În soluție trebuie să fie una după alta, pe cînd între cuburile ordonate el mai pot avea și alte cuburi printre ele.

Ce înseamnă acest lucru? Că dacă să selectăm orice șir de cuburi din șirul ordonat, chiar și pe sărite, dar care respectă condiția să se poată face turn, atunci acel șir poate fi soluție: îl vom extrage din șir și-l vom pune la începutul soluției.

În concluzie, pentru a rezolva punctul doi trebuie să găsim cel mai lung subșir de cuburi, pe sărite, care se pot așeza unul peste altul.

La prima vedere pare greu. Cunoscătorii s-ar putea gîndi imediat la o soluție cu programare dinamică. Ea va duce la o complexitate O(n2), care este foarte posibil să se încadreze în timp. Dar să nu ne aruncăm, soluția trebuie să fie de clasa a 6a, nu? :-)

Să observăm încă un lucru:

  • Orice cum am selecta în subșirul ordonat, următorul cub pe care îl vom selecta trebuie să aibă culoare diferită.

Ce înseamnă acest lucru? Că dacă avem un grup de cuburi la rînd, de aceeași culoare, putem selecta oricare dintre ele! Într-adevăr, selecția nu va afecta lungimea șirului final. Putem, deci, înlocui grupele de cuburi consecutive de aceeași culoare cu un singur cub din grupă, oricare. Dacă aplicăm această operație întregului șir ordonat ce vom obține? Doar cuburi de culori alternante. Aceasta va fi, deci, o soluție posibilă!

În concluzie, punctul doi ne cere să aflăm numărul de alternări ale culorilor în șirul ordonat al cuburilor. Banal, nu? :-)

Observație: ar părea că avem nevoie să sortăm cuburile. În fapt, toate soluțiile comisiei se bazează pe sortare, ba chiar unele din ele apelează funcția de sortare de bibliotecă. Frumos! Ei ne îndeamnă, deci, ca în clasa a șasea, să devenim utilizatori de algoritmi, nu creatori. Mai mult, să fim utilizatori de algoritmi care depășesc nivelul programei de clasa a 6a. Cumva nu reușesc să înțeleg acest lucru.

Desigur că nu avem nevoie de sortare. Laturile cuburilor fiind suficient de mici putem folosi un vector de frecvență.

Iată o soluție:

#include <stdio.h>

#define MAXL 500000

char cul[MAXL];

int main() {
  FILE *fin, *fout;
  int c, n, i, l1, l2, c1, c2, nt;
  long long h, hmax;

  fin = fopen( "turnuri.in", "r" );
  fscanf( fin, "%d%d", &c, &n );
  fscanf( fin, "%d ", &l1 ); // latura primului cub
  c1 = fgetc( fin );         // culoarea lui
  cul[l1 - 1] = c1; // pt pct 2: depunem culoarea in vect frecv al laturilor
  hmax = h = l1;    // initializam inaltimea curenta si cea maxima la latura
  nt = 1;           // numarul de turnuri formate pina acum este unu
  for ( i = 1; i < n; i++ ) {  // citim restul de n-1 cuburi
    fscanf( fin, "%d ", &l2 ); // citim latura cubului
    c2 = fgetc( fin );         // si culoarea lui
    cul[l2 - 1] = c2; // pt pct 2: depunem culoarea in vect frecv al laturilor
    if ( l2 > l1 || c2 == c1 ) { // nu putem adauga la turnul anterior
      h = 0; // resetam inaltimea turnului curent la 0 (vom adauga l2 mai jos)
      nt++;  // incepem un turn nou
    }
    h += l2; // turnul curent se inalta cu l2
    if ( h > hmax )
      hmax = h;
    
    l1 = l2; // memoram ultimul cub citit
    c1 = c2;
  }
  fclose( fin );

  // punctul 2 - rearanjare astfel incit sa avem maxim de cuburi
  // numaram grupele alternative de albastru si galben
  c1 = n = 0;
  for ( l1 = 0; l1 < MAXL; l1++ )
    if ( cul[l1] != 0 && cul[l1] != c1 ) { // culoarea difera de cea anterioara
      n++;          // putem adauga un cub la turn
      c1 = cul[l1]; // schimbam culoarea curenta
    }
  
  fout = fopen( "turnuri.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%d %lld\n", nt, hmax );
  else
    fprintf( fout, "%d\n", n );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Este destul de clar că ea este O(n + latmax) unde latmax este latura maximă a unui cub.

Problema gazon

Problema gazon a fost dată la ONI 2018 clasa a 6a. Ea este o problemă strict de organizare și atenție, ea necesitînd să navigăm cu succes prin multiple cazuri particulare.

Problema cere să pavăm o suprafată cu dale. Putem tăia dalele, dar o singură dată. Dorim să refolosim bucățile de dale la maxim.

Vom aplica două reguli generale de rezolvare a oricărei probleme:

  • Dacă introducem o ordine în obiectele de la intrare de obicei problema se simplifică.
  • Trebuie să observăm toți operatorii (mutările) pe care le putem face.

Pornind cu regula a doua, să nu ratăm operatori! De exemplu, înd tăiem o dală este posibil:

  • Ca una din bucăți să se potrivească pe o latură, iar cealaltă bucată pe cealaltă latură.
  • Ca ambele bucăți să se potrivească pe aceeași latură
  • Ca ambele bucăți să se potrivească pe ambele laturi

Toate acestea combinat cu faptul că putem să nu avem nevoie de dale tăiate pe una sau pe ambele laturi complică mult hățișul de cazuri. În fapt, toate soluțiile oficiale au peste 100 de linii (care scrise corect, o instrucțiune pe linie, se transformă în peste 120 linii). Pare că comisia nu s-a descurcat prea bine în hățișul de cazuri al propriei probleme, dat fiind că soluția poate avea sub 50 de linii.

Să aplicăm prima regulă: să introducem o ordine. Cum putem face acest lucru? Calculînd lățimile dalelor parțiale necesare pe cele două laturi și combinîndu-le dacă ele sînt identice. După această operație vom avea:

  • zero dale necesare, dacă zona se poate pava perfect
  • un tip de dale necesare, cînd fie doar o latură necesită pavare extra, fie dalele parțiale pe ambele laturi sînt identice
  • două tipuri de dale necesare, cînd ambele laturi necesită dale parțiale și ele sînt diferite

În realitate putem trata cazul cu zero dale suplimentare ca un caz particular al cazului cu un singur tip de dale.

Deoarece dalele pot fi tratate la fel și deoarece putem avea 0, 1, sau 2 tipuri, vom folosi doi vectori de două elemente pentru a simplifica codul:

  • ddale[i] este dimensiunea (lățimea) dalei i
  • ndale[i] este numărul de dale de tip i

Să presupunem că avem acești vectori. Atunci vom avea trei cazuri:

  • Avem două tipuri de dale iar cele două tipuri pot forma o dală completă. În acest caz vom avea nevoie de numărul maxim de dale dintre cele două tipuri pentru a obține necesarul de dale extra.
  • Avem zero, unul sau două tipuri de dale, dar care nu se pot combina între tipuri diferite. În acest caz vom lua la rînd tipurile de dale și vom testa dacă se pot combina în cadrul tipului. Aici vom avea iarăși două cazuri:
    • Dacă se pot combina în cadrul tipului (dala parțială este jumate din dala mare), vom aduna acel număr de dale împărțit la doi.
    • În caz contrar vom aduna chiar numărul de dale de acel tip

Iată o soluție bazată pe aceste idei:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int c, a, b, d, cd, ct, cm; // valorile de intrare
  int n, nl, nc, dv, dh, nm, nt, i;
  int ndale[2]; // ndale[i] = numarul de dale de tip i
  int ddale[2]; // ddale[i] = latimea unei dale de tip i
  long long di, amin;

  fin = fopen( "gazon.in", "r" );
  fscanf( fin, "%d%d%d%d%d%d%d", &c, &a, &b, &d, &cd, &ct, &cm );
  fclose( fin );

  // punctul 1 - dale intregi si aria minima ramasa neacoperita
  nl = a / d;     // numarul de dale pe linii
  nc = b / d;     // numarul de dale pe coloane
  di = nl * (long long)nc; // numarul de dale intregi
  dv = a % d;     // dimensiunea verticala ramasa jos
  dh = b % d;     // dimensiunea orizontala ramasa la dreapta
  amin = dv * (long long)dh; // aria ramasa neacoperita

  // punctul 2 si 3 - numarul minim de dale necesare, si numarul de taieturi
  // avem nc dale de dimensiune dv x d
  // avem nl dale de dimensiune  d x dh
  // incercam sa le combinam cit mai bine
  // asezam numarul de dale precum si dimensiunea mica a lor intr-un vector
  n = 0;  // numarul de tipuri de dale extra
  nm = 0; // numarul de dale extra de montat
  if ( dh > 0 && nl > 0 ) { // adaugam doar daca avem cel putin o dala 
    ndale[0] = nl;          // de arie nenula
    ddale[0] = dh;
    n++;
    nm += nl; // avem de montat nl dale
  }
  if ( dv > 0 && nc > 0 ) { // adaugam doar daca avem cel putin o dala 
    ndale[n] = nc;          // de arie nenula
    ddale[n] = dv;
    n++;
    nm += nc; // avem de montat nc dale
  }

  nt = 0;       // numarul de taieturi (egal cu numarul de dale extra)
  if ( n > 1 && // daca avem dale atit pe orizontala cit si pe verticala si
       ddale[0] == ddale[1] ) { // dimensiunile lor sint egale, le combinam
    ndale[0] += ndale[1];
    n = 1;
  }

  // in acest moment avem 1 sau 2 tipuri de dale
  if ( n == 2 && ddale[0] + ddale[1] == d )          // daca se pot combina
    nt += ndale[0] > ndale[1] ? ndale[0] : ndale[1]; // taiem maximul
  else // se pot combina cel mult in cadrul aceluiasi tip
    for ( i = 0; i < n; i++ )
      if ( 2 * ddale[i] == d )
        nt += (ndale[i] + 1) / 2; // nr de taieturi e aproximativ jumate
      else
        nt += ndale[i]; // altfel le taiem pe toate

  fout = fopen( "gazon.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%lld %lld\n", di, amin );
  else
    fprintf( fout, "%lld\n", c == 2 ? di + nt :
             (di + nt) * cd + nt * (long long)ct + (di + nm) * cm );
  fclose( fout );

  return 0;
}

Desigur că soluția, neavînd bucle dependente de intrare, este O(1) atît ca timp cît și ca memorie.

Problema peridia

Comentarii generale

  1. Felicitări celor ce au reușit o rezolvare cu rotații, cu cod nerepetitiv, independent de direcție: Rebengiuc, Fares, Ilie, Marcu, Nicu.
  2. Cei ce au încercat rotații, dar nu au reușit o implementare nerepetitivă, totuși, felicitări pentru încercare: Badea, Burac.
  3. Mulți dintre voi au declarat un vector de un milion de elemente! Nu știu dacă v-a confuzat faptul că matricea avea un milion de elemente, sau pur și simplu ați greșit un zero, dar vectorul avea, din enunțul problemei, fie 100 000 de elemente dacă era un vector de frecvență, fie 10000 de elemente dacă țineați minte chiar elementele nenule din matrice. Este o eroare foarte gravă, din cauza căreia veți lua zero la o astfel de problemă la olimpiadă. A folosi de zece ori mai multă memorie decît este cazul este de neacceptat la IQ Academy!
  4. În continuare, mulți din cei ce reușiți să treceți toate testele în concurs trimiteți aceeași sursă și la temă, în loc să continuați să gîndiți la ea, sau să căutați un algoritm sau un program mai bun. Este și cazul la peridia, unde cei care ați luat 100p în concurs ați trimis un program fie fără rotații, fie cu repetiții, fie cu conversii urîte de la litera direcției la codificarea ei. Foarte rău.

Rezolvare

Problema peridia este o problemă clasică de simulare creată de un elev cu doi ani mai mare ca voi. Ea este o problemă de simulare relativ clasică, în matrice, în care ne ajută mult să folosim bordare și vectori de direcție. Partea deosebită este rotația zarului. Este singura parte pe care o voi detalia mai jos, restul fiind clasice și discutate.

Rotația zarului

Putem face această rotație "de mînă", nu-i așa? Caz în care va trebui să scriem cam același cod de patru ori, pentru fiecare direcție. Iată, de exemplu, codul lui Tudor Voicu:

        X=x; Y=y; Z=z; lin=L; col=C;
        switch(s[i]) {
            case 'N':
                c=x;
                x=z;
                z=7-c;
                L--;
                break;
            case 'E':
                c=x;
                x=y;
                y=7-c;
                C++;
                break;
            case 'S':
                c=z;
                z=x;
                x=7-c;
                L++;
                break;
            default : /// 'V'
                c=y;
                y=x;
                x=7-c;
                C--;
        }
        if(L>=0 && L<n && C>=0 && C<n)
            a[L][C]+=7-x;
        else
            x=X,y=Y,z=Z,L=lin,C=col;

Observăm o mică neeleganță, anume că întîi se execută mutarea, iar apoi, dacă iese în afara tablei, o anulăm, lucru pentru care trebuie să ținem copii ale stării inițiale. Dar, în principiu, codul este corect și cam așa ne-am putea gîndi să rezolvăm rotațiile zarului.

Aceasta în absența vectorilor de direcție! Cum am putea face să nu repetăm cod? Oare nu putem face codul de rotație independent de direcție?

Desigur că da. Să observăm că o rotație constă în schimbarea celor șase valori ale fețelor pe alte poziții. O putem deci, descrie, printr-un vector de rotație, în care v[i] este poziția din care luăm noua valoare a feței i. Astfel, putem scrie ceva de genul:

for ( i = 0; i < 6; i++ )
  zar2[i] = zar1[v[i]];

La final zar2 va conține rotația lui zar1. Ne putem imagina patru astfel de vectori de rotație, pentru cele patru direcții. Pentru a-i putea accesa în funcție de direcție îi vom ține într-o matrice cu patru linii. Ea arată astfel:

int rot[4][6] = { // cele patru rotatii, cum provin valorile noului zar         
  { 1, 3, 2, 4, 0, 5 }, // rotatie E                                            
  { 2, 1, 3, 5, 4, 0 }, // rotatie N                                            
  { 4, 0, 2, 1, 3, 5 }, // rotatie V                                            
  { 5, 1, 0, 2, 4, 3 }  // rotatie S                                            
};
  • Aici am codat cele șase valori astfel, în ordine: sus, stînga, față, jos, dreapta, spate.
  • Am considerat direcțiile ca fiind, în ordine: est, nord, vest, sud.

Vom mai folosi un artificiu pe care l-am mai folosit în trecut pentru a nu copia vectori atunci cînd calculăm unul pe baza celuilalt în mod repetat: vom ține cei doi vectori zar ca o matrice de două linii. Cînd calculăm rotația, noul zar, vom calcula din zar[1-z][i] pe baza lui zar[z][i]. Apoi vom efectua z = 1 - z.

Pentru a afișa valorile din matrice în ordine crescătoare vom folosi un vector de frecvență, pentru a le sorta, valorile fiind mici.

Iată un program posibil:

#include <stdio.h>

#define MAXN 1000
#define MAXVAL 100000

int rot[4][6] = { // cele patru rotatii, cum provin valorile noului zar
  { 1, 3, 2, 4, 0, 5 }, // rotatie E
  { 2, 1, 3, 5, 4, 0 }, // rotatie N
  { 4, 0, 2, 1, 3, 5 }, // rotatie V
  { 5, 1, 0, 2, 4, 3 }  // rotatie S
};

char d2c[] = "ENVS"; // codificarea directiilor cardinale
int c2d[128];        // cd2['V'] este 2, pozitia lui 'V' in vectorul d2c[]
int dl[4] = { 0, -1,  0, 1 }; // diferentele pe linie si coloana
int dc[4] = { 1,  0, -1, 0 }; // pentru cele patru directii

int zar[2][6];       // codificat (sus, stinga, fata, jos, dreapta, spate)
int t[MAXN + 2][MAXN + 2]; // tabla de joc
int f[MAXVAL + 1];         // frecventele tablei de joc

int main() {
  FILE *fin, *fout;
  int n, k, i, j, d, l, c, z;

  for ( d = 0; d < 4; d++ ) // construim vectorul c2d[]
    c2d[d2c[d]] = d;
  
  fin = fopen( "peridia.in", "r" );
  fscanf( fin, "%d%d%d%d%d ", &n, &zar[0][0], &zar[0][1], &zar[0][2], &k );
  for ( i = 0; i < 3; i++ )  // completam celelalte trei fete ale cubului
    zar[0][i + 3] = 7 - zar[0][i];

  for ( l = 0; l <= n + 1; l++ ) // bordam matricea cu -1
    t[l][0] = t[l][n + 1] = t[0][l] = t[n + 1][l] = -1;
  
  // incepem simularea
  f[t[l = 1][c = 1] = zar[z = 0][3]] = 1; // initializari pornire
  for ( i = 0; i < k; i++ ) {
    d = c2d[fgetc( fin )];                // rotatie in directia d
    if ( t[l + dl[d]][c + dc[d]] >= 0 ) { // daca nu iesim din matrice
      for ( j = 0; j < 6; j++ )           // rotim cubul
        zar[1-z][j] = zar[z][rot[d][j]];
      f[t[l += dl[d]][c += dc[d]]]--;     // scadem din numarul de aparitii
      f[t[l][c] += zar[z = 1 - z][3]]++;  // adunam la nr ap ale nr-lui de jos
    }
  }
  fclose( fin );

  fout = fopen( "peridia.out", "w" );
  for ( i = 1; i <= MAXVAL; i++ ) // afisam indicii elementelor nenule din f[]
    for ( j = 0; j < f[i]; j++ )
      fprintf( fout, "%d ", i );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Simularea este O(1) per rotație, deci O(K). Parcurgerea vectorului de frecvență este O(valmax), unde valmax este valoarea maximă pe tablă. Presupunînd că zarul imprimă doar valoarea 6 în aceeași celulă valmax va fi maxim 6K. De aici rezultă complexitatea parcurgerii ca fiind O(K), care este și complexitatea totală a algoritmului.

Memoria folosită este tabla și vectorul de frecvență, adică O(N2 + K).


Rezolvări aici [1]

Lecție

Calculul multiplicității unui număr prim în n!

Matematicianul Adrien-Marie_Legendre a descoperit că multiplicitatea (exponentul) unui număr prim p care apare în descompunerea în factori primi a lui n! poate fi exprimată exact ca:

Exp(p,n!)=\left\lfloor {\frac  {n}{p}}\right\rfloor +\left\lfloor {\frac  {n}{p^{2}}}\right\rfloor +\left\lfloor {\frac  {n}{p^{3}}}\right\rfloor +\cdots =\sum _{{i=1}}^{{\infty }}\left\lfloor {\frac  {n}{p^{i}}}\right\rfloor .

Acest fapt se bazează pe numărarea factorilor p ai întregilor de la 1 la n. Numărul multiplilor lui p în numerele de la 1 la n este \textstyle \left\lfloor {\frac  {n}{p}}\right\rfloor ; dar această formulă numără numerele cu doi factori p o singură dată. De aceea trebuie să mai numărăm încă \textstyle \left\lfloor {\frac  {n}{p^{2}}}\right\rfloor factori ai lui p. În mod similar pentru trei, patru, cinci factori, pînă la infinit. Însă suma este finită deoarece p i este mai mic sau egal cu n într-un număr finit de valori ale lui i, drept care funcția parte întreagă va fi zero pentru toate celelalte valori.

Cînd scriem programul pentru calculul exponentului ne vom opri la acel i pentru care pi > n.

Calculul multiplicității unui număr prim la o putere în n!

Este simplu de demonstrat că dacă avem un număr prim p la o putere k atunci multiplicitatea lui pk în n! este

Exp(p^{k},n!)={\frac  {Exp(p,n!)}{k}}

Calculul multiplicității unui număr oarecare în n!

Este simplu să arătăm că dacă avem un număr a a cărui descompunere în factori primi este

a = p1k1 • p2k2 • … • pmkm

atunci multiplicitatea (exponentul) lui a în n! este

Exp(a,n!)=min(Exp(p_{1}^{{k_{1}}},n!),Exp(p_{2}^{{k_{2}}},n!),\ldots ,Exp(p_{m}^{{k_{m}}},n!))

sau

Exp(a,n!)=min({\frac  {Exp(p_{1},n!)}{k_{1}}},{\frac  {Exp(p_{2},n!)}{k_{2}}},\ldots ,{\frac  {Exp(p_{m},n!)}{k_{m}}})

Temă

Tema 22 clasa a 6a

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

Rezolvări aici: [2]