•gozzy
Strain
Karma: 0
Deconectat
Mesaje: 1
|
![](/forum/Themes/default/images/post/xx.gif) |
« : Decembrie 16, 2007, 01:16:52 » |
|
Imi poate acorda si mie cineva o indicatie amcar la cum se rezolva problema asta?
Fie N un număr natural şi un şir de 2N numere naturale X1, X2, …, X2N.
Cerinţa Trebuie să răspundeţi la un număr de Q întrebări de forma : Date k şi p, care este elementul maxim dintre elementele Xk, Xk+1, …, Xp din şir?
Date de intrare: Pe prima linie a fişierului maxim.in se află N, pe următoarea linie 2N numere separate prin câte un spaţiu reprezentând elementele şirului. Pe linia a treia se află Q, numărul de întrebări, iar pe următoarele Q linii sunt câte două numere k şi p separate printr-un spaţiu reprezentând capetele secvenţei din care trebuie să aflaţi maximul.
Date de ieşire Fişierul maxim.out conţine exact Q linii. Pe fiecare linie se află un singur număr S, reprezentând răspunsul la fiecare întrebare din fişierul de intrare.
Restricţii şi precizări • 2 N 13 • Xi este un număr între 1 şi 30.000, pentru orice i, 1 i 2N • 1 k p 2N • 1 Q 100.000
Exemplu: maxim.in 2 4 6 7 1 3 1 4 1 2 2 4 maxim.out 7 6 7 Explicaţie: Dintre elementele de la poziţia 1 la 4, maximul este 7. Dintre elementele de la poziţia 1 la 2, maximul este 6. Dintre elementele de la poziţia 2 la 4, maximul este 7.
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #2 : Decembrie 16, 2007, 08:39:29 » |
|
Concursul era din 2006 ![Smile](http://www.infoarena.ro/forum/Smileys/default/smile.gif) , scrie sus la inceput.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•pauldb
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #3 : Decembrie 16, 2007, 08:45:42 » |
|
Merge mai usor cu o preprocesare in O(N^2) sau O(N^3) si apoi O(1) pe query. Calculezi direct A[i,j] = maximul pe intervalul i,j si raspunzi la query-uri. ![Smile](http://www.infoarena.ro/forum/Smileys/default/smile.gif)
|
|
|
Memorat
|
Am zis ![Mr. Green](http://www.infoarena.ro/forum/Smileys/default/mrgreen.gif)
|
|
|
•wefgef
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #4 : Decembrie 16, 2007, 08:56:12 » |
|
Sunt 2^N numere, nu 2*N.
|
|
« Ultima modificare: Decembrie 16, 2007, 08:58:24 de către Andrei Grigorean »
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Florian
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #5 : Decembrie 16, 2007, 08:58:07 » |
|
Si daca, de exemplu pt fiecare pereche [i,j] din datele de intrare, numerele din intervalul determinat de ele si-ar modifica valoarea..intr-un mod random, sa zicem. Tot asa cu precalculare in N^3 se face? ![Confused](http://www.infoarena.ro/forum/Smileys/default/unsure.gif)
|
|
|
Memorat
|
|
|
|
•wefgef
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #6 : Decembrie 16, 2007, 08:58:48 » |
|
Se face cu arbori de intervale.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Cosmin
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #7 : Decembrie 16, 2007, 09:09:48 » |
|
@wefgef se mai refolosesc probleme, nu ziceam ca concursul din 2006 ar fi unul curent
|
|
|
Memorat
|
|
|
|
|