Clasa a VI-a lecția 28 - 28 mar 2019

From Algopedia
Jump to: navigation, search

Anunțuri

Concurs duminică înlocuit cu Infotehnium 2019

Deoarece sîmbătă se desfășoară concursul Infotehnium 2019 nu vom avea concurs duminică la varena.

Tema lecției va consta din problemele Infotehnium 2019

Concursul Infotehnium se va desfășura sîmbătă 30 martie la școala 164, ora 9:00AM pentru cei de a șasea, 10:30AM pentru cei de a cincea. Problemele de la clasa a șasea vor constitui tema pentru joia viitoare. Ele vor fi adăugate la temă după concurs, sîmbătă seară sau luni diminteață.

Instructor invitat

Lecția de joi 4 aprilie va fi ținută de Cătălin Frâncu. Vă rog să vă comportați civilizat.

Tema 25 - rezolvări

Problema album

Problema album a fost dată la OJI 2019 clasa a 6a.

Ea are o rezolvare destul de simplă, cu forță brută și diverse variante optimizate. Să discutăm o parte din ele.

Soluție forță brută

În această soluție simulăm enunțul. Fiecare copil ia primul sticker rămas pe masă, apoi culege stickerele care se potrivesc cu el. Pentru această soluție:

  • Vom memora stickerele într-un vector.
  • Vom parcurge vectorul, în ordine, căutînd elemente nenule.
  • Cînd găsim un element nenul îi calculăm cifrele maxime.
  • Apoi parcurgem restul vectorului, căutînd acele două cifre în alte numere nenule.
  • Cînd găsim astfel de numere, le adăugăm la copilul curent și apoi le setăm la zero, pentru a nu mai fi luate în calcul la o parcurgere următoare.

Ce complexitate are această soluție?

Ea depinde foarte mult de numărul de parcurgeri ale vectorului. Cîte parcurgeri putem avea? Să observăm următoarele:

  • La fiecare parcurgere vom căuta două cifre, cf1 și cf2, pereche neordonată.
  • Toate acele numere vor fi eliminate din șir, prin setarea lor la zero.
  • Atunci, la următoarele parcurgeri nu vom mai putea căuta aceeași pereche de cifre.

Rezultă că numărul de parcurgeri este numărul posibil de perechi de cifre neordonate distincte. Acest număr este Gauss(Σ+1), unde Σ este mărimea alfabetului, adică 10, în cazul nostru, deoarece avem zece cifre. Cu alte cuvinte vom avea O(Σ2) parcurgeri. Vom parcurge O(n) elemente. Pentru fiecare element vom separa cifrele sale, deci vom face O(log MAXS) împărțiri. Rezultă o complexitate totală de O(n·Σ2·log MAXS).

Se încadrează în timp? Să facem înlocuirile: știm că Σ2 este, în fapt, circa 54, iar log MAXS este, în fapt, 6. Numărul de operații va fi 800000·54·6 ≈ 260 milioane. Deoarece vorbim de împărțiri înmulțim cu 30, obținînd circa 7.8 miliarde operații. Deci această soluție nu ar trebui să se încadreze în timp pentru teste mari. Am generat un test maximal pe care această soluție a durat 4.3s, iar soluția oficială a autoarei a durat 6.8s.

Cu toate acestea, surpriza emisiunii este că soluția forță brută, scrisă îngrijit, lua 100p la ONI. Cum este posibil acest lucru? Deoarece testele oficiale sînt departe de a fi maximale. Cel mai mare test este de circa cinci ori mai mic decît cel maximal, în termen de număr de operații.

Să recapitulăm: una dintre soluțiile oficiale ale autoarei, doamna Violeta Grecea, nu trece testul maximal, promis de enunț! Dar acest lucru este mascat de faptul că testele nu sînt maximale.

De ce a decis comisia să nu folosească teste maximale? Nu putem ști. Cel mai adesea motivele lor sînt bune, la origine:

  • Să nu chinuim bieții copilași.
  • Să se încadreze în timp și soluții mai puțin bine scrise.
  • Este totuși OJI, să nu le dăm probleme ca la ONI.

Toate aceste motive sînt OK, dar comisia uită un lucru esențial:

Inversiunea valorilor: o problemă care promite un nivel elevat și nu îl respectă va defavoriza elevii buni și îi va favoriza pe cei slabi.

Acest lucru se întîmplă deoarece un elev bun își va da seama că forța brută nu se încadrează în timp și va căuta un algoritm mai bun, reușind sau nu și pierzînd puncte și timp. Un elev mai slab nu va ști să scrie decît forța brută, cu care va lua 100p, cîștigînd timp pentru a se gîndi la celelalte probleme din set.

Cuvînt deschis pentru comisia științifică: dragi profesori! Sînteți cei mai buni dintre cei buni, reprezentînd profesorii din țară la cel mai înalt nivel posibil. Nu puteți, nu aveți voie să faceți astfel de greșeli! Sînteți închiși în turnul vostru de fildeș, nimeni nu poate ajunge la voi pentru o discuție sau pentru a contesta validitatea problemelor și a testelor. Gîndiți-vă la elevii pe care este de presupus să îi îndrumați pe calea deloc ușoară a informaticii. Ei vor constata că această problemă este incorectă și se vor îndrepta către alte domenii, unde olimpiada este corectă. Olimpiada de informatică trebuie să fie meritorie! În momentul cînd elevii iau puncte nemeritat, distrugeți însuși motorul, însăși baza, însăși fundația acestei olimpiade!

Soluție semi-forță brută

Putem aduce forța brută să se încadreze în timp, cu o modificare minimală?

Motivul principal pentru care forța brută nu se încadrează în timp este faptul că face multe împărțiri. Putem să păstrăm complexitatea algoritmului, dar să reducem numărul de împărțiri? Desigur că da. Să observăm că noi nu folosim acele numere drept cantități, ci doar ca înșiruiri de cifre. Mai mult, aceste cifre ni se dau la intrare! Deci de ce să le citim ca numere, numai ca pentru apoi să ne dăm singuri de lucru să extragem cifrele lor?

O soluție care nu face nici o împărțire va citi numerele la intrare caracter cu caracter și va memora pentru fiecare număr cifrele sale. Vom avea, astfel, o matrice de n × 6 caractere. Restul algoritmului rămîne la fel. Soluția devine imediat de 30 de ori mai rapidă, plus că citirea va fi și ea de circa 4 ori mai rapidă. Cele circa 260 milioane de operații se vor încadra chiar și în 0.5s cam pe orice calculator.

Soluții elegante

Se poate mai bine? Desigur!

O primă idee ar fi să tratăm problema puțin invers: să facem o singură parcurgere, iar pentru fiecare număr să ne întrebăm dacă a fost cules și de cine. Pentru aceasta trebuie să memorăm într-un vector șirul de numere alese de copii, cele originale, pe baza cărora le alegem pe următoarele. În fapt, e deajuns să ținem minte doar cele două cifre maximale. Apoi, pentru fiecare număr citit, parcurgem vectorul de cifre maximale și vedem dacă la vreuna din poziții conține ambele cifre. Dacă da, el este luat de acea poziție. Dacă poziția este pară, este unul din copii, altfel este celălalt.

Ce complexitate are această soluție? Deoarece putem avea maxim 54 de numere în șirul de numere alese, vom avea aceeași complexitate, O(n·Σ2·log MAXS). De ce funcționa mai bine? Deoarece vom folosi mult mai puțină memorie, pentru cei doi vectori de cifre maximale, respectiv O(Σ2). Este vorba de acel cache, despre care am mai vorbit. Pentru o implementare eficientă vom construi pentru fiecare număr vectorul de frecvență al cifrelor sale. Astfel vom putea testa dacă două cifre fac parte din acel număr în O(1).

O a doua idee ar fi să mergem și mai departe: oare nu putem să scăpăm de o căutare liniară într-un vector de 54 de elemente? Am putea să facem două modificări:

  • Să creăm un vector de frecvență al cifrelor maximale. În loc să avem un vector cu acele cifre, putem să procedăm altfel: date cifrele maximale cf1 și cf2, cu cf1 ≤ cf2, vom marca în tur[cf1 * 10 + cf2] numărul turului în care au fost selectate acele cifre maximale.
  • Pentru fiecare număr din șir vom crea toate grupele de două cifre și pentru fiecare grupă vom căuta în vectorul de frecvență dacă există un tur, luînd turul minimal.

Ce complexitate are această soluție? Pentru fiecare număr vom face atîtea calcule cîte perechi putem forma, adică O(log2MAXS). Soluția va avea complexitatea O(n·log2MAXS). Făcînd înlocuirile, avem acel log drept perechile formate din 6 cifre, deci 15 posibilități, pe care le vom înmulți cu 800000, obținînd 12 milioane de operații, un număr și mai mic, care cred că este și optim. Memoria folosită va fi un vector de 100 de elemente.

Iată o soluție bazată pe aceste idei, care încearcă să implementeze ambele puncte eficient (76 linii de program):

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

int tur[100];  // tur[x] = turul la care a fost selectat numarul x = ab
int nstick[2]; // nstick[x] = numarul de stickere ale copilului x
int nume[2] = { 'R', 'V' }; // numele celor doi copii, in ordine inversa
int cifre[6]; // cifrele unui numar

int main() {
  FILE *fin, *fout;
  int n, c, i, j, ch, max1, max2, x, t, ntur, ncf;

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

  for ( i = 0; i < 100; i++ ) // pentru cerinta 2, economisim un test
    tur[i] = n + 1;
  
  i = 0;
  if ( c == 1 ) // cerinta 1 (cele mai mari doua cifre din ultimul sticker)
    for ( ; i < n - 1; i++ ) // citim in gol (si ignoram) n-1 numere
      while ( fgetc( fin ) != ' ' ); // inca o cifra?

  // cerinta 1 + cerinta 2 (cite stickere aduna fiecare din copii)
  ntur = 1;
  for ( ; i < n; i++ ) {
    ncf = 0;
    t = n + 1;
    while ( isdigit(ch = fgetc( fin )) ) { // inca o cifra?
      // testam cifra cu toate celelalte din-naintea ei
      ch -= '0';
      for ( j = 0; j < ncf; j++ ) {
        // calculam numarul din doua cifre (ch, cifre[j])
        // astfel incit cele doua cifre sa fie in ordine crescatoare
        x = cifre[j] > ch ? ch * 10 + cifre[j] : cifre[j] * 10 + ch;
        if ( tur[x] < t )
          t = tur[x];
      }
      cifre[ncf] = ch; // stocam cifra curenta in vectorul de cifre
      ncf++;
    }

    if ( t > n ) { // daca numarul nu a fost luat intr-un tur anterior
      max1 = max2 = 0;
      for ( j = 0; j < ncf; j++ )
        if ( cifre[j] > max2 ) { // calculam cele mai mari doua cifre
          max1 = max2;
          max2 = cifre[j];
        } else if ( cifre[j] > max1 )
          max1 = cifre[j];

      tur[10 * max1 + max2] = t = ntur; // avem un nou tur
      ntur++;
    }
    nstick[t % 2]++; // il adunam la copilul ce detine stickerul
  }
  fclose( fin );

  fout = fopen( "album.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%d %d\n", max1, max2 );
  else {
    t = 1;
    if ( nstick[0] > nstick[1] )
      t = 0;
    fputc( nume[t], fout );
    if ( nstick[0] == nstick[1] ) {
      fputc( ' ', fout );
      fputc( nume[0], fout );
    }
    fprintf( fout, "\n%d\n", nstick[t] );
  }
  fclose( fout );

  return 0;
}

Problema maxim2

Problema maxim2 a fost dată la OJI 2019 clasa a 6a.

Ea are o rezolvare relativ simplă, cu forță brută și diverse variante optimizate. Să discutăm o parte din ele. Vom discuta doar cerința 2, prima fiind banală, de nivel clasa a cincea.

Soluția forță brută

În această soluție simulăm enunțul. Vom memora cele n cifre într-un vector de caractere. Apoi vom lua, pe rînd, toate ferestrele de m cifre consecutive și vom forma numerele maxime. Fiecare număr maxim va fi comparat cu un maxim global.

Să detaliem puțin forța brută:

  • Cum formăm cel mai mare număr posibil din m cifre? Problema este de clasa a cincea, vom lua cifrele în ordine descrescătoare. Pentru aceasta formăm un vector de frecvență al cifrelor.
  • Cum comparăm numărul din fereastra curentă de m cifre cu maximul global? Am putea să formăm ambele numere maximale, din vectorii de frecvență, și să îi comparăm. Dar este risipitor. Este mult mai rapid să comparăm direct vectorii de frecvență. Zece comparații în loc de 1000.
  • Ce facem la egalitate? Acele condiții complicate din enunț se rezumă la ceva simplu: se dorește ultima poziție a maximului. Nu este ușor de demonstrat acest lucru. Dar, în condiții de concurs, ce puteam face? Desigur să afișăm întotdeauna ultima poziție, cum cerea a treia posibilitate din enunț. Deci, cumva, enunțul ne ghidează către soluția corectă din motivul incorect (nu știm cum să îndeplinim condiția 2).

Ce complexitate are această soluție?

Vom analiza n - m + 1 ferestre de lungime m. Pentru fiecare fereastră vom avea m operații pentru calculul vectorului de frecvență, și încă Σ operații pentru comparația vectorilor, unde Σ este mărimea alfabetului, în cazul nostru 10. Soluția este, deci, O((n - m + 1)·(m + Σ)). Dacă desfacem parantezele și ignorăm termenii nenecesari vom obține O(n·(m + Σ)). În cazul nostru, deoarece Σ este mult mai mic decît m, complexitatea finală este O(n·m).

Se încadrează în timp? Făcînd înlocuirile obținem 500000·1000, adică 500 milioane. Pare cam la limită și așa și este. Din nou, am generat un test maximal pe care această soluție a durat circa 1s, iar soluția oficială a autoarei a durat 3s, depășind timpul permis.

Cu toate acestea, din nou, surpriza emisiunii este că soluția forță brută, scrisă îngrijit, lua 100p la ONI. Cum este posibil acest lucru? Deoarece, din nou, testele oficiale sînt departe de a fi maximale. Cel mai mare test este de circa cinci ori mai mic decît cel maximal, în termen de număr de operații.

Nu are sens să mai repet cele spuse la problema album. Este evident că problema generează inversiuni de valori.

Observație importantă: dacă nu ne prindeam cum să comparăm două numere maximale de 1000 de cifre folosind vectori de frecvență puteam să folosim o metodă greșită: formam numerele efectiv, folosind tipul long long. Această soluție, greșită, ia în mod incredibl 80p, adică două treimi din punctajul acordat cerinței 2. Înțeleg ideea de a da punctaje rezonabile pentru soluții rezonabile, dar 80p este prea mult, chiar și jumate este mult. O treime ar fi normal, poate, caz în care ar fi trebuit ca punctajul pentru această soluție să fie 60p.

Soluție forță brută optimizată

O primă optimizare evidentă este de a citi cifrele drept caractere, cu fgetc(). Vom obține o viteză de citire mărită de patru ori. Deoarece citim circa un megaoctet de date, nu putem neglija cîștigul de timp.

Dar optimizarea cea mai importantă vine din altă parte. Mare parte din timpul petrecut în forța brută este recalculînd vectorii de frecvență. În fapt, ei se pot recalcula incremental, în O(1). Cum?

Cînd "deplasăm" fereastra de m elemente:

  • Adunăm la vectorul de frecvență cifra care intră în fereastră.
  • Scădem din vectorul de frecvență cifra care iese din fereastră.

Recalcularea vectorului de frecvență este, astfel, O(1). Rămîne însă comparația lor, acel factor de Σ care nu se mai poate ignora. Complexitatea rezultată este O(n·Σ). Numărul de operații este 500000·10, adică 5 milioane. Este clar că această soluție se va încadra lejer în timp.

Soluție optimă

Cîtă memorie folosim în soluția anterioară?

Desigur O(n). Putem mai bine? Da. Nu avem nevoie să memorăm toate cifrele, ci doar o fereastră de m cifre. În ea putem depune pe rînd cifrele de la intrare. Odată ce ajungem la finalul ferestrei o vom lua din nou de la început, suprascriind cifrele care nu mai sînt acum necesare.

Această structură de date se numește coadă și vom învăța despre ea anul următor.

Această soluție folosește atît de puțină memorie, circa 1000 de caractere, încît este substanțial mai rapidă ca forța brută optimizată (de circa două-trei ori), deoarece acel vector de caractere încape complet în cache-ul L1, memoria cea mai rapidă a procesorului. Pe lîngă aceasta, o soluție care nu risipește memorie este întotdeauna mai bună, nu? :-)

Vă sugerez ca la temă să implementați această soluție, deoarece vă va solicita la maxim, pregătindu-vă astfel pentru ONI.

Atenție la optimizări simple ce vă pot aduce mari îmbunătățiri la această soluție:

  • Citire cu caractere
  • Comparație vectori folosind o santinelă (un test per element în loc de două)
  • Copiere vector în vectorul maxim doar de la poziția care diferă, pe care o știm de la comparația anterioară

Iată o soluție bazată pe aceste idei, care încearcă să implementeze ambele puncte eficient (53 linii de program):

#include <stdio.h>

int fm[11], f[11]; // zece cifre plus un element pentru santinela
char ult[1024]; // coada de cifre, sa stim ce iese din fereastra de m cifre

int main() {
  FILE *fin, *fout;
  int c, n, m, i, pu, pm, cf;

  fin = fopen( "maxim2.in", "r" );
  fout = fopen( "maxim2.out", "w" );
  fscanf( fin, "%d%d%d ", &c, &n, &m );
  for ( i = 0; i < m; i++ ) {
    ult[i] = (fgetc( fin ) - '0' + 1); // citim cifra, adaugam unu
    f[ult[i]]++;            // adaugam cifra la vectorul de frecventa
    fm[ult[i]] = f[ult[i]]; // si o copiem in maxim
    fgetc( fin );           // citim spatiul dintre cifre
  }

  if ( c == 1 ) { // cerinta 1 - afisam numarul maxim din primele m cifre
    for ( cf = 10; cf > 0; cf-- )
      for ( i = 0; i < f[cf]; i++ )
        fputc( cf + '0' - 1, fout );
    fputc( '\n', fout );
  } else { // cerinta 2 - pozitia numarului maxim din m cifre rearanjate
    f[0] = 1;   // santinela
    pu = 0;     // prima pozitie in coada de cifre
    pm = m - 1; // pozitia de final a numarului maxim
    for ( i = m; i < n; i++ ) {
      f[ult[pu]]--; // scoatem cifra care iese din fereastra de M
      f[ult[(pu + m) % 1024] = (fgetc( fin ) - '0' + 1)]++; // citim cifra
      fgetc( fin );         // citim spatiul dintre cifre
      pu = (pu + 1) % 1024; // avansam prima pozitie a cozii de cifre

      // comparam vectorii fm[] si f[], luind maximul
      cf = 10;
      while ( fm[cf] == f[cf] )
        cf--;

      if ( cf == 0 || f[cf] > fm[cf] ) { // am gasit un numar >= max
        pm = i; // actualizam pozitia maximului
        // copiem f[] in fm[] pentru a stoca maximul
        for ( ; cf > 0; cf-- )
          fm[cf] = f[cf];
      }
    }
    fprintf( fout, "%d\n", pm - m + 2 );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Problema cutii1

Comentarii generale

  1. Felicitări celor ce au reușit o soluție de excepție: Voicu, Asgari, Ilie, Tatomir.
  2. Mențiuni speciale: Rebengiuc soluție de 100p ce folosește memorie O(1). Togan cu o soluție ingenioasă, deși ineficientă, ce a reușit să treacă 18 teste cu o soluție O(b), evitînd împărțirile.
  3. Mulțumiri celor ce m-au ajutat cu comentarii: Badea, Burac, Calotă, Ștefănescu, Fares.
  4. Unii din voi au dat algoritmi care au în mod evident complexitatea O(b). Era foarte clar că ei vor depăși timpul, nu-i așa? Foarte rău că nu ați încercat mai bine, mai ales la temă!
  5. Unii din voi mi-au trimis și la temă soluția din concurs, o soluție care nu funcționează. Aceasta înseamnă că nu v-ați mai gîndit deloc la ea ulterior. Foarte, foarte urît! Cine: Badea, Calotă, Grecu, Stoian.
  6. Avertismente celor ce nu au trimis nici o soluție la această problemă: Cojocariu, Mușat.

Comentarii individuale

Grupa de dimineață

  • Badea (35p): Mulțumesc pentru comentarii! Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Testele picare cu 'incorect' sînt din cauza inițializării defectuoase a lui j. În loc de j = -1; corect era j = -rest;, pentru a porni cu j de la zero.
  • Benescu (5p): Soluția ta nu este doar lentă (comentariul 4), dar și fără noimă. Vezi codul tău:
    for(i=0; i<b; i++){
      q=(t%(n*2-2)+r);
      if(q<n || q>n*2-2){
        v[q]++;
        r=n-q;
      }
      else{
        v[n+n-q]++;
        r=q-n;
      }
    }

Tu apelezi v[q] atunci cînd q>n*2-2, deși vectorul are maxim 1000 de elemente. Atenție la matematică și la limite! E inadmisibil. Dacă ai fi pus ceva comentarii aș fi încercat să corectez codul.

  • Burac (10p-90p): Mulțumesc pentru comentarii! Ideea de bază e foarte bună. Implementarea este cam încîlcită, este bine că ai pus comentarii. Vezi te rog o soluție mai simplă mai jos.
  • Calotă (5p): Mulțumesc pentru comentarii! Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Ideea de pornire e bună, dar nu te-ai descurcat cu faptul că banda se mișcă dus-întors, drept care programul este incorect. Mulțumită comentariilor am înțeles, însă, că ideea este bună.
  • Chivu (5p-42p): Ideea este bună, iar implementarea este rezonabilă. Nu înțeleg de ce ai folosit vectorul de la 1. Însă algoritmul era clar că ieșea din timp, vezi comentariul 4. N-ai găsit nimic mai bun decît O(b)?
  • Cojocariu (0p): nimic? Continui pe linia asta, rezolvi cam o problemă de temă din două.
  • Grecu (15p): Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Ideea de a combina cutiile nu e rea, codul este ordonat și scurt, dar ai greșit la formule. În loc de:
  for ( i = 0; i < b; ++i ) {
    if ( (time / n) % 2 == 1 ) {
      ++v[time % n];
    } else {
      ++v[(n - 1) - time % n];
    }
    time += t;
  }

trebuia

  for ( i = 0; i < b; ++i ) {
    if ( (time / (n - 1) ) % 2 == 1 ) { // n-1 in loc de n
      ++v[time % (n - 1)]; // n-1 in loc de n
    } else {
      ++v[(n - 1) - time % (n - 1)]; // n-1 in loc de n
    }
    time += t;
  }
  • Hossu (15p-38p): Ideea este bună, poate fi făcută să meargă. Implementarea e încîlcită. N-am putut să mă prind care e problema, căci nu ai pus comentarii. Hossu, ai lasat fprintf de debug în cod, care deschide un fișier "fout1.out". Atenție!
  • Mocanu (40p): Mocanu, din ultimele două teme ai rezolvat două probleme (din șapte). Și acelea, una din ele de 40p. Ce se întîmplă? Ai inițializat z=-1; în loc de z=-t;, de aceea ai cîțeva teste ratate cu 'incorect'.
  • Mușat (0p): nimic? N-a fost nici pe de parte cea mai grea problemă, dar e singura pe care nu ai atins-o.
  • Nicola (0p): Nimic.
  • Petcu (20p): Programul este ordonat și clar, bravo. Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Nu înțeleg de ce ai folosit vectorul de la unu, ți-a fost lene să renumerotezi cutiile de la zero? Ratezi teste pentru că modifici variabila cutie pentru a actualiza vectorul de cutii. Ea nu trebuie schimbată, ea merge circular modulo 2*n-1, ci pe baza ei trebuie să calculezi cutia propriu-zisă. Mai exact, în loc de:
    for( ; b > 0; b-- ) {
        bomboane[cutie]++;
        cutie = ( cutie + t ) % ( 2 * n - 2 );
        if( cutie == 0 )
          cutie = n;
        if( cutie > n )
          cutie = 2 * n - cutie;
    }

trebuia:

    for( ; b > 0; b-- ) {
        if ( cutie <= n )
          bomboane[cutie]++;
        else
          bomboane[2 * n - cutie]++;
        cutie = ( cutie + t ) % ( 2 * n - 2 );
        if( cutie == 0 )
          cutie = 2 * n - 2;
    }

Ideea bună, dar atenție la matematică!

  • Rebengiuc (100p): o soluție matematică interesantă. Ai folosit memorie O(1), foarte interesant. Nu am înțeles bine formula din spatele algoritmului, dacă avem timp poate o prezinți la oră. Cod foarte frumos scris.
  • Rughiniș (15p): Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Programul este destul de clar și ordonat. Folosești corect vectorul, dar te-ai încurcat la formulele de dus și de întors și de aceea ratezi teste. Mai exact, în loc de:
  a=0;
  v[n-1]++;
  for(i=0;i<b;i++){
    a+=t;
    if(a/(n-1)%2==0)
      v[n-1-a%(n-1)]++;
    else
      v[a%(n-1)]++;
  }

trebuia

  a=-t;
  for(i=0;i<b;i++){
    a+=t;
    if(a/(n-1)%2==0)
      v[n-1-a%(n-1)]++;
    else
      v[a%(n-1)]++;
  }
  • Stoian (10p): Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Mai ales că tu nu ai trimis o rezolvare, ci o aiureală, e o sursă de 0p, tu ai luat 10p cu noroc. Daria, tu poți mai mult. E o problemă de simulare, ai mai rezolvat așa ceva.
  • Ștefănescu (10p): Mulțumesc pentru comentarii! Algoritmul tău este O(t·b), adică forța cea mai brută posibil. De aceea pică 15 teste. În plus, ai fost neatentă la cum ai variat indicele cutiei. Mai exact, în loc de:
    nrb = 0;
    i = 0;
    sens = 1;
    timp = 0;
    c = n;
    m = 0;
    while (nrb < b) {
        /// schimb sensul
        if (i == n && sens == 1) {
            sens = -1;
        } else if (i == 0 && sens == -1) {
            sens = 1;
        }
    
        i += sens;
        // ...
    } 

corect era:

    nrb = 0;
    i = -1; // in loc de 0                                           
    sens = 1;                                                      
    timp = 0;
    c = n;
    m = 0;
    while (nrb < b) {
        i += sens; // mutat sus, înainte de if

        /// schimb sensul                                                       
        if (i == n-1 && sens == 1) { // n - 1 nu n                                
            sens = -1;
        } else if (i == 0 && sens == -1) {
            sens = 1;
        }
        // ...
}

Cu aceste modificări vei trece 5 teste (20p).

  • Togan: (5p-85p): Un program interesant. Deși este O(b) reușește să treacă multe teste pentru că eviți împărțirile. Desigur că asta nu face soluția bună, ci doar ingenioasă. Nu mi-e clar de ce folosești vectorul de la unu. Cod destul de greu de înțeles, dar se vede o îmbunătățire. Continuă să simplifici încîlcelile.
  • Voicu (100p): Un program bun, bravo! Cel mai eficient din grupa de dimineață. Ca observații, deși lucrezi cu indici circulari, lucrezi cu ei de la 1, în loc de 0. Tu scrii i=(i+t-1)%(2*n-2)+1; cînd ai putea scrie mai simplu i=(i+t)%(2*n-2);. Un nărav care îți complică viața. Ai lăsat un printf de debug, mai multă atenție, te poate costa problema, TLE!

Grupa de după-amiază

  • Asgari (100p): Un program bun, bravo! Clar și simplu, folosești matematică, bun! Ca observație, ca și Voicu , deși lucrezi cu indici circulari, lucrezi cu ei de la 1, în loc de 0, ceea ce îți complica viața. În loc de curp = (curp - 1 + t) % (2 * (n - 1)) + 1; puteai să scrii curp = (curp + t) % (2 * (n - 1)) ;.
  • Cadîr (25p): O simulare foarte corectă și frumos scrisă, cu excepția faptului că folosești vectorul de la 1. Păcat că algoritmul tău este O(t·b), adică forța cea mai brută posibil. De aceea pică 15 teste cu TLE. Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5).
  • Dobre (15p-22p): Algoritmul tău este complex. Programul este bine scris și îngrijit, dar nu pot să-mi dau seama ce face, deoarece ai structuri de date gen o matrice cu trei linii, al căror rost nu îl cunosc. Din cîte îmi dau seama, complexitatea algoritmului este O(t·b), adică forța cea mai brută posibil. Dacă îl repari vei lua 5 teste. Am remarcat bordarea vectorului de cutii, drăguț.
  • Fares (40p-95p): Mulțumesc pentru comentarii! Motivul pentru care am înțeles, în mare, ceea ce faci, sînt aceste comentarii. Yusuf, tu ai luat toate testele, felicitări! Dar gîndirea ta este prea încîlcită. Ai atît de multe cazuri încît sînt greu de urmărit! Acele cazuri nu există în realitate, tu le-ai introdus. Trebuie să încerci să îți simplifici gîndirea. Pentru asta este nevoie să te gîndești mai mult la algoritm, cu o hîrtie și un pix în față, înainte să te apuci să scrii la calculator. Codul tău este scris ca și cum ai vorbi liber. Iată un exemplu care nu are sens: c = 1ll * b / rep;. Sau altul:
    if (c == 0 && f1[i] == 0)
      sol1++;
    else if (c > 0 && f[i] == 0)
      sol1++;

care se putea scrie:

    if (f1[i] == 0)
      sol1++;
  • Ilie (100p): Un program ordonat și clar. Singurul lucru neclar era la ce îți trebuie vectorul rep[]. M-am lămurit, pentru a îți da seama cînd se termină primul ciclu de găleți. Pentru aceasta nu e nevoie de vector, ciclul se va încheia întotdeauna la prima găleată. Este similar cu problema celor doi băieți care săreau în cerc în direcții diferite și se opreau atunci cînd săreau acolo unde mai săriseră o dată. Per total o sursă bună, bravo!
  • Ipate (10p-18p): Elisa, două probleme cu algoritmul tău: 1. Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). 2. Metoda matematică este incorectă. Ambele sînt destul de grave, pentru că (1) înseamnă că nu ai calculat faptul că îți va depăși timpul, iar (2) înseamnă că ai slăbiciuni la matematică, ceea ce în cazul unei matematiciene e un pic îngrijorător.
  • Marcu (10p): Mulțumesc pentru comentarii! Am înțeles intenția mulțumită lor, deoarece tu nu faci ceea ce vrei să faci:
c=(c+t)%n;//folosim un vector cu 2n-1 elemente deorece la poz 2n-1 se repeta modul de parcurgere

Un calculator face ceea ce îi spui să facă, nu ceea ce vrei să facă! Păcat că nu a citit și compilatorul comentariul. Dacă vrei să folosești 2n-1 elemente atunci trebuia să scrii modulo 2n-1, nu modulo n :-). O altă problemă este că simularea ta este O(b), de aceea depășește timpul (comentariul 4).

  • Nicu (100p): Nicu, tu chiar ți-ai dorit cele 100 de puncte! Felicitări! Programul tău este unul stufos, ai lucrat, ai tastat, ai creat multe cazuri particulare acolo unde nu existau! Ai muncit împotriva încîlcelii tale. Alex, dacă vrei să te îmbunătățești trebuie să gîndești înainte să te arunci în programare la calculator. Ia o hîrtie și un creion și fă-ți cîteva teste, încearcă să înțelegi cum ai face tu. Programul tău arată ca și cînd vorbești liber: te repeți, te mai bîlbîi, etc. Precum vezi multe din sursele tale sînt pescuite. Lenea de a face teste te ține din a progresa ca informatician. Măcar dacă puneai comentarii. Așa, nu am nici cea mai vagă idee ce ai vrut să să scrii sau ce ai gîndit.
  • Stancu (25p): Mulțumesc pentru comentarii! Programul e mai ușor de citit și înțeles. Programul tău este ordonat, bravo. Soluția ta este, din păcate, ineficientă, fiind 'O(t·b), adică forța cea mai brută posibil. De aceea pică 15 teste. Ca observație, înțeleg că folosești vectorul de la 1, dar nu avea rost să îl declari de 2001 elemente, 1000 erau deajuns.
  • Tatomir (100p): O soluție bună, simplă și bine scrisă! Bravo!
  • Teodorescu (80p): O soluție foarte bună și eficientă, bravo! Se mai poate simplifica. Nu aveai nevoie neapărat de vectorul de resturi, de exemplu. Folosești indici de la 1, în loc să-i folosești de la 0, deși ai nevoie de mișcări circulare în vector. Simularea cu steguleț e greu de urmărit, chiar dacă așa v-am predat, acela este un caz general. Dacă poți simplica, simplifică. Motivul pentru care ratezi testele mici cred că este că în prima buclă te oprești doar cînd faci un ciclu complet. Dar poate se termină bomboanele mai devreme? Trebuie să mai adaugi o condiție de ieșire.

Rezolvare

Problema cutii1 a fost dată la ONI 2003 clasa a 8a. Atunci de ce am dat-o la clasa a șasea? Deoarece ea se potrivește la această clasă conform standardelor ultimilor ani.

Este o problemă de simulare care necesită unele optimizări. Să vedem:

Soluție forță brută

Putem încerca să mutăm banda din secundă în secundă, cîte o găleată. Implementarea este destul de lejeră. Ce complexitate va avea acest algoritm?

Ea va fi proporțională cu numărul de secunde al simulării. Deoarece o bomboană se eliberează la t secunde și avem b bomboane rezultă imediat o complexitate de O(b·t) secunde, adică maxim un milion de miliarde de operații. Foarte ineficient.

Soluție forță semi-brută

Am putea să "sărim" în față cîte t secunde, din bomboană eliberată în bomboană eliberată. Pentru aceasta ne trebuie o formulă matematică pentru a calcula ce cutie se află sub dispensorul de bomboane după t secunde.

Am putea fi tentați să folosim o formulă la modul i = (i + t) % n, ceea ce ar fi incorect, deoarece:

  • Cutiile se mișcă în ambele direcții.
  • Ciclul de mișcare este n - 1 și nu n. Într-adevăr, banda se va deplasa n - 1 poziții într-o direcție și apoi n - 1 poziții în cealaltă direcție.

Putem să căutăm o formulă care să țină cont de paritatea ferestrei de n - 1 secunde în care se află indicele final. În cazul impar indicele trebuie "răsturnat". Ea va funcționa.

Voi alege însă o soluție pe care o consider mai simplă, ce rezultă într-o formulă simplă și care se poate și generaliza la o soluție elegantă.

Observație: În loc de n cutii putem considera 2·n - 2 cutii așezate în cerc. În loc ca banda să facă n - 1 deplasări într-o direcție și n - 1 deplasări în cealaltă direcție, banda va fi circulară, va avea 2·n - 2 cutii și se va roti constant, în aceeași direcție (vezi figurile).

Clasic
Echivalent, cu rotație continuă

Putem introduce, astfel, încă n - 2 cutii fictive. Simularea acestor cutii se simplifică, deoarece le putem parcurge ca vector circular, modulo 2·n - 2. La final putem combina conținutul cutiilor identice. În exemplul nostru vom aduna conținuturile cutiilor 2 și 3.

Formula de salt la următoarea cutie ce primește bomboană va fi, astfel: i = (i + t) % (2·n - 2).

Iată un program care implementează această soluție:

#include <stdio.h>

#define MAXCUTII 999

int c[2 * MAXCUTII - 2];

int main() {
  FILE *fin, *fout;
  int n, t, b, i, j, bd, max, goale;

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

  i = 0; // indicele cutiei de sub dispensorul de bomboane
  bd = 0; // numarul de bomboane distribuite
  do {
    c[i]++;                    // depunem in cutie o bomboana
    i = (i + t) % (2 * n - 2); // avansam pe urmatorul indice
    bd++;                      // am mai distribuit o bomboana
  } while ( bd < b ); // cita vreme cutia de dedesubt este goala

  for ( j = 1; j < n - 1; j++ ) // combinam cutiile de dus si de intors
    c[j] += c[2 * n - 2 - j];
  
  max = goale = 0;
  for ( j = 0; j < n; j++ )
    if ( c[j] == 0 )
      goale++;
    else if ( c[j] > max )
      max = c[j];
  
  fout = fopen( "cutii1.out", "w" );
  fprintf( fout, "%d %d\n", goale, max );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Deoarece fiecare buclă a iterației tratează o bomboană dispensată, complexitatea va fi O(b). Deoarece b poate fi un miliard soluția va depăși timpul pe teste mari.

Soluție optimă

Rezolvarea anterioară repetă foarte multe operații. Este clar că după cel mult 2·n - 2 dispensări vom reveni la cutia numărul 1. Apoi ciclul se va repeta. Putem, deci, să simulăm distribuția doar pînă ce cutia 1 ajunge sub dispensor. Să spunem că la acest moment am distribuit bd bomboane (bomboane distribuite). Atunci acest ciclu se va executa de b / bd ori. Putem, deci, înmulți numărul de bomboane din cutii (care este 1 sau 0) cu b / bd. Aceasta este echivalent cu a executa ciclul de simulare de b / bd ori. Va rămîne de simulat ultima porțiune ce va distribui b % bd bomboane. Acesta este algoritmul.

Iată o soluție care îl implementează:

#include <stdio.h>

#define MAXCUTII 999

int c[2 * MAXCUTII - 2];

int main() {
  FILE *fin, *fout;
  int n, t, b, i, j, bd, max, goale;

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

  i = 0; // indicele cutiei de sub dispensorul de bomboane
  bd = 0; // numarul de bomboane distribuite
  do {
    c[i] = 1;                   // depunem in cutie o bomboana
    i = (i + t) % (2 * n - 2);  // avansam pe urmatorul indice
    bd++;                       // am mai distribuit o bomboana
  } while ( i > 0 && bd < b );  // cita vreme nu am revenit la prima cutie

  for ( j = 0; j < 2 * n - 2; j++ ) // multiplicam ciclul de b / bd ori
    c[j] *= (b / bd);

  for ( b %= bd; b > 0; b-- ) { // ultimii pasi ai simularii
    c[i]++;                     // depunem in ea o bomboana
    i = (i + t) % (2 * n - 2);  // avansam pe urmatorul indice
  }

  for ( j = 1; j < n - 1; j++ ) // combinam cutiile de dus si de intors
    c[j] += c[2 * n - 2 - j];
  
  max = goale = 0;
  for ( j = 0; j < n; j++ )
    if ( c[j] == 0 )
      goale++;
    else if ( c[j] > max )
      max = c[j];
  
  fout = fopen( "cutii1.out", "w" );
  fprintf( fout, "%d %d\n", goale, max );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Deoarece bd ≤ 2·n - 2 rezultă că toți cei trei pași ai simulării sînt O(n), aceasta fiind și complexitatea algoritmului. n fiind maxim 1000 programul se va încadra lejer în timp. Memoria folosită va fi tot O(n).

Problema pește

Problema pește a fost dată la ONI 2017 clasa a 6a.

Ea conține două subpuncte ce constituie, în fapt, două probleme diferite, ambele destul de întîlnite la concursuri. Să le discutăm pe rînd.

Soluție prima cerință

Prima cerință cere ca dat un număr să se elimine două cifre consecutive ca poziție astfel încît cifrele rămase, concatenate, să rezulte într-un număr maxim.

Problema pare banală, nu? Vom încerca toate posibilitățile de eliminare, comparînd numerele nou formate și selectînd maximul. Este o soluție rezonabilă. Dar ce complexitate are ea? Dacă numărul de cifre este C vom efectua C - 1 comparații, iar o comparație va face C - 2 operații, deci complexitatea este O(C2). Deoarece numerele pot avea 18 cifre rezultă că vom efectua 272 de operații.

Se poate mai bine? Da, folosind matematică și logică. Să presupunem că numărul nostru inițial este:

  • Numărul inițial este D = d1 d2 d3 ... dC unde di este cifra numărul i.
  • Numărul final este X.

Să observăm următoarele:

  • X va începe fie cu cifra d1, fie cu cifra d3. El nu poate începe cu cifra d2! De ce?
  • Dacă d1 < d3 este clar că vom elimina primele două cifre pentru ca X să fie maxim, deci ne putem opri.
  • Dacă d1 > d3 este clar că nu putem elimina primele două cifre, deoarece numărul rezultat ar fi strict mai mic. Vom păstra deci prima cifră, obligatoriu. Dar acum am rămas cu o problemă similară: avem cifrele rămase din C, anume d2 d3 ... dC și vrem să aflăm numărul maxim ce se poate forma din acest număr. Deci vom relua algoritmul.
  • Dacă d1 = d3 nu știm dacă vom elimina sau nu primele două cifre. Deci va trebui să ne uităm la cifrele d2 și d4. Avem și aici trei variante posibile:
    • Dacă d2 < d4 vom elimina primele două cifre, d1 < d2. Dar, deoarece d1 = d3, putem elimina cifrele doi și trei, adică d2 < d3 cu același efect. De exemplu, dacă numărul nostru D este 4245236 putem elimina primele două cifre, obținînd 45236, sau cifrele pe pozițiile 2 și 3, rezultînd 4 5236, care lipite duc la același număr 45236. Rezultă că 'putem păstra prima cifră și continua cu restul numărului, ca și încazul anterior.
    • Dacă d2 > d4 atunci nu putem elimina primele două cifre, deoarece numărul rezultat ar fi mai mic. Și în acest caz 'putem păstra prima cifră.
    • Dacă d2 = d4 atunci avem un număr de forma 4242xxxxx... Ceea ce înseamnă că și dacă am decide să eliminăm primele două cifre, acest lucru ar fi echivalent cu a elimina cifrele pe pozițiile 2 și 3, sau 3 și 4. Și în acest caz 'putem păstra prima cifră și continua cu restul numărului.

Ce rezultă din aceste observații? Că singurul caz în care nu vom lua prima cifră a numărului este cazul cînd ea este strict mai mică decît a treia cifră. De aici rezultă un algoritm foarte simplu și elegant:

  • Pornim cu poziția poz = 2 (a treia cifră din număr).
  • Cîtă vreme poz < C și dpoz-2 ≤ dpoz
    • poz = poz + 1

La terminarea acestui algoritm cifrele eliminate vor fi dpoz și dpoz+1. Pentru a obține numărul final, după eliminare, vom copia cifrele începînd cu dpoz+2 pînă la final cu două poziții spre dreapta.

Cum calculăm cele mai eliminate două cifre? Desigur folosind un vector de frecvență al numerelor de două cifre. Avem grijă să formăm din cele două cifre eliminate un număr cu două cifre în aceeași ordine, de exemplu prima cifră mai mică decît a doua.

Acest algoritm se implementează ușor dacă avem deja extrase cifrele numărului. De aceea nu vom citi numărul cu fscanf() ci cu fgetc(). Deoarece avem N numere, vom folosi o matrice de N×C caractere ce vor memora cifrele celor N numere. Iată codul pentru eliminarea celor două cifre consecutive ca poziție:

    cif[i][ncf = 0] = fgetc( fin ); // citim primele doua cifre separat
    cif[i][1] = fgetc( fin );
    while ( (ch = fgetc( fin )) != '\n' && ch <= cif[i][ncf] ) {
      cif[i][ncf + 2] = ch;
      ncf++;
    }
    // calculam cifrele eliminate, in ordine
    p1 = cif[i][ncf] - '0';
    p2 = cif[i][ncf+1] - '0';
    p = p1 < p2 ? p1 * 10 + p2 : p2 * 10 + p1;
    f[p]++;
    if ( f[p] > max )
      max = f[p];
    // citim restul numarului
    while ( ch != '\n' ) {
      cif[i][ncf] = ch;
      ncf++;
      ch = fgetc( fin );
    }
    cif[i][ncf] = cif[i][ncf+1] = 0; // marcam finalul de numar

Soluție a doua cerință

A doua cerință ne cere ca, dîndu-se N numere de maxim 16 cifre să se așeze unul după altul formînd un număr X maximal.

Aceasta este o problemă "clasică" în concursuri. Cum am putea să încercăm să o rezolvăm?

  • Am putea să ordonăm numerele descrescător și să le luăm în acea ordine. Soluție incorectă, deoarece numerele 82 și 9 trebuie așezate invers, 9 și 82 pentru a obține numărul maxim, 992.
  • Am putea să considerăm numerele drept cuvinte, pe care să le ordonăm alfabetic descrescător. Soluție incorectă, deoarece 8 și 82 trebuie puse în ordinea 8 și 82, pe cînd 8 și 89 trebuie puse în ordinea 89 și 8.

Soluția clasică a acestei probleme este să folosim orice sortare prin comparații, de exemplu sortarea prin selecție, la care vom folosi o funcție specială de comparație. Mai exact, atunci cînd comparăm numerele X și Y vom compara de fapt numerele XY și YX. Dacă XY > YX vom considera că X > Y.

Interesant, nu? Putem, acum, aplica sortarea prin selecție obișnuită! Pentru a ne ușura implementarea vom ține cont de următoarele:

  • În loc să memorăm pentru fiecare număr și numărul său de cifre vom păstra cifrele sale drept caractere între '0' și '9', avînd la final un caracter terminator de șir anume '\0', adică caracterul al cărui cod este chiar numărul zero.
  • Cînd comparăm două șiruri X și Y am putea să le copiem în alte două șiruri, unul după altul, în cele două moduri, XY și YX.
  • În loc de aceasta, însă, vom proceda direct la comparație, pornind cu doi indici zero, unul în X și altul în Y. Atunci cînd unul din indici ajunge la finalul șirului său, îl vom comuta pe celălalt șir.
  • Codul de comparație devine astfel mai scurt și mai eficient.

Iată o soluție care aplică cele de mai sus (86 linii de cod):

#include <stdio.h>

char f[100], cif[100][19];

int main() {
  FILE *fin, *fout;
  int n, c, i, p, ncf, ch, max, i1, i2, p1, p2;
  char aux;

  fin = fopen( "peste.in", "r" );
  fscanf( fin, "%d%d ", &c, &n );
  max = 0;
  for ( i = 0; i < n; i++ ) {
    cif[i][ncf = 0] = fgetc( fin ); // citim primele doua cifre separat
    cif[i][1] = fgetc( fin );
    while ( (ch = fgetc( fin )) != '\n' && ch <= cif[i][ncf] ) {
      cif[i][ncf + 2] = ch;
      ncf++;
    }
    // calculam cifrele eliminate, in ordine
    p1 = cif[i][ncf] - '0';
    p2 = cif[i][ncf+1] - '0';
    p = p1 < p2 ? p1 * 10 + p2 : p2 * 10 + p1;
    f[p]++;
    if ( f[p] > max )
      max = f[p];
    // citim restul numarului
    while ( ch != '\n' ) {
      cif[i][ncf] = ch;
      ncf++;
      ch = fgetc( fin );
    }
    cif[i][ncf] = cif[i][ncf+1] = 0; // marcam finalul de numar
  }
  fclose( fin );

  fout = fopen( "peste.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%d\n", max );
  else {
    // cerinta 2 - numarul maxim format din numerele din cif[][]
    // aplicam select sort comparind perechi de numere
    // o pereche se compara punind numerele unul dupa altul in cele doua moduri
    for ( p = 0; p < n - 1; p++ ) { // sortare prin selectie
      max = p;
      for ( i = p + 1; i < n; i++ ) {
        // comparam cif[max] cu cif[i]
        i1 = i2 = 0;
        p1 = max;
        p2 = i;
        while ( cif[p1][i1] != 0 && cif[p1][i1] == cif[p2][i2] ) {
          i1++;
          if ( cif[p1][i1] == 0 && p1 == max ) { // comutam pe celalalt numar
            p1 = i;
            i1 = 0;
          }
          i2++;
          if ( cif[p2][i2] == 0 && p2 == i ) { // comutam pe celalalt numar
            p2 = max;
            i2 = 0;
          }
        }
        if ( cif[p1][i1] != 0 && cif[p1][i1] < cif[p2][i2] )
          max = i; // inlocuim maximul
      }
      i1 = 0; // interschimbam max cu p
      while ( cif[p][i1] != 0 || cif[max][i1] != 0 ) {
        aux = cif[p][i1];
        cif[p][i1] = cif[max][i1];
        cif[max][i1] = aux;
        i1++;
      }
    }
    for ( p = 0; p < n; p++ ) { // afisam numerele in ordine
      i = 0;
      while ( cif[p][i] != 0 ) {
        fputc( cif[p][i], fout );
        i++;
      }
    }
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

Rezolvări aici: [1]

Tema 27 - rezolvări

Problema factoriale

Problema [2] a fost dată într-un concurs IQ Academy 2019 clasa a 6a.

Iată o soluție:

#include <stdio.h>

#define MAXN 65000
#define MAXNR 1000000
#define MOD 2147483647

unsigned short poz[MAXNR+1];
int fact[MAXN+1];

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

  fin = fopen( "factoriale.in", "r" );
  fscanf( fin, "%d ", &n );
  // construim un vector de frecventa in care memoram pentru fiecare numar
  // de la intrare pozitia pe care s-a aflat la intrare, pentru a sti sa
  // raspundem la intrebari in ordine
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%d", &x );
    poz[x] = i; // pozitia lui x este i
  }
  fclose( fin );

  // calculam factorialele de la 1 la max x (sau MAXNR - 1 milion)
  // stocam rezultatele in ordinea numerelor de la intrare
  // daca poz[x] == 0 inseamna ca nu am avut valoarea x la intrare
  // pentru a economisi un test, il adaugam totusi la fact[0]
  p = 1;
  for ( x = 1; x <= MAXNR; x++ )
    fact[poz[x]] = p = p * x % MOD;
  
  fout = fopen( "factoriale.out", "w" );
  for ( i = 1; i <= n; i++ )
    fprintf( fout, "%d ", fact[i] );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Problema cifru1

Problema cifru1 a fost dată la ONI 2007 clasa a 6a.

Iată o soluție:

#include <stdio.h>

int dlin[4] = { 0, 1, 0, -1 }; // diferenta pe linie in functie de directie
int dcol[4] = { 1, 0, -1, 0 }; // diferenta pe coloana in functie de directie
int tablou[100][100];          // matricea tabloului de butoane
int aux[400];                  // vector auxiliar pentru copierea unei rame

int main() {
  FILE *fin, *fout;
  int n, i, j, l, c, rama, mij, dir, suma, smax, jmax, sumatotala;

  fin = fopen( "cifru1.in", "r" );
  fscanf( fin, "%d", &n );
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ )
      fscanf( fin, "%d", &tablou[l][c] );
  fclose( fin );

  sumatotala = 0;
  mij = n / 2;                           // cite rame avem
  for ( rama = 0; rama < mij; rama++ ) { // parcurgem fiecare rama
    smax = -1;              // suma maxima din cele patru laturi ale ramei
    l = c = rama;           // primul element al ramei
    j = 0;                  // am stocat 0 elemente din rama curenta in aux[]
    for ( dir = 0; dir < 4; dir++ ) { // parcurgem cele patru laturi ale ramei
      suma = tablou[l][c]; // suma laturii curente, initializare cu primul elem
      for ( i = 1; i < n - 2 * rama; i++ ) { // pentru celelalte elemente
        l += dlin[dir];        // avansam pe elementul curent
        c += dcol[dir]; 
        suma += tablou[l][c];  // il adunam la suma
        aux[j] = tablou[l][c]; // si il copiem in vectorul auxiliar
        j++;
      }
      if ( suma > smax ) {  // daca laturii este mai mare
        smax = suma;        // o pastram
        jmax = j - n + 2 * rama + 1; // si tinem minte inceputul laturii
      }
    }
    
    sumatotala += smax; // adunam suma maxima la suma totala
    // copiem aux inapoi in matrice, rotit; parcurgem rama copiind de la jmax
    l = c = rama;
    j = jmax; // indicele primului punct din latura maxima copiata in aux[]
    for ( dir = 0; dir < 4; dir++ ) { // parcurgem cele patru laturi ale ramei
      for ( i = 1; i < n - 2 * rama; i++ ) { // pentru celelalte elemente
        l += dlin[dir];   // avansam pe elementul urmator in rama
        c += dcol[dir];
        tablou[l][c] = aux[j];
        j++;
      }
      j %= (4 * n - 8 * rama - 4); // deplasare circulara in  vectorul aux[]
    }
  }

  fout = fopen( "cifru1.out", "w" );
  fprintf( fout, "%d\n", sumatotala );
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      fprintf( fout, "%d ", tablou[l][c] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Problema Șenila

Problema șenila necesită cunoștințe de baze de numerație și matrice.

Pentru a rezolva problema trebuie să observăm o mică păcăleală: deşi enunţul specifică o codificare a şenilei în baza 2, în realitate fiecare segment al şenilei este o cifră în baza 4. Drept care toate operaţiile din rezolvare trebuie efectuate în baza 4.

Punctul 1: codificarea şenilei

Pentru a rezolva primul punct, codificarea şenilei după K rotaţii va trebui să mutăm ultima cifră a numărului în baza patru de la finalul numărului la începutul numărului. Am mai rezolvat această problemă cu numere zecimale. Vom calcula puterea lui 4 necesară, respectiv 4S-1, deoarece avem S segmente de şenilă. Ultima cifră a numărului în baza 4 este desigur z % 4. Pentru a elimina ultima cifră şi a deplasa numărul spre dreapta vom calcula z / 4. Astfel, formula care roteşte numărul în baza 4 este:

z = z / 4 + z % 4 * p4;

Rămîne de observat că nu are rost să rotim şenila de mai mult de S ori, deoarece o vom lua de la capăt, iar acest calcul poate depăşi timpul. Este suficient să o rotim de K % S ori. Complexitatea va fi O(S), faţă de O(K). Vom face maxim S-1 rotaţii.

Observaţie: putem fi tentaţi să rezolvăm această problemă cu vectori. Este o soluţie posibilă, dar programul va fi mai lung şi mai ineficient. Este o soluţie fie pentru leneşii care nu vor să gîndească, fie pentru cei ce nu stăpînesc bazele de numeraţie.

Punctul 2: coordonatele finale

Pentru a calcula coordonatele finale ale şenilei după A deplasări am putea să efectuăm A deplasări ale şenilei. Această soluţie are complexitatea O(A). Deoarece A poate fi un miliard evident că va depăşi timpul. Ce putem face? Să observăm că după o rotaţie completă a şenilei mişcarea acesteia se va repeta. Drept care putem calcula deplasarea şenilei după o rotaţie completă şi apoi să repetăm această deplasare de cîte ori se execută o rotaţie completă. Deplasarea înseamnă diferenţele pe linie şi pe coloană între punctul de start şi punctul de final. Pentru a repeta deplasarea vom înmulţi aceste diferenţe cu numărul de rotaţii complete. Ultima parte, rotaţia incompleta, va fi simulată separat.

Pentru calculul noii poziţii putem folosi vectori de direcţie. Segmentul de pe pămînt este o cifră în baza patru, ea putînd avea patru valori, corespunzătoare celor patru direcţii.

Complexitatea acestei soluţii este O(S).

Punctul 3: simularea mişcării în matrice

La acest punct trebuie să efectuăm toate mişcările cerute, deoarece ni se cere să calculăm matricea finală. Vom proceda similar cu punctul 2, însă vom efectua R rotaţii. De asemenea, vom avea grijă să înscriem codificarea şenilei la fiecare deplasare în matrice. Vom folosi din nou vectorii de direcţie. În plus, vom folosi tehnica bordării matricei, pentru a simplifica testul de ieşire de pe tablă. Deoarece matricea poate conţine elemente mai mari sau egale cu zero vom iniţializa bordura cu elemente negative, de exemplu cu -1.

Complexitate

Complexitatea totală a acestei rezolvări pare a fi O(S + S + R) care este totuna cu O(S + R) deoarece constanta 2 cu care se înmulţeşte S poate fi ignorată. Dar, deoarece avem de afişat matricea, avem de efectuat M x N operaţii de afişare, care trebuie adăugate la complexitatea finală care este O(S + R + MxN).

Iată un program posibil:

#include <stdio.h>

#define MAXLAT 200

int dlin[4] = { 0, 1, 0, -1 };
int dcol[4] = { 1, 0, -1, 0 };

long long tab[MAXLAT+2][MAXLAT+2];

int main() {
  FILE *fin, *fout;
  int s, k, a, m, n, r, i, kmod, amod, l2, c2, l3, c3;
  long long z, z1, z2, p4;

  fin = fopen( "senila.in", "r" );
  // S Z K A
  // M N L C R
  fscanf( fin, "%d%lld%d%d%d%d%d%d%d", &s, &z, &k, &a, &m, &n, &l3, &c3, &r );
  fclose( fin );

  // punctul 1, codificarea senilei dupa k rotatii
  kmod = k % s; // ce ramine cind scadem rotatiile complete
  p4 = 1;
  for ( i = 1; i < s; i++ ) // puterea lui 4 pentru a extrage prima cifra
    p4 *= 4;
  z1 = z;
  for ( i = 0; i < kmod; i++ )
    z1 = z1 / 4 + z1 % 4 * p4;

  // punctul 2, coordonatele finale
  // simulam o rotatie completa si calculam diferenta de coordonate
  z2 = z;
  l2 = c2 = 0;
  for ( i = 0; i < s; i++ ) {
    l2 += dlin[z2%4];
    c2 += dcol[z2%4];
    z2 = z2 / 4 + z2 % 4 * p4;
  }
  // adunam aceste diferente de cite ori avem o rotatie completa
  l2 = 1 + a / s * l2;
  c2 = 1 + a / s * c2;
  // apoi simulam in continuare pina se termina ultima rotatie, incompleta
  amod = a%s;
  for ( i = 0; i < amod; i++ ) {
    l2 += dlin[z2%4];
    c2 += dcol[z2%4];
    z2 = z2 / 4 + z2 % 4 * p4;
  }

  // punctul 3, simulare pe matrice
  // mai intii bordare cu -1
  for ( i = 0; i <= m + 1; i++ )
    tab[i][0] = tab[i][n+1] = -1;
  for ( i = 1; i <= n; i++ )
    tab[0][i] = tab[m+1][i] = -1;
  // apoi incepem simularea
  // rostogolim cita vreme nu am facut k mutari si mai sintem in tabla
  do {
    tab[l3][c3] = z; // scriem senila la punctul curent
    l3 += dlin[z%4]; // avansam linia
    c3 += dcol[z%4]; // avansam coloana
    z = z / 4 + z % 4 * p4; // rostogolim senila - schimbam codul
    r--; // mai avem r mutari
  } while ( r >= 0 && tab[l3][c3] >= 0 );

  fout = fopen( "senila.out", "w" );
  fprintf( fout, "%lld\n%d %d\n", z1, l2, c2 ); // primele doua puncte
  for ( l3 = 1; l3 <= m; l3++ ) {
    for ( c3 = 1; c3 <= n; c3++ )
      fprintf( fout, "%lld ", tab[l3][c3] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Rezolvări aici: [3]

Lecție

Lecția a constat din discuții despre problemele de la ultimele două teme, ale lecțiilor 25 și 27, respectiv problemele șenila, pește, cutii1, factoriale.

Temă

Tema 28 clasa a 6a

  • atlantis dată la Infotehnium 2019 clasa a 6a avansați
  • pomi dată la Infotehnium 2019 clasa a 6a avansați

Atenție! Această temă va consta din cele două probleme date la concursrul Infotehnium 2019, la clasa a șasea avansati. De aceea tema începe duminică 31 martie 2019. Este posibil să înceapă și sîmbătă noapte.

Rezolvări aici: [4]