infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Iunie 15, 2005, 15:40:12



Titlul: 073 Perechi
Scris de: Mircea Pasoi din Iunie 15, 2005, 15:40:12
Aici puteţi discuta despre problema Perechi (http://infoarena.ro/problema/perechi).


Titlul: 073 Perechi
Scris de: Pavel Mircea din Iunie 18, 2005, 15:01:08
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 )


Titlul: Atata da
Scris de: Filip Cristian Buruiana din Iunie 18, 2005, 19:55:25
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


Titlul: 073 Perechi
Scris de: Pavel Mircea din Iunie 19, 2005, 08:18:55
lucrez in pascal si am verificat fisierul de iesire si nu este decat numarul fara alte marcaje.Oricum mersi filipb.


Titlul: 073 Perechi
Scris de: Rus Cristian din Martie 25, 2006, 19:49:39
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...


Titlul: 073 Perechi
Scris de: u-92 din Martie 25, 2006, 20:11:09
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


Titlul: 073 Perechi
Scris de: Rus Cristian din Martie 25, 2006, 21:32:07
am scapat de TLE....am WA pe primu test...am verificat si pt N=1...dar tot WA...


Titlul: 073 Perechi
Scris de: Andrei Grigorean din Martie 26, 2006, 15:36:59
Citat din mesajul lui: 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...


se poate in O(sqrt(N))


Titlul: Raspuns: 073 Perechi
Scris de: Andrei Purice din Februarie 15, 2007, 10:33:56
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!


Titlul: Raspuns: 073 Perechi
Scris de: Andrei Grigorean din Februarie 15, 2007, 16:57:00
Poate ca iti intra in ciclu infinit pe unele cazuri particulare.


Titlul: Raspuns: 073 Perechi
Scris de: Bogdan-Alexandru Stoica din Februarie 15, 2007, 17:33:03
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)


Titlul: Raspuns: 073 Perechi
Scris de: Cezar Mocan din Februarie 15, 2007, 17:55:52
In cazul asta ati putea sa ne dati un hint micut?? :-' (si eu intampin aceleasi dificultati)
 :monkey:


Titlul: Raspuns: 073 Perechi
Scris de: Damian Alexandru din Februarie 15, 2007, 20:14:36
n % x merge cand n si x sunt long long??


Titlul: Raspuns: 073 Perechi
Scris de: Bondane Cosmin din Februarie 15, 2007, 20:19:05
ar trebui sa mearga  :wink: Ai grija ca este f inceata, incearca sa o eviti (de ex. foloseste scaderea )


Titlul: Raspuns: 073 Perechi
Scris de: Savin Tiberiu din Februarie 15, 2007, 20:21:46
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);



Titlul: Raspuns: 073 Perechi
Scris de: Damian Alexandru din Februarie 15, 2007, 20:23:56
doh silly me ... corect


Titlul: Raspuns: 073 Perechi
Scris de: Andrei Grigorean din Februarie 15, 2007, 20:41:56
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  :-'


Titlul: Raspuns: 073 Perechi
Scris de: Damian Alexandru din Februarie 15, 2007, 20:44:05
exact asta fac si eu doar ca am gresit formula  :D


Titlul: Raspuns: 073 Perechi
Scris de: Cezar Mocan din Februarie 15, 2007, 20:46:29
Multumim wef (in numele meu si al lui Andi) :) . Sper sa gasim formula cat mai repede  :weightlift:
 :monkey:


Titlul: Raspuns: 073 Perechi
Scris de: Andrei Purice din Februarie 15, 2007, 20:53:41
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....???


Titlul: Răspuns: 073 Perechi
Scris de: Macarescu Sebastian din Aprilie 22, 2010, 07:47:43
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.


Titlul: Răspuns: 073 Perechi
Scris de: Ciobotariu Narcis din Februarie 21, 2011, 09:08:30
am luat 10p...in 8 teste imi depaseste timpul de executie...


Titlul: Răspuns: 073 Perechi
Scris de: Cristian Lambru din Mai 07, 2011, 21:32:38
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 :) .


Titlul: Răspuns: 073 Perechi
Scris de: c a e n din Mai 14, 2011, 20:23:42
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!


Titlul: Răspuns: 073 Perechi
Scris de: MciprianM din Mai 14, 2011, 20:28:05
Gandestete ce se intmapla cand n este prim!


Titlul: Răspuns: 073 Perechi
Scris de: c a e n din Mai 14, 2011, 20:54:08
Am reusit sa o rezolv de 100 verificand daca N este prim inainte de a calcula rezultatul. Asta ar fi solutia corecta?


Titlul: Răspuns: 073 Perechi
Scris de: MciprianM din Mai 15, 2011, 08:56:44
Pentru a afla divizorii unui numar poti face asa:

Cod:
for ( d = 2; d * d <= n; ++ d ){
        if ( n % d == 0 )
                scrie d si n/d
}

Astfel in O(sqrt(n)) putem afla toti divizorii! Totusi atentie la patrate perfecte!(9, 16, ...)
Pentru descompunere in factori primi, putem face similar:
Cod:
k = 0;
for ( d = 2; d * d <= n; ++ d ){
        if ( n%d==0 ){     p [ k ]  = d; e [ k ] = 0; k ++;}
        while ( n % d == 0 ){
                e [ k - 1] ++;
                n/=d;
         }
}
if ( n > 1 ){p[k]=n;e[k ]=1;k++;}


Titlul: Răspuns: 073 Perechi
Scris de: UAIC.VlasCatalin din Iulie 15, 2011, 19:43:59
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 ](*,)


Titlul: Răspuns: 073 Perechi
Scris de: cont cu nume gresit sau fals din Iulie 15, 2011, 19:52:54
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.


Titlul: Răspuns: 073 Perechi
Scris de: UAIC.VlasCatalin din Iulie 15, 2011, 20:15:37
defapt, de acolo doaream sa aflu formula pentru a rezolva anume aceasta problema :?


Titlul: Răspuns: 073 Perechi
Scris de: cont cu nume gresit sau fals din Iulie 15, 2011, 20:41:05
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=a1d1*a2d2*...*akdk 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 aidi.
2. exista un caz in care numarul x contine aidi, iar y are ai in componenta dar nu de suficient de multe ori.
3. exista un caz in care numarul y contine aidi, iar x are ai in componenta dar nu de suficient de multe ori.

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

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.


Titlul: Răspuns: 073 Perechi
Scris de: UAIC.VlasCatalin din August 01, 2011, 19:49:37
Poate sa-mi dea careva vreo sugestie de ce am intruna NON ZERO EXIT STATUS la testul 9, pls?


Titlul: Răspuns: 073 Perechi
Scris de: Stefan Teodorescu din Ianuarie 03, 2012, 21:05:03
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


Titlul: Răspuns: 073 Perechi
Scris de: Florin Chirica din Ianuarie 03, 2012, 21:17:38
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).


Titlul: Răspuns: 073 Perechi
Scris de: Paul-Dan Baltescu din Ianuarie 03, 2012, 21:47:12
De fapt el are O(N^2 log N), deoarece calculeaza la fiecare pas cmmdc-ul.


Titlul: Răspuns: 073 Perechi
Scris de: Visan Radu din Aprilie 25, 2012, 21:51:40
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...


Titlul: Răspuns: 073 Perechi
Scris de: Mihai-Alexandru Dusmanu din Aprilie 25, 2012, 21:59:52
Cred ca greseala ta este in urmatoarea parte a codului:
Cod:
if(n>1) factors.push_back(n);

Trebuie sa fie:
Cod:
factors.push_back(1);


Titlul: Răspuns: 073 Perechi
Scris de: Visan Radu din Aprilie 25, 2012, 22:01:10
Asta era, multumesc mult!


Titlul: Răspuns: 073 Perechi
Scris de: Dinu Radu din Noiembrie 05, 2012, 20:39:31
Hint : cmmmc a doua nr nu poate fi = cu n daca produsul lor e mai mic ca n.


Titlul: Răspuns: 073 Perechi
Scris de: Soucup Nicolae Silviu din Noiembrie 11, 2012, 14:48:25
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:


Titlul: Răspuns: 073 Perechi
Scris de: Darius-Florentin Neatu din August 04, 2013, 15:04:36
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:
Cod:
void Solve()
{
    for(int i=1;i<=k && n!=1;i++)
        if(n % P[i]==0)
        {
            int exp=0;
            while(n % P[i]==0)n/=P[i],exp++;
            //formula-sol
        }

    
    g<<sol<<'\n';

}


Titlul: Răspuns: 073 Perechi
Scris de: Salajan Razvan din August 04, 2013, 17:35:08
Pierzi cazul cand n > 1( dupa ce l-ai descompuns in factori primi ). Trateaza acest caz si o sa iei 100.


Titlul: Răspuns: 073 Perechi
Scris de: Darius-Florentin Neatu din August 04, 2013, 19:28:32
da...ai avut dreptate...ms mult....nu observasem treaba asta....si trimisesem 5000 de surse:D....ms mult...voi fi mai atent pe viitor


Titlul: Răspuns: 073 Perechi
Scris de: patcas rares danut din August 15, 2016, 18:14:28
ce se intampa daca n e prim


Titlul: Răspuns: 073 Perechi
Scris de: Adrian Dinu din August 16, 2016, 15:11:31
Daca n e prim atunci vei avea doar 2 perechi: (1, n), (n, n).


Titlul: Răspuns: 073 Perechi
Scris de: Coroian David din Noiembrie 05, 2016, 13:09:46
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.