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 (posibil chiar prefixul nul) este prost. Se ştie de asemenea că se poate testa orice poziţie $i$ în timp $a{~i~}$ 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 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.

h3. Exemplu: