monthly-2014/runda-8/solutii

Infoarena Monthly 2014 - Runda 8, Solutii

Avand o secure cu puterea <tex>P</tex> si o papusa cu <tex>X</tex> puncte de viata, avem nevoie de <tex>\lceil\frac{X}{P}\rceil</tex> lovituri pentru a distruge papusa. Deci, numarul mediu de secunde este egal cu <tex>\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</tex>.
Solutia are complexitatea <tex>O(T(B-A))</tex>.

Aceasta solutie se poate imbunatati cu observatia ca exista <tex>O(\sqrt{B-A})</tex> valori distincte pentru <tex>\lceil\frac{X}{i}\rceil</tex>. Le putem parcurge doar pe acestea si stim de cate ori apare fiecare in suma. Complexitatea devine <tex>O(T\sqrt{B-A})</tex>. Nu era nevoie de aceasta optimizare pentru a ne incadra in timp.
 

h1. 'Super Mario':problema/supermario
*Solutia 1*