|
Titlul: 038 Tribute Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:37:28 Aici puteţi discuta despre problema Tribute (http://infoarena.ro/problema/tribute).
Titlul: 038 Tribute Scris de: Tiberiu-Lucian Florea din Februarie 13, 2005, 15:20:33 Ce complexitati ati scos la pb. asta?
Btw, misto problema. :D Titlul: 038 Tribute Scris de: Cosmin Negruseri din Februarie 14, 2005, 03:54:59 O(n) sau O(n log n) fara radix sort.
Titlul: 038 Tribute Scris de: Tiberiu-Lucian Florea din Februarie 14, 2005, 06:40:33 Eu O(nr de coordonate).
Titlul: 038 Tribute Scris de: Chris din Februarie 17, 2005, 13:57:16 Eu am rezolvat cu O(N+MAX_C) (vreo 4 baleieri) dar imi da wrong answer la ultimul test! (weird!) :cry:
Titlul: 038 Tribute Scris de: Silviu-Ionut Ganceanu din Februarie 18, 2005, 15:07:48 Citat Eu am rezolvat cu O(N+MAX_C) (vreo 4 baleieri) dar imi da wrong answer la ultimul test! (weird!) Probabil te-ai complicat inutil. E nevoie doar de doua baleieri din cate mi-aduc aminte. Citat Btw, misto problema. Mersi :) Este evident ca dupa sortare problema se rezolva in O(N). Sortarea se poate face O(NlogN) sau O(MAX_VALUE). Ambele garanteaza punctajul maxim. Silviu Titlul: 038 Tribute Scris de: Tiberiu-Lucian Florea din Februarie 18, 2005, 15:20:38 Ce N log N? sortare in timp liniar :) Cred ca rezolvarea mea la aceasta problema nu a folosit absolut nimic in afara de niste parcurgeri de vectori. :D
Titlul: 038 Tribute Scris de: Constantin Cristian din Martie 20, 2005, 23:15:57 Am implementat un algoritm dar nu am reusit sa iau decat 10 puncte.
In principiu, am cautat sa aflu unde ar trebui sa fie asezat terenul pe orizontala si pe verticala. Prima data am sortat abscisele punctelor. Am luat o dreapta in punctul cu abscisa cea mai mica si unul in capatul celalat si m-am apropiat cu dreptele una de cealalta pana distanta dintre ele este DX. La fel am procedat si pentru verticala. Dupa care, avand coordonatele terenului, calculez distanta pana la fiecare punct din exteriorul sau. Unde am gresit? Voi cum ati rezolvat problema? Va multumesc!!! Titlul: Răspuns: 038 Tribute Scris de: Pop Paul din Martie 09, 2007, 10:58:23 daca nu ti-a raspuns nimeni de 2 ani nu cred ca eu am ceva sanse sa-mi raspunda cineva astazi :)
Titlul: Răspuns: 038 Tribute Scris de: Marius Stroe din Martie 09, 2007, 16:52:59 Vroiam sa iti raspund maine. :)
Daca pastrezi coordonatele punctelor in doi vectori X[], Y[], atunci nu iti ramane decat sa vezi unde poti pune terenul pe orizontala, cu ajutorul lui X[], respectiv pe verticala, cu ajutorul lui Y[], astfel incat sa minimizezi raspunsul final. Titlul: Răspuns: 038 Tribute Scris de: Pop Paul din Martie 09, 2007, 17:38:19 mersi
fac un hamburger la cluj daca trec de oji :) |