infoarena

Aici puteţi discuta despre problema Patrate (http://infoarena.ro/problema/patrate).

Mi-au furat australienii problema :( http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3282

:-k Interesant... Si testul dat pe site e cam acelasi.... Hmm... Cred ca intr-un fel ai putea sa fii mandru. Oricum... Interesanta faza... 8)

Hmm, si eu m-as supara sa vad ca imi fura unu problema, dar daca nu era speciala nu o copiau ;)

Nu cred ca exista drepturi de autor la probleme, nu ? Si chiar daca ar exista, ar trebui s-o inregistrezi undeva.  :lol:

Imi poate da si mie cineva o solutie ?:) sau macar sa-mi spuneti cand s-a dat aceasta problema pentru ca eu de exemplu m-am uitat in arhiva de lot 2005 sibiu si nu e :(

Problema mea e urmatoarea: m-am gandit sa caut binar lungimea aceea minima, sa zicem ca e L, si apoi incerc sa acopar punctele toate cu 3 patrate de lungime L. Ei, ultima parte ar iesi catastrofal din timp :)

E buna ideea ta cu cautarea binara. Trebuie sa vezi cum acoperi un set de puncte cu 3 patrate de lungime data. Te uiti la cel mai mic dreptunghi care contine punctele tale. Fiecare din cele 4 laturi ale dreptunghiului contine cel putin un punct. Intr-o solutie in care reusesti sa acoperi toate punctele cu 3 patrate, vei avea pe fiecare latura cel putin un patrat. Cum sunt 4 laturi iar tu ai 3 patrate => cel putin un patrat va fi in coltul dreptunghiului. Iti variezi coltul, si problema s-a redus la 2 patrate :). De aici cred ca te descurci si singur ;)

Imi puteti sugera si mie va rog ce as fi putut gresi? Iau 96 pct, cu Incorect chiar pe primul test.  :-s

Iti merge pentru N = 3?

Gata, am descoperit! Pentru n<=3 eu afisam 1. Dar se pare ca putem considera latura si de lungime 0.  :D Multumesc de idee!  :)

Poate cineva sa-mi dea un n si o combinatie de coordonate ca sa-mi testez programul(de preferat mari) si raspunsul? nu de alta dar nu prea am imaginatie in momentul acesta...