Clasa a VI-a lecția 31 - 11 apr 2019

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Problema agent

Problema agent 007 a fost dată la Olimpiada locală 2015, clasa a 6a.

Iată o soluție posibilă (41 linii de cod):

#include <stdio.h>

char mesaj[2][679]; // ultimele doua mesaje generate (678 car. + terminator)

int main() {
  FILE *fin, *fout;
  int n, i, j, k, nrc, f;

  mesaj[0][0] = 1;
  fin = fopen( "agent.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  f = 0;                      // ultimul mesaj calculat este mesaj[f]
  for ( k = 1; k < n; k++ ) { // cita vreme mai avem mesaje de calculat
    f = 1 - f; // trecem pe noua pozitie a mesajului
    i = j = 0; // i = indice in mesajul vechi, j = indice in cel nou
    nrc = 1;   // caracterul se repeta de nrc ori (initial o data)
    while ( mesaj[1-f][i] != 0 ) { // cita vreme mai avem car. in mesajul vechi
      i++;                         // avansam la urmatorul caracter
      if ( mesaj[1-f][i] != mesaj[1-f][i-1] ) { // caract. diferit de anterior?
        mesaj[f][j] = nrc; // stocam perechea curenta in noul mesaj
        mesaj[f][j+1] = mesaj[1-f][i-1];
        j += 2;            // avansam indicele in mesajul nou
        nrc = 0;           // caract. a aparut de 0 ori (e incrementat mai jos)
      }
      nrc++;                  // marim numarul de aparitii
    }
  }
  
  fout = fopen( "agent.out", "w" );
  i = 0;
  while ( mesaj[f][i] != 0 ) { // afisam mesajul curent pina dam de zero
    fputc( mesaj[f][i] + '0', fout );
    i++;
  }
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Ea nu este ușor de estimat. Știm însă că vom avea n iterații, fiecare a maxim 679 de operații. Deci, putem supraestima complexitatea ca fiind O(n·MAX_L). Înlocuind numerele cu maxim obținem circa 15000 de operații.

Observație: unii din voi au dat o soluție foarte simpatică în care toate răspunsurile sînt precalculate într-un vector preinițializat. Acest vector este, evident, calculat de un alt program care, în fapt, rezolvă cu adevărat problema. Apreciez foarte mult astfel de soluții, care sînt în spiritul de hacker caracterizat de către Richard Stallman (părintele free software și GNU/Linux) drept playful cleverness. În același spirit, vă invit să vedeți o soluție cu aceeași idee, dar de două ori mai mică. Căutați soluțiile mele la problemă pe varena.

Problema debarcare

Problema debarcare a fost dată la ONI 2003 clasa a 7a.

Iată o soluție posibilă:

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

char linie[81];
long long col[9];

int main() {
  FILE *fin, *fout;
  int n, c, i, ncol, ucf, pcf, sens;

  fin = fopen( "debarcare.in", "r" );
  n = 0;
  while ( (c = fgetc( fin )) != '\n' ) {
    linie[n] = ('0' <= c && c <= '9') ? c - '0' : c - 'A' + 10;
    n++;
  }
  fclose( fin );

  ncol = sqrt( n );         // calcul numar coloane
  for ( i = 0; i < n; i++ ) // calcul numere pe fiecare coloana
    col[i % ncol] = col[i % ncol] * 16 + linie[i];

  fout = fopen( "debarcare.out", "w" );
  fprintf( fout, "%d\n", ncol ); // afisam numarul de coloane
  for ( i = 0; i < ncol; i++ ) { // pentru fiecare coloana
    ucf = col[i] % 10;  // calculam ultima cifra si penultima
    col[i] /= 10;
    pcf = col[i] % 10;
    sens = pcf - ucf;   // stabilim sensul de crestere
    if ( sens != 0 ) {  // daca ultimele doua cifre n-au fost egale
      do {              // comparam ultimele doua cifre cita vreme
        ucf = pcf;      // au acelasi sens ca 'sens'
        col[i] /= 10;
        pcf = col[i] % 10;
      } while ( col[i] > 0 &&
                ((pcf < ucf && sens < 0) || (pcf > ucf && sens > 0)) );
      if ( col[i] == 0 ) { // daca am consumat tot numarul, nu este mixt
        if ( sens < 0 )
          fprintf( fout, "infanterie\n" );
        else
          fprintf( fout, "aviatie\n" );
      } else // daca numarul nu e zero am gasit o neconcordanta, deci e mixt
        fprintf( fout, "mixt\n" );
    } else
      fprintf( fout, "mixt\n" );
  }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Citirea și calculul numerelor este, desigur, O(n). Apoi, avem {\sqrt  {n}} numere, pe care le vom prelucra calculînd fiecare cifră a lor. Ele vor avea tot {\sqrt  {n}} cifre în baza 16. Deși vor fi ceva mai multe cifre în baza zece vom vedea în clasa a zecea cînd învățăm proprietățile logaritmilor că numărul de cifre în baza 10 diferă de cel în baza 16 printr-o constantă, deci nu inluențează complexitatea.

Rezultă o complexitate totală de O(n) atît ca timp cît și ca memorie. n fiind ridicol de mic, o sută, soluția se va încadra în limite.

Observații: am văzut multe soluții care repetă cod. Ele rescriu codul pentru cele două cazuri, cifre crescătoare sau descrescătoare. Nu este bine. Nu uitați să factorizați codul! Puteți face acest lucru suprapunînd porțiunile de cod aproape identic și parametrizîndu-le, adică înlocuind diferențele cu variabile. Vedeți exemplul de mai sus.

Problema numere9

Problema numere9 a fost dată (într-o formă simplificată) la OJI 2017 clasa clasa a 5a.

Ea este o problemă profund matematică. k este atît de mare încît nu putem calcula linia pe care se află el într-o buclă, avem nevoie de o formulă.

Mai exact, pentru a calcula suma cerută vom proceda astfel:

  • Calculăm linia l pe care se află k
  • Calculăm suma ultimelor numere pe fiecare linie, pînă la x inclusiv, unde x este ultimul număr de pe linia lui k.
  • Observăm că diferența de la această sumă la suma cerută este Gaussx - k.

Să luăm cei trei pași pe rînd:

Linia l pe care se află k

Ne propunem mai întîi să calculăm l, numărul liniei pe care se află k.

Dacă l este linia pe care se află k ne propunem să aflăm numărul liniei l. Nu intru în detalii, primul număr pe linia l este:

1 + l · (l - 1) / 2

Avem deci inecuația:

1 + l · (l - 1) / 2 ≤ k

Înmulțim cu 2:

2 + l · (l - 1) ≤ 2k

Desfacem parantezele:

2 + l2 - l ≤ 2k

Avem și aici două variante.

Varianta de clasa a 6a

Putem să scriem inecuația de mai sus astfel:

l2 ≤ 2k - 2 + l

Dacă vom calcula {\sqrt  {2k-2}} vom obține un număr mai mic sau egal cu cel real. Drept care este posibil să trebuiască să ajustăm în sus acest număr, cu maxim o unitate (de ce?). Cu alte cuvinte, codul care va calcula linia este:

  l = sqrtl(2 * k - 2);          // linia pe care se afla k
  if ( l * (l + 1) / 2 < k )     // posibila ajustare
    l++;

Aici avem nevoie de funcția sqrtl() deoarece 2k depășește tipul întreg.

Avem astfel linia l pe care se află numărul k.

Observație importantă: mulți dintre voi au calculat sqrtl(2 * k). Deși funcționează este matematic incorect! Putem găsi teste pe care codul nu va funcționa (găsiți-le voi). Din nefericire testele actuale nu diferențiază între formula corectă și cea incorectă (probabil acest lucru se întîmplă pentru l mic iar testele sînt mari).

Varianta de clasa a 8a

Avem o variantă mai elegantă, care necesită cunoașterea soluției ecuației de gradul doi. Inecuația originală:

2 + l2 - l ≤ 2k

se poate scrie astfel:

l2 - l - 2k + 2 ≤ 0

care, rezolvînd inecuația și punînd condiția ca l ≥ 0 se transformă în:

l ≤ (1 + {\sqrt  {8k-7}}) / 2

Astfel, codul care va calcula l fără a folosi condiții devine:

l = (sqrtl( 8 * k - 7 ) + 1) / 2; // linia pe care se afla k

Această soluție este mai elegantă deoarece nu folosește condiții. Este ea și mai rapidă? Probabil că nu, iar diferența este oricum nesemnificativă :-)

Suma numerelor pînă la x

Se observă că x este:

x = Gaussl

adică suma numerelor de la 1 la l. Vrem să calculăm suma ultimelor numere pe fiecare linie pînă la l. Drept care avem de calculat:

s = Gauss1 + Gauss2 + Gauss3 + ... + Gaussl

Aceasta este, iarăși matematică de nivel ceva mai mare decît clasa a 6a, dar care poate fi înțeleasă. Nu intru aici în detalii, dar suma de mai sus se calculează ca fiind:

s = l(l + 1)(l + 2) / 6

Atenție! Nu putem calcula această sumă direct, deoarece vom obține o depășire de long long. O variantă simplă este să aflăm care din cei trei factori se împarte la 3 și să îl simplificăm. Astfel codul devine:

  s = l * (l + 1) / 2;
  if (s % 3 == 0)
    s = s / 3 % MOD * (l + 2) % MOD;
  else
    s = s % MOD * ((l + 2) / 3 % MOD) % MOD;

Există și o soluție bazată pe calculul inversului numărului 6 modulo MOD, dar voi intra în detalii. Pentru curioși, algoritmul lui Euclid extins calculează eficient inversul unui număr modulo MOD. Acest algoritm va face mai multe calcule decît cel de mai sus.

Suma finală

Observăm că diferența de la această sumă la suma cerută este Gaussx - k. Pentru aceasta faceți un desen și observați că din momentul cînd calea către x se desparte de calea către k diferențele dintre perechile de numere pe fiecare linie vor fi 1, 2, 3, ..., x - k. Toate aceste diferențe trebuie scăzute.

Iată o soluție bazată pe aceste idei, incluzînd ecuația de gradul doi:

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

#define MOD 1953752261

int main() {
  FILE *fin, *fout;
  long long k, x, d, l, s;
  
  fin = fopen( "numere9.in", "r" );
  fscanf( fin, "%lld", &k );
  l = (sqrtl( 8 * k - 7 ) + 1) / 2; // linia pe care se afla k
  x = l * (l + 1) / 2;           // ultimul nr din linia l
  d = x - k;                     // diferenta pe linie intre k si x
  // suma pina la x, ultimul din linie
  // calculează l * (l + 1) * (l + 2) / 6 % MOD
  s = l * (l + 1) / 2;
  if (s % 3 == 0)
    s = s / 3 % MOD * (l + 2) % MOD;
  else
    s = s % MOD * ((l + 2) / 3 % MOD) % MOD;
  s -= ((d % MOD) * ((d + 1) % MOD) / 2) % MOD; // diferenta sumei de la x la k
  s = (s + MOD) % MOD;           // in caz ca era negativa
  fclose( fin );

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

  return 0;
}

Ce complexitate are această soluție?

în mod evident O(1), deoarece nu avem bucle.

Problema flori6

Problema flori6 a fost dată la OJI 2006 clasa a 9a.

Este, în fapt, o problemă mascată de grafuri, adică de clasa a 11a. Faptul că a fost dată la o clasă mult mai mică mă face să mă tem că ar putea da ceva similar la clasa a șasea, drept care v-am dat-o ca temă.

Există mai multe soluții posibile, foarte diferite între ele. Voi descrie una care mi se pare cel mai simplu de înțeles. Vom proceda astfel:

  • Pentru fiecare fată memorăm buchetul mulțime, nu ne interesază florile duplicat. Vom memora, astfel, un vector de frecvență al florilor din toate buchetele.
  • Pentru fiecare floare posibilă:
    • Grupăm toate fetele ce o dețin
    • Construim un buchet al grupului care constă din reuniunea buchetelor fetelor din grup
    • Păstrăm în algoritm fata cu numărul cel mai mic din grup, căreia îi atașăm reuniunea buchetelor
    • Celelalte fete nu mai intră în calcul la pașii următori, dar vor fi marcate ca avînd ca reprezentantă fata cu numărul cel mai mic
  • La final calculăm pentru fiecare fată reprezentanta reprezentantei, și așa mai departe pînă găsim fata minimă.
  • Pentru fiecare fată ce nu are reprezentantă (este prima în grupul ei) o afișăm împreună cu toate fetele care o au ca reprezentant.

Iată o soluție posibilă:

#include <stdio.h>

#define MAX_FETE 150
#define MAX_FLOARE 100

// buchet[l][c] = 1 daca fata 'l' are macar o floare de tip 'c'
char buchet[MAX_FETE][MAX_FLOARE + 1];
// reprezentant [l] = fata reprezentanta a grupului fetei 'l'
char reprezentant[MAX_FETE];

int main() {
  FILE *fin, *fout;
  int n, k, l, i, floare, prima;

  fin = fopen( "flori6.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( l = 0; l < n; l++ )
    for ( i = 0; i < k; i++ ) {
      fscanf( fin, "%d", &floare );
      buchet[l][floare] = 1; // fata 'l' are o floare de tip 'floare'
    }
  fclose( fin );

  // cream grupurile
  // pentru fiecare tip de floare punem in acelasi grup fetele care o au
  // cind punem doua fete in acelasi grup grupul va contine reuniunea
  // florilor acelor fete - transferate la reprezentantul grupului
  for ( floare = 0; floare <= MAX_FLOARE; floare++ ) {
    prima = -1;
    for ( l = 0; l < n; l++ )
      if ( reprezentant[l] == 0 ) { // fata nu face parte deja dintr-un grup
        if ( buchet[l][floare] > 0 ) { // are floare de tip 'floare'
          if ( prima == -1 ) // avem o prima fata ce are floarea 'floare'
            prima = l;       // retinem numarul ei
          else { // adaugam fata 'l' la 'prima'
            reprezentant[l] = prima + 1; // +1 sa o deosebim de zero
            // amestecam buchetele - dam florile fetei 'l' fetei 'prima'
            for ( i = 0; i <= MAX_FLOARE; i++ )
              if ( buchet[l][i] > 0 )
                buchet[prima][i] = 1;
          }
        }
      }
  }

  // pentru fiecare fata aflam din ce grup face parte
  // pentru aceasta urmarim linia reprezentantilor pina ce ajungem la
  // o fata cu reprezentant zero, insemnind ca e ea este reprezentanta
  // grupului
  for ( l = 0; l < n; l++ )
    if ( (i = reprezentant[l]) != 0 ) {  // fata 'l' are reprezentant?
      while ( reprezentant[i - 1] != 0 ) // cata vreme 'i' are reprezentant
        i = reprezentant[i - 1];         // avansam pe el
      reprezentant[l] = i; // la final retinem reprezentantul fetei 'l'
    }

  fout = fopen( "flori6.out", "w" );
  // afisam grupurile
  // pentru fiecare fata 'l' care nu are reprezentant
  // o afisam pe ea si toate fetele care o au ca reprezentant
  for ( l = 0; l < n; l++ )
    if ( reprezentant[l] == 0 ) {   // prima din grup, ii afisam grupul
      fprintf( fout, "%d", l + 1 ); // mai intii o afisam pe ea
      for ( i = l + 1; i < n; i++ ) // apoi cautam in restul de fete
        if ( reprezentant[i] == l + 1 )  // pe cele care o au ca reprezentant
          fprintf( fout, " %d", i + 1 );
      fprintf( fout, "\n" );
    }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

  • Citirea este O(n·k).
  • Calculul grupurilor este O(n·MAX_FLOARE) (De ce? Ar putea să pară că este O(n·MAX_FLOARE2), nu?)
  • Calculul reprezentantelor este O(n2).
  • Afișarea este O(n2).

Rezultă o complexitate totală de O(n·MAX_FLOARE + n2). Făcînd înlocuirile rezultă circa 32500 operații, ceea ce se va încadra ușor în timpul alocat, de o secundă. În fapt, algoritmul este dominat de citire (în caz că vă întrebați cum este posibil ca la testul 10 timpul să fie diferit de zero).

Cîtă memorie folosim? O(n·MAX_FLOARE), sau, mai exact, 15kb.

Rezolvări aici: [1]

Lecție

Lecția constă din discuții ale problemelor de la temă.

Temă

Tema 31 clasa a 6a

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

Concurs clasa a 6a

Rezolvări aici: [2]