h2. "Pudge":https://www.infoarena.ro/problema/pudge
Putem observa ca Pudge cu cat arunca hook-ul mai in stanga de pozitia lui, timpul in care hook-ul ajunge pe axa Ox creste, deci inamicii se vor deplasa mereu mai spre dreapta decat erau inainte. Astfel, observam ca un inamic fixat intra in raza hook-ului la un punct (X1, 0) in care Pudge poate arunca hook-ul si iese din raza hook-ului la un punct (X2, 0), X2 <= X1, deci doar in intervalul [X2 + 1, X1] acest inamic va fi in raza hook-ului. Daca Pudge se afla in punctul (X, Y) si arunca hook-ul in punctul (X0, 0), timpul hook-ului sa ajunga pe axa Ox este <tex> \sqrt{(X-X0) * (X-X0) + Y * Y} </tex>, iar singurul termen care variaza din aceasta formula este X0. Astfel, pentru fiecare inamic vom cauta binar punctul X0 in care acesta intra in raza hook-ului si punctul X0 in care acesta iese din raza hook-ului, si vom creea un vector de evenimente de tipul (X, tip): daca tip e 1 inseamna ca de la pozitia X un inamic intra in raza hook-ului, iar daca tip e -1 inseamna ca de la pozitia X un inamic iese din raza hook-ului. Parcurgem acest vector de evenimente si vom sti la fiecare pas cati inamici prinde Pudge daca arunca hook-ul in punctul respectiv prin adunarea variabilelor "tip" din vector, iar raspunsul este maximul acestor valori.

(Atentie la cautarea binara deoarece pot exista erori de precizie din cauza radicalului, acestea pot fi rezolvate prin izolarea radicalului si ridicarea la patrat a inegalitatii pentru a scapa de acesta, sau putem lua un epsilon foarte mic pentru a verifica egalitatile)

(Atentie la cautarea binara deoarece pot exista erori de precizie din cauza radicalului, acestea pot fi rezolvate prin izolarea radicalului si ridicarea la patrat a inegalitatii pentru a scapa de acesta, sau putem lua un epsilon foarte mic pentru a verifica egalitatile)
 
h2. "Tenerife":https://www.infoarena.ro/problema/tenerife
 
Problema ne da un graf orientat aciclic unde nodurile sunt cluburile si muchiile sunt strazile dintre cluburui si ne cere sa calculam numarul de lanturi de cost 1. Costul unui lant este dat de cel mai mare divizor comun dintre valorile muchiilor de pe lant si o valoare K. Vom calcula numarul de lanturi de cost mai mare strict ca 1, deoarece vom vedea ca e mai usor sa calculam aceasta valoare, iar numarul de lanturi de cost 1 va fi numarul de lanturi posibile minus numarul de lanturi de cost mai mare strict ca 1.
Vom face sortarea topologica a grafului si numarul de lanturi posibile il vom calcula cu ajutorul programarii dinamice:
Dp[nod] = numarul de lanturi care incep din nod cu minim 2 noduri
Iar recurenta va fi: Dp[nod] = Suma din (Dp[vec] + 1), unde vec este un vecin al lui nod
Numarul de lanturi posibile este egal cu Suma din Dp[nod], pentru orice nod.
Acum trebuie sa calculam numarul de lanturi cu costul mai mare strict ca 1. Putem observa ca orice lant are costul egal cu cel mai mare divizor dintre (K, alte numere) => costul unui lant este divizibil cu cel putin un factor prim al lui K.
Pentru fiecare factor prim P al lui K putem calcula numarul de lanturi care au costul divizibil cu P, astfel vom afla numarul de lanturi cu costul mai mare strict ca 1. Pentru a nu lua in considerare un lant de mai multe ori ne vom folosi de principiul includerii si excluderii pe factorii primi distincti ai lui K.
Pentru o submultime de factori primi distincti ai lui K: P1, P2, .. , Pi vom calcula numarul de lanturi care au costul divizibil cu P1 * P2 * .. * Pi. Pentru a calcula acest numar vom face aceeasi dinamica ca inainte, doar ca vom folosi doar muchiile care au valoarea divizibila cu P1 * P2 * .. * Pi, acest lucru ne asigura faptul ca orice lant va avea costul divizibil cu P1 * P2 * .. *Pi.
Vom adauga sau vom scadea acest numar de lanturi gasit pentru o submultime fixata in functie de paritatea numarului de elemente al submultimii.
Rezultatul va fi = Numarul de lanturi posibile - Numarul de lanturi cu costul mai mare strict ca 1.