Salut.Nu reusesc nicidecum sa rezolv asta:
Un tort dreptunghiular de dimensiuni MxN trebuie împărţit în porţii pătrate de aceeaşi mărime. Cerinţă Găsiţi numărul minim de porţii care se pot obţine şi dimensiunea L a acestora. Atât dimensiunile dreptunghiului cât şi ale pătratelor în care se împarte sunt numere întregi. Date de intrare Fişierul de intrare tort.in va conţine pe prima linie numerele M şi N separate printr-un spaţiu. Date de ieşire Fişierul de ieşire tort.out va conţine pe o singură linie, două numere naturale separate printr-un spaţiu, primul fiind numărul minim de porţii, iar celălalt dimensiunea L. Restricţii 1≤M,N≤10000 Exemple tort.in 20 24 tort.out 30 4
Multumesc!
Sal!
Solutia se bazeaza pe prop divizibilitatii!
Daca notam cu l latura portiei si cu m,n asa cum ai notat tu laturile tortului, atunci solutia problemei va fi data de relatia:
l | m si l | n; (l divide m si l divide n);
Nu se pot aplica proprietatile de suma si diferenta resp inmultire, ar fi favorabila diferenta miscorand cautarea solutiei, din cauza faptului ca ai pastra aria dar ai modifica forma tortului.
Asa ca pleci cu un l = min(m,n), si il micsorezi pana gasesti solutia sistemului
{ L | m, L | n;
Pentru optimizare se poate folosi algoritmul de cautare binara!
Succes! Daca nu reusesti lasi un mesaj si am sa incerc sa iti implementez eu programul in timpul meu liber!
Multumesc larry de raspuns! Dupa multe ore de incercari, am gasit o solutie mai usoara,zic eu.( pt solutia ta ar fi trebuit sa stapanesc cautarea binara…da’ de unde ?)😀
Cum am facut ?
Aria tortului este M x N. Aria unei portii este L x L. Avem k portii, deci:
M x N = k x L x L => k = (M x N)/(L x L)
Vrem sa obtinem un numar minim de portii. De asemenea stim ca M, N, L si k sunt numere naturale nenule.
Se observa, din aceasta restrictie, ca L trebuie sa divida atat M cat si N. Deoarece k trebuie sa fie minim, reiese ca L trebuie sa fie cel mai mare divizor al numerelor M si N.
Am gasit si eu solutia ta, numai ca nu sunt sigur daca e ok di cauza faptului ca lucrand cu arii modifici forma dreptunghiului deoarece m*n = m’*n’ unde m != m’ si n != n’;
Si la solutia asta se poate folosi cautarea binara pentru optimizarea cautarii!
Daca ai luat punctaj maxim pe ea atunci e ok!:D