|
Titlul: Problema Scris de: Grosu Andrei Nicolae din 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. Titlul: Răspuns: Problema Scris de: Cosmin Negruseri din Decembrie 16, 2007, 02:20:37 Sper ca nu e de la ceva concurs de acuma, eu am gasit-o aici http://lsp.vs.edu.ro/pracsiu/Centrul%20de%20excelenta/subiecte%20OLI/OLI%202006%20Subiecte%209-12.htm
Cauta range minimum query pe google, poti de asemenea citi de RMQ in articolul lui Daniel Pasaila de aici: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor . Pe scurt folosesti matricea a[j] = max (X ... X[i + 2^j - 1]) (i de la 1 la 2^n, j de la 0 la n) pentru a raspunde in O(1) la un query. Titlul: Răspuns: Problema Scris de: Andrei Grigorean din Decembrie 16, 2007, 08:39:29 Concursul era din 2006 :), scrie sus la inceput.
Titlul: Răspuns: Problema Scris de: Paul-Dan Baltescu din 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. :)
Titlul: Răspuns: Problema Scris de: Andrei Grigorean din Decembrie 16, 2007, 08:56:12 Sunt 2^N numere, nu 2*N.
Titlul: Răspuns: Problema Scris de: Florian Marcu din 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? :?
Titlul: Răspuns: Problema Scris de: Andrei Grigorean din Decembrie 16, 2007, 08:58:48 Se face cu arbori de intervale.
Titlul: Răspuns: Problema Scris de: Cosmin Negruseri din Decembrie 16, 2007, 09:09:48 @wefgef se mai refolosesc probleme, nu ziceam ca concursul din 2006 ar fi unul curent
|