|
Titlul: 135 Dreptunghiuri Scris de: ditzone din Noiembrie 19, 2005, 16:07:52 Aici puteţi discuta despre problema Dreptunghiuri (http://infoarena.ro/problema/dreptunghiuri).
Titlul: 135 Dreptunghiuri Scris de: Alb Gabriel din Noiembrie 27, 2005, 11:13:46 Imi puteti spune va rog cat da pt m = 8 si n = 4?
Titlul: 135 Dreptunghiuri Scris de: ditzone din Noiembrie 27, 2005, 11:26:26 200
Titlul: 135 Dreptunghiuri Scris de: Deac Andrei din Februarie 03, 2006, 20:50:42 pt 100 100 ce se obtine?
Titlul: Răspuns: 135 Dreptunghiuri Scris de: Mihai Leonte din Aprilie 06, 2007, 21:17:00 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. Titlul: Răspuns: 135 Dreptunghiuri Scris de: Florian Marcu din Aprilie 30, 2009, 16:06:14 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:
Citat 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! :) Titlul: Răspuns: 135 Dreptunghiuri Scris de: Moise Razvan din Martie 26, 2010, 20:02:38 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 :readthis: ce am omis? :angry: Titlul: Răspuns: 135 Dreptunghiuri Scris de: Oncescu Costin din Noiembrie 28, 2013, 22:16:16 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 .:)
|