cautare

Ştim cu toţii ce este un arbore binar de căutare. Este acel arbore binar în care informaţia din orice nod este mai mare decât informaţiile nodurilor din subarborele stâng al nodului respectiv şi mai mică decât cele din subarborele drept.

Când se caută o informaţie într-un arbore binar de căutare, începem din rădăcina arborelui şi comparăm cu informaţia din rădăcină. Dacă informaţia căutată e mai mică decât informaţia din rădăcină, se continuă căutarea în subarborele stâng, iar dacă e mai mare în subarborele drept. Dacă cele două informaţii sunt egale căutarea se termină cu succes. Dacă în direcţia în care continuăm căutarea (stânga sau dreapta) subarborele nu mai are noduri înseamnă că informaţia căutată nu se găseşte în arbore. Evident, numărul de comparaţii efectuate la o căutare depinde de distanţa dintre rădăcină şi nodul în care se găseşte informaţia, respectiv cel la care putem decide că informaţia nu se află în arbore.

Ce s-ar întâmpla dacă înainte de a construi arborele binar de căutare am şti ce informaţii urmează să fie căutate în el? Nu cumva am putea construi arborele în aşa fel încât să minimizăm numărul de comparaţii efectuate?
De exemplu cu informaţiile 1, 2 şi 3 putem construi un arbore binar de căutare în următoarele 3 moduri (din totalul de 5 posibile):

Dacă vom căuta informaţiile (1, 1, 3, 1, 2), atunci timpul total de căutare este pentru arborele din stânga 1+1+3+1+2 = 8, pentru arborele din centru 2+2+2+2+1 = 9, iar pentru arborele din dreapta 3+3+1+3+2 = 12

Deci arborele din stânga este cel adecvat pentru căutările noastre, iar timpul total de căutare minim este 8.

De remarcat că dacă se caută o informaţie care nu există în arbore atunci numărul de comparaţii efectuate la căutare este egal cu nivelul ultimului nod interogat. De exemplu, dacă se caută informaţia 4 pe cei trei arbori atunci timpii vor fi: 3, 2, respectiv 1 (de la stânga la dreapta).

Cerinţă

Scrieţi un program care, pentru anumite informaţii căutate, determină timpul total de căutare minim.

Date de intrare

Din fişierul cautare.in se citeşte de pe prima linie numărul T de teste. În fişier urmează cele T teste. Pentru fiecare test în fişier sunt scrise următoarele linii:

• prima linie conţine N, numărul de noduri ale arborelui de căutare şi M numărul de interogări, separate prin spaţiu;
• pe următoarea linie urmează N numere întregi distincte, separate prin câte un spaţiu, reprezentând informaţiile din nodurile arborelui
• pe fiecare dintre următoarele M linii sunt câte 2 numere întregi separate printr-un spaţiu, reprezentând un număr căutat şi respectiv de câte ori a fost căutat (între 1 şi 100).

Date de ieşire

În fişierul cautare.out se va scrie, pentru fiecare test câte o linie care conţine timpul total minim de căutare pentru interogările din testul respectiv.

Restricţii și precizări

• 0 < T, N < 101, 0 < M < 1001
• Informaţiile nodurilor arborelui sunt numere întregi din intervalul [-10000, 10000]
• Informaţiile căutate sunt numere întregi din intervalul [-1000000, 1000000] şi pot fi căutate de un număr de ori cuprins între 1 şi 100.
• Pentru 50 de puncte T<4.

Exemplu

cautare.in

3
3 3
1 2 3
1 3
2 1
3 1
3 3
1 2 3
1 50
2 49
3 51
3 2
1 2 3
2 1
4 20

cautare.out

8
251
22

Explicaţii

Primul test este cel discutat. În al doilea test se interoghează 1 de 50 de ori, 2 de 49 de ori si 3 de 51 de ori. Cel mai bun rezultat se obţine în cazul arborelui din centru, şi anume 251 (2*50+49+2*51). Al treilea test conţine o interogare a lui 4 (care nu se află în arbore) de multe ori (20). Evident că cel mai bun e arborele din dreapta, pe care ne dăm seama repede că 4 nu se află în arbore. Timpul total este (1*20+2).