Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-11-25 13:09:11.
Revizia anterioară   Revizia următoare  

Solutii preONI 2008, Runda 1

comentarii aici...

Ordine

Multimi 2

Ecuatie

Economie

Teren

Pairs

Problema admite o rezolvare triviala de complexitate O(N2log MAX), unde MAX este maximul dintre cele N numere ale multimii M: pentru fiecare pereche de numere din multimea data se calculeaza cel mai mare divizor comun folosind algoritmul lui Euclid. O astfel de rezolvare obtine 20-30 de puncte, in functie de prezenta unor optimizari. Rezolvarea optima are complexitatea O(MAX log MAX) si se baza pe faptul ca O(N/1 + N/2 + N/3 ... + N/N) = O(N log N), pentru orice N.
Din numarul total de perechi, N*(N-1)/2, vom scadea numarul de perechi (x y), astfel incat x si y nu sunt prime intre ele si vom obtine rezultatul cerut. Notam cu Res numarul de perechi (x y), cu cmmdc(x, y) > 1. Pentru a afla efectiv numarul Res vom folosi procedeul includerii si excluderii. Fie xi numarul de numere din M care se divid cu i. Vectorul x se poate calcula in O(MAX log MAX): pentru fiecare numar i de la 1 la MAX verificam cate din numerele i, 2i, 3i ... [MAX/i]*i apartin multimii M. Consideram toate numerele P ce se scriu ca produs de numere prime, unde fiecare numar prim este folosit cel mult o data. Daca numarul de numere prime din descompunerea lui P este un numar impar, adunam xP la Res. Altfel, din Res scadem xP.
Rezolvarea de complexitate O(MAX log MAX) asigura obtinerea punctajului maxim.

Aliens

Problema se rezolva cu ajutorul programarii dinamice. Fiecare fractie din cele date se poate scrie ca un produs de forma 2x * 3y * 5z, unde x, y si z sunt numere intregi. Daca codificam fiecare fractie prin tripletul corespunzator, problema revine la a selecta anumite triplete (x1, y1, z1), (x2, y2, z2)... (xK yK zK) din cele N astfel incat:

  • x1 + x2 + ... + xK ≥ 0
  • y1 + y2 + ... + yK ≥ 0
  • z1 + z2 + ... + zK ≥ 0
  • 2(x1 + x2 + ... + xK) * 3(y1 + y2 + ... + yK) * 5(z1 + z2 + ... + zK) sa fie maxim posibil.

Problema se rezolva prin programare dinamica. Fie Di, x3, x5 valoarea maxim posibila pentru exponentul lui 2 care se poate obtine din primele i fractii, astfel incat exponentul lui 3 sa fie x3 si exponentul lui 5 sa fie x5. Tabloul D poate contine si indici negativi! Relatia de recurenta este urmatoarea:
Di, x3, x5 = maxim(Di-1, x3, x5, x2' + Di-1, x3-x3', x5-x5'), unde (x2' ×3' x5') este tripletul asociat celei de a i-a fractii.
Din considerente de memorie nu vom retine tot tabloul D. Deoarece elementele de pe pozitii de forma (i, a, b) depind doar de elemente de pe pozitii de forma (i-1, a', b') vom retine o singura matrice in locul unui tablou tridimensional si vom actualiza elementele din aceasta matrice printr-o parcurgere convenabila a indicilor.
Dupa ce avem tabloul D construit, aflam maxim(2DN,x3,x5 * 3x3 * 5x5), cu DN, x3, x5 ≥ 0, x3 ≥ 0 si x5 ≥ 0. Pentru a compara doua numere 2x1 * 3y1 * 5z1 si 2x2 * 3y2 * 5z2 vom logaritma si vom compara x1*ln2 + y1*ln3 + z1*ln5 cu x2*ln2 + y2*ln3 + z2*ln5. Atunci cand am aflat o solutie optima, este necesara implementarea operatiilor pe numere mari, deoarece rezultatul nu se incadreaza in nici un tip de date conventional.
Complexitatea problemei este O(N3) de constanta 4*(log3MAX)*(log5MAX), unde MAX = 400.000.000. Aceasta solutie obtine 100 de puncte.

Tunelul groazei

NKPerm