Problema saptamanii - Minim local

Cosmin Negruseri
12 septembrie 2010

Saptamana aceasta avem o problema ce vroiam sa o folosim ca problema simpla in una din zile la Olimpiada Europei Centrale de Informatica (CEOI 2009). Ea era s-a dovedit a fi destul de cunoscuta fiind deja folosita in alte doua concursuri la care participasera unii dintre concurenti.

Se da o matrice A de 1000×1000 de numere intregi distincte. Putem pune intrebari de tipul "care este valoarea elementului A[x][y]". Dati un algoritm ce gaseste un minim local in aceasta matrice folosind cel mult 3100 de intrebari. Un element este minim local daca este mai mic decat cele patru elemente vecine ortogonal in matrice.

Puteti trimite solutii la adresa cosminn at gmail.com