Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-04-24 18:57:06.
Revizia anterioară   Revizia următoare  
Bad macro "include(page="monthly-2012/runda-4/solutii/cal")== Fie x si y coordonatele initiale ale calului. Citim pe parcurs in (a,b) coordonatele fantanelor si verificam daca |x-a|+|y-b|=s, caz in care marim un contor cnt. Solutia este chiar cnt. ==include(page="monthly-2012/runda-4/solutii/scalecrop")"

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.