h3(#problema-1). Problema 1: 'Drilling':http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en

bq. Se da un şir de $N$ numere naturale $(a{~1~}, a{~2~}, ..., a{~N~})$. Se ştie că un prefix al acestui şir (adică o subsecvenţă de la începutul şirului, posibil nulă) este prost. Toate elementele din acel prefix (şi doar din acel prefix) sunt proaste. Se ştie de asemenea că se poate testa orice poziţie $i$ în timp $a{~i~}$ pentru a afla dacă este proastă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este prost.

bq. Se da un şir de $N$ numere naturale $(a{~1~}, a{~2~}, ..., a{~N~})$. Se ştie că un prefix al acestui şir (adică o subsecvenţă de la începutul şirului, posibil nulă) este **defect**. Toate elementele din acel prefix (şi doar din acel prefix) sunt defecte. Se ştie de asemenea că se poate testa orice poziţie $i$ în timp $a{~i~}$ pentru a afla dacă este defectă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este defect.

h3. Exemplu:

Pentru secvenţa de numere $(8 24 12 6)$, răspunsul ar fi $42$. Astfel, se testează mai întâi poziţia $2$. Dacă nu este proastă, mai rămâne de testat poziţia $1$. Altfel, în cel mai rău caz mai trebuie testate poziţiile $3$ şi $4$, aducând timpul total la $24 + 12 + 6 = 42$.

Pentru secvenţa de numere $(8 24 12 6)$, răspunsul ar fi $42$. Astfel, se testează mai întâi poziţia $2$. Dacă nu este defectă, mai rămâne de testat poziţia $1$. Altfel, în cel mai rău caz mai trebuie testate poziţiile $3$ şi $4$, aducând timpul total la $24 + 12 + 6 = 42$.

h3. Rezolvare:
O să începem prin a da altă îmbrăcăminte problemei. Astfel, să ne imaginăm că am construi un arbore binar de căutare pe şirul dat, având drept chei poziţiile din şir, şi drept valori auxiliare valorile poziţiilor respective din şir (un nod cu cheia $i$ va avea valoarea auxiliara $a{~i~}$.

Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul, pe care îl considerăm de acum ca fixat. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este proastă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.

Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul, pe care îl considerăm de acum ca fixat. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este defectă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.

Să observăm că dacă considerăm costul unui drum în arbore de la rădăcină la o frunză ca suma valorilor auxiliare din drumul (unic) respectiv, atunci se observă că costul strategiei bazate pe acest arbore este chiar costul maxim al unui drum ! De acum încolo, vom defini costul unui arbore ca costul maxim al unui drum din el. Să exemplificăm pe şirul din exemplu: