|
Titlul: 037 Atac Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:37:05 Aici puteţi discuta despre problema Atac (http://infoarena.ro/problema/atac).
Titlul: 037 Atac Scris de: Tiberiu-Lucian Florea din Februarie 18, 2005, 21:59:12 ...
Titlul: Linux cu ghinion Scris de: Gogu Marian din Martie 10, 2005, 22:47:22 Pentru cei in pascal:
Cred ca am trimis de peste 10 ori sursa si de fiecare data lua 0 p. Si era ciudat, fiindca la mine mergea pe orice test ca si un brute force care lua 40 p. Pana la urma am setat un vector care era declarat array[1..max] sa fie array[0..max] si am luat 100. In windows merge, insa in linux face figuri, asa ca aveti grija la oni, daca lucrati in free pascal de windows sa nu aveti neplaceri dupa Titlul: 037 Atac Scris de: Filip Cristian Buruiana din Iunie 26, 2005, 15:48:57 Si eu am luat 0 la asta(WA la toate).. sunt de abia la prima postare si am cam postat-o pe NV (am dat doar testul din exemplu si inca un test al meu tricky... ). Pentru doua noduri aflam LCA in logN, si apoi pt. fiecare din cele 2 lanturi (de la X la LCA si de la Y la LCA) aflam tot in logN care este minimul pe lantul respectiv cu un algoritm gen cel de la "stramosi", cu intoarcere la descendenti cu puteri de 2. Deci in total pe query imi dadea in final logN ( cu o constanta maricica, e adevarat ).
Pe langa WA, la testul 10 imi da TLE! Exista si un algoritm mai simplu pt. problema asta? Titlul: 037 Atac Scris de: Silviu-Ionut Ganceanu din Iunie 26, 2005, 23:06:54 Solutia mea e cea descrisa de tine. Acum s-ar putea sa fie diferente la implementare (de exemplu poti face LCA in O(1), etc). Stiu ca am pus limita relativ larga (cred ca sursa mea merge in jumatate din timp) deci, in mod normal, nu ar trebui sa fie probleme cu o sursa relativ ingrijit implementata.
Incearca sa o faci sa mearga si apoi mai bagi mici optimizari. Spor! Silviu Titlul: 037 Atac Scris de: Filip Cristian Buruiana din Iulie 22, 2005, 13:32:13 Am o nelamurire la problema asta: noi trebuie sa afisam "numarul minim pentru... ultimele P perechi ". Primul numar afisat va fi cel pt. cea de a (M-P+1)-a pereche sau pentru cea de a M-a pereche?
Adica rasp. pt. perechi se afiseaza in ordinea: (M-P+1), (M-P+2).. M, sau in ordinea M, M-1... (M-P+1) ( incepand cu ultima pereche)? bubbleSORT Titlul: 037 Atac Scris de: sorin fagateanu din Noiembrie 20, 2005, 17:21:41 poate ca sunt eu batut in cap...dar ](*,) exemplu din felu in care am inteles eu problema nu e corect:-/
x=6;y=7;a,b,c,d=1 7-5-1-2-3 ...|.....| ...6....4 drum intr 6..7 cica e 6..5+5..7=2+3 nuh? x:=(6+7)mod 7 +1=7 nuh? y:=(7+5)mod 7 +1=6 nuh? drum intre 7..6 acelsi x:=(7+6)mod 7+1=7 nuh? y:=(6+5)mod 7+1=5 nuh? =>tre scris 5 drum intre7..5=2 =>tre scris 2 deci unde nu am inteles bine?:-s Titlul: 037 Atac Scris de: VladS din Noiembrie 20, 2005, 18:12:57 Pentru a izola nodurile 7 si 6 costul este 2( blochezi muchia dintre 5 si 7), nu 5.
Titlul: 037 Atac Scris de: sorin fagateanu din Noiembrie 20, 2005, 18:37:43 ah..deci cum ar veni muchia minima de pe drumu ala? hmm ...:( tre sa rescriu sursa :cry: :(
Titlul: 037 Atac Scris de: Sara Nicolae Bogdan din Februarie 26, 2006, 12:10:10 Cum pot sa calculez muchia de cost minim de pe un lant in timp logaritmic ? Need some help pls !! :oops:
Titlul: 037 Atac Scris de: u-92 din Februarie 26, 2006, 12:15:30 folosind ideea de la stramosi, de altfel este si un post mai sus in care este mentionata chestia asta
Titlul: Raspuns: 037 Atac Scris de: Sachelarie Bogdan Lucian din Noiembrie 12, 2006, 18:05:09 Imi da si mie cineva un test mai smecher.Habar n-am de ce nu iese.
Titlul: Răspuns: 037 Atac Scris de: Onicas Mircea din Martie 25, 2010, 16:21:07 Se poate raspunde cumva in O(1)? :ok:
Titlul: Răspuns: 037 Atac Scris de: theprdv din Iunie 27, 2015, 09:49:42 ori este gresit enuntul ori gresesc eu : in testul din enunt trebuia ca pe linia 5 V-ul sa fie 1 (costul de la 1 la 5 sa fie 1) ca sa dea acele rezultate
|