135 Dreptunghiuri

[ditzone]

Aici puteţi discuta despre problema Dreptunghiuri.

[•Gabi]

Imi puteti spune va rog cat da pt m = 8 si n = 4?

[ditzone]

200

[•Stilgar]

pt 100 100 ce se obtine?

[•MarcvsHdr]

E super simpla problema asta si totusi ceva am gresit. Mie imi da 190 pt m=8 si n=4, si nu ma prind unde am gresit  .
Pentru exemplul asta mi-au dat:
- 168 dreptunghiuri cu laturile paralele cu marginile grilajului
- 12 dreptunghiuri de laturi sqrt(2) si sqrt(2)
- 10 dreptunghiuri de laturi sqrt(2) si 2*sqrt(2) (5 orientate oblic "in sus", si 5 orientate oblic "in jos", ca sa ma exprim babeste).

Imi spune si mie cineva, pls, ce am uitat sa numar?

Never mind, m-am prins.

[•Florian]

Am folosit ideea din articolul cu solutii. Cu toate astea, pe testul 8 4 imi da 194, in loc de 200. Ma chiunui de doua zile sa imi dau seama ce are, si nu reusesc sa gasesc greseala. Pseudocodul ( pt W si H fixate) arata cam asa:

s_partiala = 1; // nr de dreptunghiuri inscrise in dreptunghiul de laturi W si H.
pentru ( A = 2; A < H; ++A ) // A nu poate fi in coltul dreptunghiului
{
   - calculez solutiile ecuatiei C^2 - W*C + A * (H - A). (necunoscuta C)
   - daca delta < 0 sau delta nu e patrat perfect continue;
   - daca C1 (sau C2)  este numar intreg si e cuprins in intervalul [ 2 , W-1 ] s_partiala ++;
}
sol_totala += (N - H + 1) * (M - W + 1) * sp;

2<=W<=M si 2<=H<=N. Plec cu ele de la 2, pentru ca laturile din care poate fi format un dreptunghi paralel cu axele trebuie sa contina cel putin 2 puncte.
A imi pleaca de la 2, la H-1, intrucat nu iau in considerare dreptunghiul de laturi (H,W), ( caz luat in considerare atunci cand s_partiala = 1 ). Iar solutia pentru C trebuie sa apartina lui [ 2, W-1 ], intrucat C nu poate fi colt al dreptunghiului (H,W). Prin lungimea unei laturi inteleg numarul de puncte laticiale de pe ea. Sper ca am explicat destul de bine ceea ce fac. Ma poate lumina cineva? Multumesc! 

[•Bunicool]

Bun, deci am luat in calcul :
-patratele si dreptunghiurile cu laturi paralele cu axele ox si oy
-patratele si dreptunghiurile neparelele cu axele, a caror laturi fie sunt amandoua sqrt2, fie cel putin doua din ele contin mai mult de doua puncte din caroiaj
-patratele neparalele cu axele cu laturi mai mari de sqrt2 si care contin doar doua puncte din caroiaj (varfurile)

merge garantat pentru 8 4 ca sa dea 200, iar la 100 100 da 40501196

concluzie: 0 puncte  
ce am omis?  

[•geniucos]

Ar putea fi micsorata limita de timp.Exista solutii de N^2*constanta de cmmdc si solutii de N^2.S-ar putea pune o limita de 0.05 s .