073 Perechi

[•domino]

Aici puteţi discuta despre problema Perechi.

[•mips]

Am facut problema si am facut teste verificand rezultatul prin forta bruta si toate testele pe care le-am facut mi-au iesit bine.Problema este ca iau 0 puncte si nu stiu de ce.Poate cineva care a rezolvat corect problema sa-mi zica cat ii da pt:
5040 : mie mi-a dat 203 si la fel si pe programul de verificare.
87297210:imi da 7655 da asta nu l-am testat (prea mult de asteptat )

[•filipb]

Da 7655 ( cat ai spus tu ). Daca lucrezi in C/C++, fii atent sa afisezi cu formatul corect... adica nu ai ceva de genul fprintf(fout, "%lld"), si rezultatul tau sa fie tinut intr-o variabila doar de tip long (nu long long). Sau daca ai marcaj de sfarsit de linie (desi nu sunt sigur daca evaluatorul ia asta in considerare)

bubbleSORT

[•mips]

lucrez in pascal si am verificat fisierul de iesire si nu este decat numarul fara alte marcaje.Oricum mersi filipb.

[•cristy]

ce complexitate ati scos?...eu am scos un O(Sqrt(N)+D^2) si imi iese din timp pe un test si imi da 3 WA...D este numarul de divizori...

[u-92]

cu complexitatea asta nu exista nici un motiv sa iti iasa din timp, numarul de divizori e foarte mic.. poate nu folosesti long long, iti cicleaza undeva.. mai verifica cu niste teste mari

[•cristy]

am scapat de TLE....am WA pe primu test...am verificat si pt N=1...dar tot WA...

[•wefgef]

ce complexitate ati scos?...eu am scos un O(Sqrt(N)+D^2) si imi iese din timp pe un test si imi da 3 WA...D este numarul de divizori...

se poate in O(sqrt(N))

[•Protoman]

salut!  :)Am incercat sa fac problema intr-o complexitate O(sqrt(n)+numarul de divizori^2)  imi merge sub 0.01 pe majoritatea testelor de evaluare dar imi iese din timp la 3 teste....mai precis pe 4 5 si 14 .... care ar fi motivul?( folosesc FPC )

si cam ce ar insemna cazuri particulare?

Multumesc anticipat!

[•wefgef]

Poate ca iti intra in ciclu infinit pe unele cazuri particulare.

[•fireatmyself]

numarul de divizori poate fi destul de mare (de exemplu 2095632000 are 1152 de divizori, dar exista numere mai mici decat el cu un numar mai mare de divizori). dupa cum spunea si wefgef, aceasta problema se poate rezolva in O(sqrt(N)) pentru a obtine punctaj maxim. personal eu am rezolvat-o in O(PMAX * 2^PMAX), unde PMAX este numarul maxim de facori primi ce pot copune un numar mai mic decat 2^31. (PMAX = 11, parca)

[•CezarMocan]

In cazul asta ati putea sa ne dati un hint micut?? (si eu intampin aceleasi dificultati)
 

[•alex_damian]

n % x merge cand n si x sunt long long??

[•cos_min]

ar trebui sa mearga  Ai grija ca este f inceata, incearca sa o eviti (de ex. foloseste scaderea )

[•devilkind]

nu sunt chiar asa sigur ca in acest caz e bine sa folosesti scaderea. Adik scaderea o folosesti atunci cand scazi o singura data. Dar dak u vrei sa afli restul impartirii lui 2 000 000 000 la 2 si faci scadere iti va iesi imediat din timp. Incearca sa faci asa:

r = n - ((n/x) * x);

[•alex_damian]

doh silly me ... corect

[•wefgef]

Nu stiu cum v-ati gandit voi, insa eu aflu exponentii factorilor primi din descompunerea lui N, iar apoi am gasit o formula . Poate va vine si voua ideea cum se face asa daca nu va intra in timp rezolvarea voastra 

[•alex_damian]

exact asta fac si eu doar ca am gresit formula 

[•CezarMocan]

Multumim wef (in numele meu si al lui Andi) . Sper sa gasim formula cat mai repede 
 

[•Protoman]

Bine zis Cezar...  nom avea noi 100 inca da macar incercam...chiar daca, cu ajutor!
Dar tot nu ma prea prind... ce ar trebui sa fie cazul particular .... decat asha o idee sau ceva minor ash vrea sa stiu....

[•andunhill]

O problema aproape la fel s-a dat la oni 2010 cl 9 numita cmmmc. Numai ca perechile trebuiau sa fie ordonate si se cerea si perechea cu suma cea mai mica. Daca o faceam probabil nu buseam la oni.

[•narcis2007]

am luat 10p...in 8 teste imi depaseste timpul de executie...

[•maritim]

Imi poate da si mie cineva un Hint pentru O(sqrt(N)), sau pentru formula ! Nu pot sa trec de 85 pct in O(sqrt(N) + D^2).

L.E. : Pentru a-i ajuta si pe ceilalti, sa caute in solutiile de la ONI 2010 clasa a 9-a, la problema cmmmc. Acolo este explicata cu de-amanuntul formula si evident o rezolvare mai rapida pentru aceasta problema .

[•caen1]

M-am uitat si eu peste solutia de la ONI 2009, am implementat cu formula si am luat 95p cu TLE pe testul 7. Cred ca am o problema la descompunerea in factori primi. Eu o fac ca mai jos, asta ar fi problema? Am incercat si cu ciur, dar iau 0 cu TLE pe toate testele

Cod:

for(i = 2; n > 1; ++i) {
   cnt = 0;
   if(!(n % i)) ++cnt, n /= i;
}

Multumesc!

[•MciprianM]

Gandestete ce se intmapla cand n este prim!