Training Dummy

Avand o secure cu puterea $P$ si o papusa cu $X$ puncte de viata, avem nevoie de $\lceil\frac{X}{P}\rceil$ lovituri pentru a distruge papusa. Deci, numarul mediu de secunde este egal cu $\sum\limits_{i=A}^{B}P(\text{securea echipata are puterea i})\cdot\lceil\frac{X}{i}\rceil = \sum\limits_{i=A}^{B}\frac{1}{B-A+1}\cdot\lceil\frac{X}{i}\rceil = \frac{1}{B-A+1} \sum\limits_{i=A}^{B}\lceil\frac{X}{i}\rceil$ .
Solutia are complexitatea $O(T(B-A))$ .

Super Mario

Solutia 1

Definim o functie $f(st, dr)$ care returneaza numarul minim de mutari necesare pentru a distruge toate testoasele din intervalul $[st, dr]$ , folosind numai testoase din acest interval. Raspunsul va fi dat de $f(1, N)$ .
In continuare, incercam sa gasim raspunsul pentru intervalul $[st, dr]$ . Pe care testoasa o distrugem prima si in ce directie o impingem?
Fie $p$ pozitia testoasei din acest interval cu puterea maxima. Observam ca la prima mutare o vom alege tot timpul pe aceasta. Nu are rost sa incepem cu alta testoasa, deoarece avem sansa sa ne lovim de tesoasa $p$ si in acest caz era mai bine sa inversam ordinea mutarilor.
Deci, distrugem testoasa $p$ si incercam sa o impingem in ambele directii. Daca o impingem spre stanga, distrugem toate testoasele din intervalul $[st, p-1]$ . In acest caz avem nevoie de $1 + f(p+1, N)$ mutari. Similar, daca o impingem spre dreapta, avem nevoie de $1 + f(st, p-1)$ mutari. Deci, $f(st, dr) = min(1 + f(st, p-1), 1 + f(p+1, dr))$ . Cazul de baza este $st > dr$ .
Aceasta solutie are complexitatea $O(NlogN)$ , deoarece in cel mai rau caz vizitam $N$ intervale si pentru fiecare aflam maximul in $O(logN)$ . Maximul se poate afla cu arbori de intervale sau cu range minimum query.

infoarena informatica de performanta

Training Dummy

Super Mario

Hero's Call: Northrend!

Temple