Cal
Se verifică pentru fiecare punct dacă distanta manhattan fata de (sx,sy) e egală cu S si se creşte un contor.
Distanţa manhattan pentru 2 puncte A(a,b) B(x,y) se calculează cu formula: |a-x|+|b-y|
ScaleCrop
Pentru ca poza se scaleaza, avem ca wpn=f*wp si hpn=f*hp. Ramane doar sa gasim cel mai mic factor f cu care trebuie sa inmultim dimensiunile pozei, pentru a obtine wpn >= wf si hpn >= hf. Acest factor il putem gasi in timp logaritmic folosind cautarea binara sau in timp constant, alegand f dintre wf/wp si hf/hp in asa fel incat sa nu ramana nicio bucata din flyer neacoperita de poza.
ProDiv
Solutie O(sqrtN)
Se decompune N în factori primi. Fiecare factor il "distribuim" între cele 2 numere egal. De exemplu pentru 24 il inmultim pe a si pe b cu 22.
Notăm nrm = numărul de factori primi care au exponentul impar. Solutia este 2nrm
Arbore5
Solutie O(N)
Pentru fiecare nod reţinem nr[nod]=câte query-uri au unul din capete in nod sau în subarborele lui nod. Solutia este numărul de noduri diferite de rădăcină(nu are o muchie care să-l lege de un tată) care au nr[nod] par.
