Clasa a V-a lecția 26 - 24 feb 2015

Tema - rezolvări

Rezolvări aici [1]

Lecţie

Discuţie despre problemele de la olimpiada pe sector.

Problema crioac

Această problemă ne cere ca, dîndu-se două parcurgeri ale unui rînd de pătrate, să calculăm numărul minim de salturi în care se poate parcurge rîndul, precum şi punctul de întîlnire al celor două parcurgeri (dacă există).

Ambele puncte ale acestei probleme pot fi rezolvate printr-un calcul direct, iterativ (în buclă), sau mai elegant, prin formule matematice. Să le luăm pe rînd.

Numărul minim de salturi

Pentru a calcula în cîte salturi parcurge greierele aleea am putea să scriem o buclă while în care, la fiecare pas, să adunăm un salt la distanţa parcursă. Astfel, vom aduna X pînă ce numărul de pătrate parcurse devine mai mare sau egal cu N. La fiecare adunare vom contoriza unu într-un contor. La final valoarea contorului este chiar numărul de salturi. Vom proceda similar pentru a calcula numărul de salturi ale broscuţei. Apoi vom calcula şi afişa minimul.

Există şi o variantă mai simplă, daca observăm că, în fapt, avem următoarea relaţie între numărul de salturi şi mărimea unui salt:

K x X > N

De aici putem calcula K ca fiind

K > N / X

Deoarece N / X poate fi un număr fracţionar rezultă că, de fapt, K este primul întreg mai mare strict decît partea întreagă a lui N / X. Pentru aceasta avem formula:

K = N / X + 1

Astfel, folosind matematica, am redus soluţia primului punct la o singură atribuire constînd dintr-un calcul matematic.

Numărul dalei de întîlnire

Şi aici avem o soluţie directă, în care folosim o buclă while. La fiecare pas vom deplasa greierele cu X pătrate şi broscuţa cu Y pătrate. Ne vom opri atunci cînd pătratul greierului devine mai mare sau egal cu cel al broscuţei, moment la care ne vom întreba dacă ele sînt chiar egale, caz în care cei doi se întîlnesc.

Există şi o variantă mai simplă, dacă observăm relaţia dintre numărul de salturi şi mărimile celor două salturi. Care este dala unde se află greierele după K salturi? Ea este:

Dg = K x X

Similar, căsuţa unde se află broscuţa este

Db = N - K x Y + 1

Pentru ca cei doi să se întîlnească trebuie să existe un număr de salturi K după care cele două dale să fie egale:

Dg = Db, adică
K x X = N - K x Y + 1, adică
K x X + K x Y = N + 1, adică
K x (X + Y) = N + 1

De aici rezultă că trebuie ca numărul de paşi înmulţit cu suma distanţelor parcurse în fiecare pas trebuie sa acopere întreaga alee exact. Cu alte cuvinte, trebuie ca numărul N + 1 să fie divizibil cu X + Y, caz în care avem numărul de paşi K:

K = (N + 1) / (X + Y)

iar dala cerută va fi

D = K x X = (N + 1) / (X + Y) x X

Astfel, întreaga problemă se poate rezolva în trei rînduri de calcul.

Problema magic

Problema magic ne cere să calculăm, pe rînd:

• Să calculăm un număr N pe baza reprezentării lui în baza doi formată din K cifre binare.
• Să calculăm cele mai mari numere de două cifre incluse în N, considerînd cele două parcurgeri ale lui N, de la prima cifră către ultima, sau de la ultima cifră către prima (atenţie la o excepţie).
• Să calculăm produsul acestor două numere
• Să calculăm cel mai mare pătrat perfect P care îl divide pe N

Problema se rezolvă urmărind îndeaproape enunţul. Vom citi cele K cifre, pe rînd şi vom actualiza numărul N cu formula:

n = n * 2 + cf;

unde cf este cifra binară citită la intrare. Apoi vom extrage, pe rînd, numerele de două cifre din coada numărului, calculînd restul împărţirii la 100. Pentru fiecare astfel de număr de două cifre vom calcula şi răsturnatul său, pentru a obţine numerele de două cifre din parcurgerea în ordine inversă. Trebuie să calculăm maximul dintre aceste numere, precum şi următorul maxim, diferit de el, deoarece enunţul cere ca numerele să fie distincte. De aceea va trebui să calculăm şi maximul al doilea, pentru acest caz. Atenţie la cazul cînd numărul este format dintr-o singură cifră repetata! În final vom calcula produsul acestor două numere.

În final trebuie să calculăm cel mai mare pătrat perfect, P, la care se împarte produsul calculat anterior. Putem face acest lucru direct: vom calcula într-o buclă pătratele perfecte 1 x 1, 2 x 2, 3 x 3, etc., întrebîndu-ne dacă ele divid produsul nostru. Îl vom memora pe cel mai mare. Ne vom opri atunci cînd pătratul perfect depăşeşte produsul.

O metodă similară, ceva mai bună, este să pornim în sens invers: de la pătratul radicalului produsului, mergînd în jos. Ne vom opri la primul pătrat care divide produsul.

Există şi o altă metodă, bazată pe descompunerea în factori primi, dar nu vom intra in detalii aici.

Temă

Tema 26 clasa a 5-a ce constă din probleme date la OJI 2013

• bețe
• chibrituri

Rezolvări aici [2]