•greco
|
|
« : Aprilie 02, 2006, 01:39:37 » |
|
Aici puteţi discuta despre problema Paralelograme.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•amadaeus
Client obisnuit
Karma: 28
Deconectat
Mesaje: 93
|
|
« Răspunde #1 : Aprilie 02, 2006, 17:32:19 » |
|
am gasit o metoda de rezolvare care mi se pare corecta (am verificat "manual" pentru (1,1), (1,2), (2,2)); totusi, iau WA pe toate testele; pentru n=3 m=2, am gasit 58 de paralelograme; asta e raspunsul corect?
|
|
|
Memorat
|
"one of these days I'm going to cut you into little pieces..."
|
|
|
•wefgef
|
|
« Răspunde #2 : Aprilie 02, 2006, 17:36:13 » |
|
inca nu am facut problema, dar esti sigur ca nu ai numarat paralelogramele degenerate?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•amadaeus
Client obisnuit
Karma: 28
Deconectat
Mesaje: 93
|
|
« Răspunde #3 : Aprilie 02, 2006, 17:43:02 » |
|
is sigur uite cum fac: notez cu s(i,j) numarul paralelogramelor care se incadreaza perfect intr-un dreptunghi de i x j (inclusiv dreptunghiul insusi). Astfel gasesc ca s(i,j) = ij + (i-1) + (j-1) Apoi notez cu f(i,j) numarul locurilor in care pot translata paralelogramele care se incadreaza perfect in i x j; obtin f(i,j) = (n-i+1)*(m-j+1); Solutia problemei devine Suma (1<=i<=n; 1<=j<=m) din ( s(i,j) * f(i,j) ) Asta verifica pentru (1,1), (1,2), (2,1), (2,2); pentru (3,2) da 58... wtf is wrong?
|
|
|
Memorat
|
"one of these days I'm going to cut you into little pieces..."
|
|
|
•domino
|
|
« Răspunde #4 : Aprilie 02, 2006, 17:45:47 » |
|
Nu m-am uitat pe metoda ta, dar pentru 3 2 trebuie sa dea 60.
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #5 : Aprilie 02, 2006, 18:54:55 » |
|
is sigur uite cum fac: notez cu s(i,j) numarul paralelogramelor care se incadreaza perfect intr-un dreptunghi de i x j (inclusiv dreptunghiul insusi). Astfel gasesc ca s(i,j) = ij + (i-1) + (j-1) Apoi notez cu f(i,j) numarul locurilor in care pot translata paralelogramele care se incadreaza perfect in i x j; obtin f(i,j) = (n-i+1)*(m-j+1); Solutia problemei devine Suma (1<=i<=n; 1<=j<=m) din ( s(i,j) * f(i,j) ) Asta verifica pentru (1,1), (1,2), (2,1), (2,2); pentru (3,2) da 58... wtf is wrong? Ai gresit la s(i, j)... Ia un exemplu mai mare pe foaie si vezi cum il poti calcula mai bine
|
|
|
Memorat
|
|
|
|
•amadaeus
Client obisnuit
Karma: 28
Deconectat
Mesaje: 93
|
|
« Răspunde #6 : Aprilie 02, 2006, 18:55:35 » |
|
am gasit.. greseala era la formula pentru s(i,j). o intrebare: daca am un dreptunghi de m x n puncte laticeale, cate puncte se afla "sub" diagonala principala? [later edit] tocmai imi dadusem si eu seama - am facut brute-force si am vazut ca pierdeam cateva din vedere. ms mult oricum, bogdan
|
|
« Ultima modificare: Aprilie 02, 2006, 18:58:54 de către amadaeus »
|
Memorat
|
"one of these days I'm going to cut you into little pieces..."
|
|
|
•bogdan2412
|
|
« Răspunde #7 : Aprilie 02, 2006, 19:00:04 » |
|
Foloseste teorema lui Pick.... Google it
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #8 : Aprilie 02, 2006, 19:33:32 » |
|
Nu cred ca trebuie teorema lui Pick aici ... poti sa vezi cate puncte sunt pe diagonala sa le scazi din n * m cate sunt in intreg dreptunghiul si dupaia sa imparti la 2 ... E un articol in ginfo care se ocupa cu probleme de genul asta
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #9 : Aprilie 02, 2006, 20:53:22 » |
|
Da.. eh.. eu m-am comlicat putin atunci
|
|
|
Memorat
|
|
|
|
•amadaeus
Client obisnuit
Karma: 28
Deconectat
Mesaje: 93
|
|
« Răspunde #10 : Aprilie 02, 2006, 21:07:54 » |
|
Da.. de fapt, ori cu teorema lui Pick, ori fara, ajungi la acelasi rezultat
|
|
|
Memorat
|
"one of these days I'm going to cut you into little pieces..."
|
|
|
•APOCALYPTO
|
|
« Răspunde #11 : Iulie 23, 2010, 21:51:56 » |
|
E un articol in ginfo care se ocupa cu probleme de genul asta Imi poti spune si mie rubica(Focus, Babel),anul sau autorul. M-am uitat peste titlurile de pe site si unde mi s-a parut ca ar putea fi vorba despre articolul respectiv am deschis si pdf-ul ca sa verific dar din pacate nu am reusit sa-l gasesc.
|
|
« Ultima modificare: Iulie 24, 2010, 13:37:38 de către Dragos »
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #12 : Iulie 24, 2010, 02:46:13 » |
|
Cred ca Cosmin se refera la articolul acesta.
|
|
|
Memorat
|
Am zis
|
|
|
•APOCALYPTO
|
|
« Răspunde #13 : Iulie 31, 2010, 12:46:16 » |
|
Cred ca Cosmin se refera la articolul acesta. Multumesc! Chiar mi-a fost de ajutor.
|
|
|
Memorat
|
|
|
|
|