infoarena

Aici puteţi discuta despre problema Paralelograme (http://infoarena.ro/problema/paralelograme).

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?

inca nu am facut problema, dar esti sigur ca nu ai numarat paralelogramele degenerate?

is sigur :D
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?  :-k

Nu m-am uitat pe metoda ta, dar pentru 3 2 trebuie sa dea 60.

Ai gresit la s(i, j)... Ia un exemplu mai mare pe foaie si vezi cum il poti calcula mai bine :)

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 :)

Foloseste teorema lui Pick.... Google it :)

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 ;)

Da.. eh.. eu m-am comlicat putin atunci :)

Da.. de fapt, ori cu teorema lui Pick, ori fara, ajungi la acelasi rezultat :)

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.

Cred ca Cosmin se refera la articolul acesta (http://infoarena.ro/probleme-cu-puncte-laticiale).

Multumesc! Chiar mi-a fost de ajutor.