(Creat de '_Cosmin_':user/Cosmin la data de _2005-11-19_ categoria _Competitii_, autor(i) _Echipa info-arena_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
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.

 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.

*Continut lung:*

==Include(page="template/raw")==
 

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 [1]http://infoarena.devnet.ro/index.php?page=preONI_2006.

(clasa a 9-a problema medie)

Mai intai sa completam matricea doar cu 1 si 5 astfel incat produsul elementelor de pe fiecare linie sau coloana sa fie 5. Observam ca pe fiecare linie si pe fiecare coloana se plaseaza exact un 5, restul matricii fiind completata cu 1. Este evident ca fiecare permutare a multimii (1, 2 * N) reprezinta de fapt o posibilitate de aranjare a numarului 5 in matrice, iar de aici deducem ca numarul de posibilitati de a completa matricea doar cu 1 si 5 este P[N] (adica N!). Cum putem folosi si -1 si -5, rezultatul final va fi 2^N*N*N!

Mai intai sa completam matricea doar cu 1 si 5 astfel incat produsul elementelor de pe fiecare linie sau coloana sa fie 5. Observam ca pe fiecare linie si pe fiecare coloana se plaseaza exact un 5, restul matricii fiind completata cu 1. Este evident ca fiecare permutare a multimii (1, 2 â?? N) reprezinta de fapt o posibilitate de aranjare a numarului 5 in matrice, iar de aici deducem ca numarul de posibilitati de a completa matricea doar cu 1 si 5 este P[N] (adica N!). Cum putem folosi si -1 si -5, rezultatul final va fi 2^N*N*N!

La implementare trebuie sa se efectueze operatii cu numere mari. De asemenea, se recomanda ca baza in care se lucreaza trebuie sa fie destul de mare pentru a se obtine eficienta dorita.

(A + B)^2 = Rosu^2

(C * D)^2 = Albastru^2

(C â?? D)^2 = Albastru^2

Rosu^2 + Albastru^2 = Roz^2

De aici avem ca (A + B)^2 + (C * D)^2 =A^2 + B^2 + C^2 + D^2, astfel obtinem AB = CD, dar B = H * A, iar D = W * C deci avem ca C^2 * WC + A(H * A) = 0. Daca il fixam pe A atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta C, solutia trebuie sa fie intreaga intre 0 si W.

De aici avem ca (A + B)^2 + (C â?? D)^2 =A^2 + B^2 + C^2 + D^2, astfel obtinem AB = CD, dar B = H â?? A, iar D = W â?? C deci avem ca C^2 â?? WC + A(H â?? A) = 0. Daca il fixam pe A atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta C, solutia trebuie sa fie intreaga intre 0 si W.

Astfel in O(H) vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H * W. Acest dreptunghi poate fi pus in (N * H + 1) * (M * H + 1) locatii pe o grila de dimensiune N * M. Deci solutia are complexitate O(N*M^2), pentru fiecare dreptunghi de dimensiuni 1 <= H <= N si 1<= W <= M calculandu-se numarul de dreptunghiuri inscrise.

Astfel in O(H) vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H * W. Acest dreptunghi poate fi pus in (N â?? H + 1) * (M â?? H + 1) locatii pe o grila de dimensiune N * M. Deci solutia are complexitate O(N*M^2), pentru fiecare dreptunghi de dimensiuni 1 <= H <= N si 1<= W <= M calculandu-se numarul de dreptunghiuri inscrise.

O rezolvare de complexitate O(N^2*M^2) in care se cautau solutiile ecuatiei printr-un for ar fi luat 60 de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de 80 de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu A <= H/2 este egal cu numarul de solutii cu A >= H * H/2 si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H, W este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni W, H.

O rezolvare de complexitate O(N^2*M^2) in care se cautau solutiile ecuatiei printr-un for ar fi luat 60 de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de 80 de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu A <= H/2 este egal cu numarul de solutii cu A >= H â?? H/2 si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H, W este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni W, H.