• Home
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
• Aparitii in presa
• Runde
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda Finala

Comentarii aici...

Solutii Runda Finala

Orase

(problema usoara, clasa a 9-a)

Sarpe

(problema medie, clasa a 9-a)

Vom calcula intai numarul de posibilitati pentru cazul in care 1 se afla in unul din colturi. Sa presupunem ca l-am asezat in coltul stanga sus. Distingem doua cazuri:

• 2 este asezat la dreapta lui 1 caz in care exista un singur mod de completare

• 2 este asezat in coltul dreapta jos caz in care vom avea de completat tabla ramasa cu numerele 3, 4, ... 2N punand 3 la dreapta lui 2 lucru care este echivalent cu completarea unei table cu N-1 coloane cu 1 fixat in unul din colturi.

In concluzie numarul de moduri in care se poate completa tabla de dimensiune N cu 1 pus intr-un colt fixat este N. Analizam acum cazul in care 1 este pus pe una din coloanele 2, 3 , ... N-1. 2 nu poate fi pus sub 1 deoarece tabla s-ar imparti in doua bucati care nu sunt conexe si nu se poate completa comform cerintei. Daca 2 este pozitionat in stanga lui 1 toate coloanele 1, 2, ... i se vor completa in mod unic.

Deci vor ramane de completat N-i coloane care trebuie completate cu 2*i+1 pus intr-un colt fixat. Deci vom avea in total N-i posibilitati. In mod analog daca 2 se afla in dreapta vom avea i-1 posibilitati. Numarul total de posibilitati cand 1 se afla pe una din coloanele 2, 3, ... N-1 va fi suma de la 2 la N-1 din 2(N-i+i-1) adica 2(N-2)(N-1) deoarece se poate incepe de sus sau de jos. Raspunsul cautat va fi 4N + 2(N-1)(N-2), N > 1. Operatiile trebuiau efectuate pe numere mari.

Sate

(problema grea, clasa a 9-a, problema usoara, clasa a 10-a)

Branza

(problema medie, clasa a 10-a)

Aceasta problema se rezolva folosind metoda programarii dinamice. O solutie triviala are complexitatea O(N*T) si se realizeaza calculand vectorul m[i] = costul minim pentru a obtine un kg de branza in saptamana i. Acesta se obtine folosind formula m[i] = min{C[j] + (i-j)*S | i-j ≤ T}.
Pentru a reduce complexitatea la O(N) se observa ca pentru calculul lui m[i] avem nevoie doar de valorile lui C cuprinse intre max(1, i-T) si i, interval a carei dimensiuni nu poate decat sa creasca sau sa ramana constanta. Se foloseste un deque in care se introduc pe rand valorile din C modificate corespunzator pentru a asigura gasirea minimului cerut la fiecare pas. Astfel la pasul i se va introduce in deque valoarea C[i] + (N-i)*S, pentru a mentine relatia de ordine corespunzatoare relatiei de recurenta intre elementele structurii. La pasul i se considera elementul din coada deque-ului (fie acela provenit de la C[j]) din care se scade (N-j)*S pentru a obtine pe m[i].
Solutia ceruta este m[1] * P₁ + m[2] * P₂ + ... + m[N] * P_N

Gradina

(problema grea, clasa a 10-a)

P-Sir

(problema usoara, clasele 11-12)

Eval

(problema medie, clasele 11-12)

Obiective

(problema grea, clasele 11-12)

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: