Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-04-24 19:05:05.
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")== Pentru usurinta, notam cu (x,y) dimensiunile flyerului si cu (m,n) dimensiunile imaginii(pozei). In limbaj geometric, trebuie sa gasim cel mai mic raport de omotetie ce transforma poza originala in o poza ce acopera complet flyerul.Daca acest raport este k, solutia va fi k*(m,n). Acest k este egal cu maximul dintre y/n si x/m. ==include(page="monthly-2012/runda-4/solutii/prodiv")"

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.