Clasa a V-a lecția 38 - 26 apr 2018

Tema - rezolvări

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-04-26-lectie-info-38-720p.mp4</html5media>

Discuție despre problemele de la ONI 2018 clasa a 5^a, pe care le veți avea apoi ca temă pentru acasă.

Problema desen

Problema desen a fost dată la ONI 2018 clasa a 5^a. Ea este o problemă banală, de primele lecții de informatică. Ea este însă complicată de o chichiță, și anume de posibilitatea de depășire a numerelor întregi. Ea nu testează talentul vostru informatic, ci cunoștințele voastre de reprezentare a numerelor în calculator, cunoștințe ce nu au ce căuta în primele luni de informatică, la clasa a cincea, la început de drum.

Drept dovadă că reprezentarea numerelor în calculator este cunoștință de nivel înalt, chiar și profesorii pot avea probleme cu ea. Iată, soluțiile C/C++ ale comisiei la această problemă folosesc tipul unsigned long long (tip nemaifolosit in istoria olimpiade naționale la clasa a cincea, din cîte știu eu). În realitate problema se poate rezolva folosind tipul long long, nefiind necesară încărcarea cunoștințelor voastre cu încă un tip de întreg, cînd deja trebuie să știți trei: char, int, long long.

Desen este, deci, o problemă foarte slabă din punct de vedere al testării cunoștințelor voastre algoritmice, creată să pice acei elevi care nu știu tipuri de întregi la limită, dar, chiar și din acest punct de vedere eșuează deoarece comisia pierde din vedere o soluție mai simplă.

Acestea fiind zise, să analizăm puțin această problemă. Ea are un enunț mediu ca lungime, și un desen de triunghiuri imbricate care poate părea înfricoșător la prima vedere. Însă, dacă urmărim cu atenție cerințele, observăm următoarele:

Cerința 1

Cerința 1 ne cere să calculăm numerele triunghiurilor de început și de sfîrșit din pasul în care se obține triunghiul K. Dacă ne uităm la proprietățile acestor numere se observă lejer că ele sînt puteri ale lui doi. Fiecare pas începe cu un număr putere a lui doi și se termină cu numărul cu unu mai mic decît următoarea putere a lui doi. Va trebui, deci, să încadrăm numărul K între două puteri ale lui doi.

Cerința 2

Cerința 2 ne cere să afișăm triunghiurile care includ triunghiul cu numărul K. Din nou, regula se observă lejer, triunghiul din care se formează K este jumătatea întreagă a numărului K. Vom continua să împărțim K la doi și să afișăm valorile obținute. Deoarece trebuie să afișăm acele valori în ordine crescătoare, le vom memora într-un vector, pe care îl vom parcurge apoi în sens invers.

Unde ne-am putea încurca? La cerința 1, pentru a căuta cea mai mare putere a lui doi mai mică sau egală cu K am putea fi tentați să scriem:

Problema mostenire

Problema mostenire a fost dată la ONI 2018 clasa a 5^a. Este o problemă complexă dar rezolvabilă în totalitate cu cunoștințe de clasa a 5^a.

Am fi tentați să rezolvăm cele două cerințe separat. Și rezolvările comisiei fac acest lucru. Este însă preferabil să tratăm cele două cazuri împreună, pentru a evita repetiția de cod.

"Carnea" oricărei rezolvări este modificarea secvențelor din parolă în mod repetat, de K ori. O modificare constă în parcurgerea unei secvențe de cifre, între pozițiile S și D, și înlocuirea fiecărei cifre cu o altă cifră, conform cheii Q. Mai exact, o cifră c se înlocuiește cu cifra aflată pe poziția c în cheia Q.

Aceasta s-ar întîmpla dacă am urmări algoritmul regelui. Însă noi avem la intrare ultima parolă, nu prima. De aceea noi va trebui să facem modificările în sens invers. Care este inversul înlocurii cifrei c cu cifra de pe poziția c? Vom înlocui cifra c cu poziția pe care se află cifra c în Q. De aceea ar fi bine să construim un vector care pentru fiecare din cele nouă cifre nenule păstrează poziția acelei cifre în cheia Q. Cum construim acest vector? Știm că ultima cifră a lui Q are poziția 9. Dacă o eliminăm din Q prin împărțire la 10, ultima cifră din noul Q va avea poziția 8. Repetăm procedeul pentru toate cele nouă cifre ale cheii Q. Rezultă codul:

  int inloc[10];
  ...
  for ( poz = 9; poz > 0; poz-- ) {
    inloc[q % 10] = poz;
    q /= 10;
  }

Avînd aceste observații generale, să vedem, pe rînd, cum tratăm cele două cerințe:

Cerința 1

Cum prelucrăm parola finală, pentru a o obține pe cea inițială? E relativ simplu, pentru fiecare pereche (S D) vom parcurge pozițiile din parolă dintre S și D și vom înlocui valorile parola[j] cu inloc[parola[j]]. Atenție: perechile (S D) vor trebui parcurse în ordine inversă decît se dau ele la intrare, deoarece noi mergem înapoi pe modificările regelui. Aceasta înseamnă ca va trebui să memorăm aceste valori în doi vectori, s[] și d[].

Cerința 2

Cerința 2 are de fapt două subcerințe:

Subcerința 1: cea mai des modificată poziție

Ni se cere să găsim poziția din parolă care a fost cel mai des modificată, iar dacă sînt mai multe astfel de poziții se cere cea minimă. Cum rezolvăm această cerință? Să observăm următoarele:

1. Pozițiile care se modifică sînt cele între perechile (S D)
2. Perechile (S D) pot fi văzute ca segmente sau intervale de numere în cadrul parolei
3. Ni se cere să aflăm poziția din parolă unde se suprapun cît mai multe segmente (intervale)

Putem afla pentru fiecare din pozițiile din parolă de cîte ori a fost modificată, în cei K ani? Pentru aceasta ar trebui să folosim un vector, nrap[], care pentru fiecare poziție din parolă memorează numărul de modificări. El ar fi un vector de frecvență a modificărilor, nu-i așa? Cum calculăm acest vector? Pentru fiecare pereche (S D) știm pozițiile atinse: vom aduna unu la toate pozițiile din nrap[] între S și D, deoarece ele vor fi modificate. La final poziția maximului în nrap[] este chiar poziția căutată (mai exact poziția primului maxim).

Cînd vom calcula vectorul nrap[]? Să ne aducem aminte că va trebui să păstrăm valorile S și D în doi vectori, pentru a le putea parcurge în ordine inversă. Putem, deci, calcula vectorul nrap[] chiar la citirea acestor valori.

Subcerința 2: cifrele ce apar pe cea mai modificată poziție

Ni se cere ca, pentru poziția cel mai des modificată, să afișăm toate cifrele care au apărut pe acea poziție pe parcursul modificărilor aduse de rege. Este, cred, destul de clar că odată ce știm poziția cel mai des modificată, să-i spunem poz, putem să calculăm cifrele ce apar pe acea poziție foarte ușor: oricum vom prelucra parola finală pentru a o calcula pe cea inițîală, nu-i așa? În timp ce calculăm modificările, după fiecare din modificări, vom adăuga cifra de pe poziția poz la mulțimea cifrelor ce au apărut pe poziția poz. Cum păstrăm această mulțime de cifre? Pentru ușurință o vom păstra ca un vector de frecvență, să-i spunem cfpoz[].

La final vom afișa pozițiile din cfpoz[] unde avem elemente nenule.

Problema pyk

Problema pyk a fost dată la ONI 2018 clasa a 5^a.

Problema are o primă cerință foarte stranie, deoarece nu are nici o legătură cu cerința a doua. Ea fiind banală, este clar că există pentru ca și elevii slabi să ia zece puncte. Ceea ce o face și mai stranie este faptul că, deși din enunț rezultă că ea ar fi trebuit punctată cu 10p, în realitate ea a fost punctată cu 15p, ceea ce mă duce cu gîndul exact la "săltarea" elevilor slabi. Dat fiind că au fost circa 8 elevi care au rezolvat cerința doi, rezultatele ar fi arătat rău cu o primă cerință punctată doar 10p: marea majoritate a elevilor ar fi avut sub 10p. Așa, ei au 15p, ceva mai bine.

În concluzie nu vom trata punctul unu, el fiind banal, mult prea ușor pentru olimpiada națională.

Enunțul cerinței doi este unul destul de matematic. Pe scurt, ea cere să completăm un produs de numere x_i prin înmulțirea cu un alt număr y, pentru a îl aduce la forma unui număr la puterea k.

O rezolvare forță brută ar putea fi să calculăm numărul x, produsul numerelor x_i, iar apoi să căutăm numere la puterea k, din ce în ce mai mari, care să se împartă la x. Această soluție va depăși numerele long long pentru multe din testele de la intrare.

Să observăm un lucru important: problema nu ne cere să optimizăm timpul execuției algoritmului nostru. Ea ne cere să optimizăm algoritmul astfel încît el să se încadreze în tipul întreg. Ca și la problema unu, desen, accentul se pune pe depășirea întreagă, în loc să se pună pe cunoștințele voastre de algoritmică. Problema devine astfel una de clasa a șasea. Din nou comisia dovedește o înțelegere superficială a complexității problemei în cadrul unei programe de olimpiadă extrem de vag specificată.

Ceea ce este și mai straniu este faptul că rezolvărea comisiei este una inutil de complicată. Îmi este absolut neclar la ce ar putea folosi ciurul lui Eratostene în rezolvare, așa cum ne spune comisia.

Să încercăm să rezolvăm această problemă. Cum ne putem da seama dacă un produs de numere este ceva la puterea k? Deoarece nu ni se cere numărul y, ci descompunerea sa în factori primi, aceasta ne sugerează ideea să analizăm descompunerea în factori primi a produsului x₁ * x₂ * x₃ * ... * x_n. Dacă am avea o descompunere în factori primi a unui număr, care este condiția ca el să fie ceva la puterea k? Să considerăm următoarea descompunere în factori primi:

p = a₁^p₁ · a₂^p₂ · a₃^p₃ · ... · a_m^p_m

Deoarece factorii a_i sînt primi ei nu pot forma ceva la puterea k. De aceea este necesar ca fiecare factor a_i^p_i să fie de forma ceva la puterea k. Dar pentru aceasta este necesar ca p_i să fie divizibil cu k.

Ce facem dacă o putere p_i nu este divizibilă cu k? Va trebui ca numărul a_i^p_i să fie completat prin înmulțirea cu a_i, pînă ce obținem un a_i^p_i+j astfel încît p_i+j este divizibil cu k.

Se conturează un algoritm, nu-i așa? Putem calcula descompunerea în factori primi a fiecărui număr x_i de la intrare. Cumva vom îmbina aceste descompuneri în factori primi pentru a obține descompunerea în factori primi a produsului celor n numere. Apoi vom calcula completările necesare pentru a obține un număr de forma ceva la puterea k. Acele completări vor forma numărul y cerut.

Cum vom calcula descompunerea în factori primi a produsului? Va trebui să memorăm perechi de forma a_i^p_i. Pentru fiecare factor prim a_i va trebui să calculăm de cîte ori apare el în toate numerele x_i de la intrare. Cu alte cuvinte, atunci cînd descompunem un număr x_i în factori primi va trebui să adunăm puterile factorilor obținuți la puterile anterioare, din celelalte descompuneri în factori primi.

Pentru un factor prim a la puterea p va trebui să adunăm rapid p în dreptul factorului a. De aceea ne ducem cu gîndul la un vector, să-i spunem pf[]. Astfel, pf[a] va fi numărul de apariții ale lui a în toate numerele x de la intrare. Astfel, vectorul pf[] este un vector de frecvență.

Folosind aceste idei, algoritmul va fi următorul:

// calculeaza descompunerea in factori primi a produsului numerelor de la intrare
1. Pentru fiecare număr x citit la intrare:
  1.1 Descompune x in factori primi
  1.2 Pentru fiecare produs a<sup>p</sup> din x:
    1.2.1 Adună p la pf[a]

// calculeaza descompunerea in factori primi a numarului completare, y
2. Pentru fiecare produs a<sup>pf[a]</sup> din pf[] calculat anterior:
  2.1 Calculează cel mai mic număr j astfel încît pf[a]+j să fie divizibil cu k
  2.2 Dacă j > 0 păstrează perechea (a j)

3. Afiseaza perechile păstrate la punctul anterior

Atenție! Ce trebuie să avem grijă?

• Descompunerea în factori primi trebuie făcută eficient, pînă la radical din x, altfel este posibil să depășim timpul.
• Dacă toate puterile din vectorul pf[] sînt divizibile cu k ar rezulta că y are valoarea 1. Acest lucru este interzis de restricțiile problemei (deși nu foarte explicit), deoarece se cere ca y să fie minim 2. În acest caz y minim care îndeplinește condițiile este 2^k

Temă

Tema 38: să se rezolve următoarele probleme (program C trimis la vianuarena):

• desen dată la ONI 2018 clasa a 5^a
• moștenire dată la ONI 2018 clasa a 5^a
• pyk dată la ONI 2018 clasa a 5^a

Rezolvări aici [2]