infoarena

Aici puteţi discuta despre problema Perechi (http://infoarena.ro/problema/perechi).

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 :P )

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

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

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...

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

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

se poate in O(sqrt(N))

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!

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

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)

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

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

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

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);

doh silly me ... corect

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  :-'

exact asta fac si eu doar ca am gresit formula  :D

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

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....???

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.

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

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 :) .

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 :-?

Multumesc!

Gandestete ce se intmapla cand n este prim!

Am reusit sa o rezolv de 100 verificand daca N este prim inainte de a calcula rezultatul. Asta ar fi solutia corecta?

Pentru a afla divizorii unui numar poti face asa:


Astfel in O(sqrt(n)) putem afla toti divizorii! Totusi atentie la patrate perfecte!(9, 16, ...)
Pentru descompunere in factori primi, putem face similar:

cei care au gasit solutia problemei cmmmc de la ONI 2010, dati-mi si mie va rog un link, ca tot caut sa nu pot gasi nimic ](*,)

Cred ca ar fi mai bine sa postezi aici (http://infoarena.ro/forum/index.php?topic=4799.msg40529#msg40529) pentru ca problema cmmmc (http://infoarena.ro/problema/cmmmc) este si pe infoarena.

defapt, de acolo doaream sa aflu formula pentru a rezolva anume aceasta problema :?

Oricum, daca esti interesat de problema cmmmc, e mai bine sa postezi acolo. Daca nu, atunci spune ca esti interesat de perechi.
Uite un hint pentru perechi.

Daca ai n=a₁^d₁*a₂^d₂*...*a_k^d_k considera vectorul d.
pentru fiecare element i te gandesti asa:
1. exista un caz in care si numarul x si numarul y au in componenta a_i^d_i.
2. exista un caz in care numarul x contine a_i^d_i, iar y are a_i in componenta dar nu de suficient de multe ori.
3. exista un caz in care numarul y contine a_i^d_i, iar x are a_i in componenta dar nu de suficient de multe ori.

nici x, nici y nu vor avea a_i in componenta la un exponent mai mare de d_i.

Si nu depinde de cum alegi pentru i ca sa alegi pentru j.

Daca vreun admin/moderator considera ca am zis un prea mult il rog sa-mi stearga postul.

Poate sa-mi dea careva vreo sugestie de ce am intruna NON ZERO EXIT STATUS la testul 9, pls?

eu nu am facut descompunerea in factori
in for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
calculez cmmdc i si j si calculez cmmmc cu formula cmmmc=(a*b)/cmmdc(a,b) (formula tine)
si iau TLE la majoritatea (iau 15 puncte) cum ar trb sa fac? :D

Stefane, vezi ca ai complexitatea O(N^2) care e prea mare aici. In mod normal cu N^2 intra pentru N <= 1000. Intra si tu pe fb si iti zic acolo cum sa faci, nu pot sa scriu aici solutia (sau citeste postu' lu Magnus de mai sus).

De fapt el are O(N^2 log N), deoarece calculeaza la fiecare pas cmmdc-ul.

Imi puteti spune si mie care ar fi motivul pt care iau incorect pe testul 7? http://infoarena.ro/job_detail/741411
Am trimis in cateva luni peste 80 de surse, nu pot lua 100...

Cred ca greseala ta este in urmatoarea parte a codului:

Trebuie sa fie:

Asta era, multumesc mult!

Hint : cmmmc a doua nr nu poate fi = cu n daca produsul lor e mai mic ca n.

Finally! Cred ca acum merge si pentru N>2^31 - Pentru N=6227020800 exista 1584 divizori si 15592 de perechi gasite sub 0,5 secunde (in medie 400-450 ms) - Nu stiu daca valorile sunt trunchiate  :yahoo:

va rog sa ma ajutati...iau 90p...incorect pe testele 9 si 18.......
am gasit o formula in care apar exponentii numerelor prime din descompunerea lui n in factori.... totusi da incorect pe 2 teste si nu stiu de ce.....am scris tot codul de la capat si degeaba... e vreun caz special ceva?
LE:

Pierzi cazul cand n > 1( dupa ce l-ai descompuns in factori primi ). Trateaza acest caz si o sa iei 100.

da...ai avut dreptate...ms mult....nu observasem treaba asta....si trimisesem 5000 de surse:D....ms mult...voi fi mai atent pe viitor

ce se intampa daca n e prim

Daca n e prim atunci vei avea doar 2 perechi: (1, n), (n, n).

Salut!
iau 10 puncte si nu inteleg de ce, am folosit formula: ((exp1 * 2 + 1) * (exp2 * 2 + 1) * ... * (expn * 2 + 1) + 1) / 2

LE : am 100.