infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: Marius Stroe din Aprilie 11, 2009, 16:08:12



Titlul: Probleme cu puncte laticiale
Scris de: Marius Stroe din Aprilie 11, 2009, 16:08:12
Comentarii la articolul Probleme cu puncte laticiale (http://infoarena.ro/probleme-cu-puncte-laticiale) scris de Cosmin Negruşeri (http://infoarena.ro/utilizator/cosmin).

Îi mulţumim Alexandrei Diculescu (http://infoarena.ro/utilizator/portocala) pentru că s-a implicat în transcrierea lui.


Titlul: Răspuns: Probleme cu puncte laticiale
Scris de: Florian Marcu din Aprilie 30, 2009, 18:27:19
Legat de problema #7 ( paralelograme ): Spre sfarsitul explicatiei de la rezolvare, se da urmatoarea idee de optimizare:
Citat
Mai putem optimiza factorii constanţi ai soluţiei observând că într-un triunghi de dimensiuni H * W poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un triunghi W * H. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.
La ce triunghiuri se refera?  :-k


Titlul: Răspuns: Probleme cu puncte laticiale
Scris de: Cosmin Negruseri din Aprilie 30, 2009, 21:55:46
Am corectat la dreptunghi.

Cand vezi ceva gresit poti sa corectezi chiar tu. Siteul este wiki si va incurajam sa fiti activi nu pasivi.


Titlul: Răspuns: Probleme cu puncte laticiale
Scris de: Dragos din Iulie 24, 2010, 16:47:28
La problema 5  avem formula 4 * ((H - 1)(W - 1) + H - 1 + W - 1).

Factorul 4 reprezinta cele 4 pozitii ale primului punct.
Produsul (H - 1)(W - 1) toate perechile care se pot forma intre ultimele H-1 puncte de pe verticala si primele W-1 puncte de pe orizontala?
H-1 repezinta numarul de puncte de pe verticala pe care le putem imperechea cu al W-lea de pe orizontala?
Iar W-1 reprezinta numarul de puncte de pe orizontala pe care le putem imperechea cu primul de pe verticala?
 
Later edit:
Iar la problema 7 avem h * w - cmmdc(h - 1, w - 1) - 2 posibilităţi
Pentru diagonala avem cmmdc(h - 1, w - 1) +1 posibilitati si mai eliminam un 1 deoarece putem obtine un patrat de 2 ori?
(Scuzati-ma daca nu se intelege bine ce am scris).

Later later edit:
Si tot la problema 7 la seventa de cod este o mica greseala.
Este scris:
Cod:
 num += (N - h + 1) * (M - w + 1) * laux;
si trebuia
Cod:
 num += (N - h + 2) * (M - w + 2) * laux;
pentru ca N si M sunt numarul de randuri respectiv coloane deci numarul de puncte pe verticala este N+1 iar pe orizontala M+1.
Pot sa modific?


Titlul: Răspuns: Probleme cu puncte laticiale
Scris de: Tulus Andrei din Aprilie 22, 2011, 10:05:40
in legatura cu problema 6 nu am inteles de unde il iau pe H si W pt ca in enunt mi se da doar N si M


Titlul: Răspuns: Probleme cu puncte laticiale
Scris de: Paul-Dan Baltescu din Aprilie 22, 2011, 12:16:43
Citat
Astfel, în O(H) vom şti numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni H * W. Acest dreptunghi poate fi pus în (N - H + 1) * (M - W + 1) locaţii pe o grilă de dimensiune N * M. Deci, soluţia are complexitate O(N*M^2), pentru fiecare dreptunghi de dimensiuni 1 ≤ H ≤ N şi 1 ≤ W ≤ M calculându-se numărul de dreptunghiuri înscrise.

Cum e precizat mai sus, ideea e sa alegi toate perechile (H,W) cu 1 <= H <= N si 1 <= W <= M, iar pentru fiecare pereche in parte sa calculezi in O(H) numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H si W, folosind indicatiile din primele paragrafe. Acest numar va trebui inmultit cu numarul de amplasari posibile ale unui astfel de dreptunghi (adica (N - H + 1) * (M - W + 1)).


Titlul: Răspuns: Probleme cu puncte laticiale
Scris de: Rares Cheseli din Mai 28, 2013, 21:38:10
La problema 7 cum pot folosi faptul ca  într-un dreptunghi de dimensiuni H * W poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un dreptunghi W * H?
am incercat sa fac asa dar nu da rezultat bun :
Cod:
for (int h=2; h<=max(m, n)+1; h++)
    {
        for (int w=2; w<=h; w++)
        {
            aux=(h-2)*(w-2) + h*w - gcd[h-1][w-1]-2;
            num+=(n-h+2)*(m-w+2)*aux;
        }
    }