Problema saptamanii - Minim local

Cosmin Negruseri
12 septembrie 2010

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

Se da o matrice A de 1000×1000 de numere intregi distincte. Putem pune intrebari de genul care este valoarea elementului A[x][y]. Se cere sa se dea un algoritm ce gaseste un minim local in aceasta matrice in 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