h1. Solutii preONI 2006 - Runda 1

(Categoria _Competitii_, autor(i) _Echipa infoarena_)

(Categoria _Competitii_, autor(i) _Echipa info-arena_)

Runda 1 a concursului preONI 2006 s-a incheiat. Acest articol contine solutiile oficiale pentru toate probleme propuse spre rezolvare, cat si comentarii referitoare la concurs.
Fiecare grupa a avut spre rezolvare 3 probleme, fiecare fiind catalogata de catre comisie ca fiind usoara, medie sau grea. Batalia pentru calificarea la finala este abia la inceput!

Pentru mai multe detalii despre finala, cat si despre concursul preONI 2006 si sponsorii nostri va rugam sa consultati "pagina preONI-2006":preONI-2006.

Pentru mai multe detalii despre finala, cat si despre concursul preONI 2006 si sponsorii nostri va rugam sa consultati "pagina preONI-2006":http://infoarena.ro/preONI-2006.

Rezultatele finale sunt disponibile la:

h3. (clasele 11-12, problema grea)

Problema a fost gandita sa rasplateasca pe "fanii infoarena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/task/secventa, "Secventa 2":http://infoarena.ro/task/secv2, "Secventa 3":http://infoarena.ro/task/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice 2N*2M, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Problema a fost gandita sa rasplateasca pe "fanii info-arena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/task/secventa, "Secventa 2":http://infoarena.ro/task/secv2, "Secventa 3":http://infoarena.ro/task/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice 2N*2M, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Rezolvarea acum se va baza pe cautarea binara a balansului maxim (idee folosita si la rezolvarea problemei "Secventa 3":http://infoarena.ro/task/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica: