068 Patrate

[•domino]

Aici puteţi discuta despre problema Patrate.

[•Cosmin]

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

[•calinux]

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

[•dobre]

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

[•greco]

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

[•cip]

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

[•wefgef]

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

[•otilia_s]

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

[•wefgef]

Iti merge pentru N = 3?

[•otilia_s]

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

[•Iulian94]

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...