485 Exp

[•Bit_Master]

Nu. Inseamna ordinul radicalului.

O. Exista si pagina 2 de comentarii...

[edit] la fel ca si butonul de editare a mesajelor; nu mai posta consecutiv

[Later edit] Eu am postat direct de pe http://infoarena.ro/problema/exp, deci din afara forum-ului. Acolo nu exista buton de editare, de aceea nu l-am gasit. Ar trebui adaugat si acolo.

[•cristian9]

Puteti sa-mi dati niste teste, va rog? cat mai urate

[•dornescuvlad]

aici iau 40 puncte din 100 pct. si la eval oji 2006 iau 100 pucte.

[•SpiderMan]

La evaluatorul OJI iau 100 pct. usor, dar aici imi da TLE pe primul test,pe al doilea imi da 32ms. Care ar fi problema? Am facut intr-un vector de constante toate nr. prime , apoi am desc. fiecare nr. X in factori primi pana la sqrt.x, si apoi am parcurs pentru erori.
[Later Edit] Am rezolvat cu citire parsata si cu inca cateva modificari

aici iau 40 puncte din 100 pct. si la eval oji 2006 iau 100 pucte.

E ok rezolvarea, aici se pune accent pe timp (prea mult), limita ar trebui sa fie cel putin 0,2 secunde. Daca iti da Ok pe evaluator, inseamna ca ai facut ok problema. 

[•gabitzish1]

aici iau 40 puncte din 100 pct. si la eval oji 2006 iau 100 pucte.

E ok rezolvarea, aici se pune accent pe timp (prea mult), limita ar trebui sa fie cel putin 0,2 secunde. Daca iti da Ok pe evaluator, inseamna ca ai facut ok problema. 

Nu se pune prea mult accent pe timp. Daca o rezolvare care ia 100 pe un eval de la oji, pe infoarena ia doar 40 inseamna ca cineva a gasit o rezolvare mai buna, mai rapida, si n'ar strica sa o descoperi ca nu ai decat de invatat din asta. Daca te multumesti cu putin, e decizia ta.
De exemplu bublesort si qsort fac acelasi lucru, sorteaza la fel de corect, doar ca unul merge in O(N^2) altul in O(NlogN). Vei avea foarte mult de pierdut daca te multumesti doar cu buble, ca doar acelasi rezultat ti'l da.. dar un pic mai lent.

[•SpiderMan]

Da , asta asa este. Dar un incepator, care face aceasta problema ca si la OJI, nu cred ca ar putea rezolva problema in alt mod. Sper exemplu problema Al k-lea termen Fibonacci, se poate rezolva usor, dar metoda optima e cea cu matrice. Nu cred ca multi stiu operatii cu matrice 

[•Florian]

Nu cred ca multi stiu operatii cu matrice 

Cei care nu stiu inmultirea a doua matrice, ar trebui sa termine culegerea de info de la clasa, si abia apoi sa tasteze in browser "infoarena.ro". 

[•SpiderMan]

Eu ma refeream la cei de clasele mai mici 

[•paul_gabryel]

imi poate ajuta cineva
pe evaluatorul de la oji 2004 iau 100p si aici iau 40p cu incorect 
de ce ?

[•SpiderMan]

Aici sunt cateva teste in plus fata de OJI, un pic mai mari. Ai de grija mare la limite . 

[•dutzul]

imi da 80 de pct  pe infoarena si pe campion.edu.ro imi da 100 nu iau time limit exeded ci incorect pe testele 1 si 2
help 

[•SpiderMan]

Sunt teste mai mari, incearca ciurul lui eratosthenes pentru ele (nu sunt testele de la OJI, din cate tin minte sunt puse de pe InfoArena).

[•NicuCJ]

Iau 90 cu TLE pe primul test, pe al doilea am 24ms cel mai bine. Idei de optimizare ?

[•visanr]

Eu luam 90 cu TLE daca faceam descompunerea in factori primi pt un numar N for(int i = 2; i * i <= N; ++ i), dar daca tratam separat cazul cu i = 2, iar mai apoi for(i = 3; i * i <= N; i += 2) intra in timp.

[•veleandu]

Am luat 100 parsand citirea 

Eu am facut euler prima data.
Am retinut divizorii.
Cand descompuneam un numar luam doar numerele prime nu orice numere.

Nu a mers.

Apoi, in loc de sirul Viz la eular tineam pt fiecare numar factorul prim maxim care apare in descompunerea sa.
Pt 666013 tineam 666013 de exemplu .. ( stiu ca erau pana la 30.000 ).
Asta credeam ca o sa ajute.

Dar nu! Desi e o idee buna

Cand faci euler poti sa iti faci si descompunerea in factori primi.
Asa ar trebui sa iti iasa in o(1) queryul

MLE
Un vector( doar daca il declari ) ocupa 10 octeti ( 2,5 inturi )
Ocupa 700 bks vectorul de descompunere din care 400kbs doar faptul ca il declaram.
Iarasi o idee buna dar care nu merge )

[•kappykk]

Imi puteti oare spune de ce la testul 1 primesc TLE orice as face ?

[•stefi024]

Ma poate ajuta cineva si pe mine cu acesta problema ?
 
Cerinţa

Se dă un şir cu n elemente, numere naturale. Să se verifice dacă reprezintă o permutare a mulţimii {1,2,...,n}.
Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale şirului, separate prin spaţii.
Date de ieÅŸire

Programul afișează pe ecran mesajul DA, dacă şirul reprezintă o permutare a mulţimii {1,2,...,n}, respectiv NU în caz contrar.
Restricţii şi precizări

    1 ≤ n ≤ 100

[•SebiSebi]

Verifici, folosind un vector caracteristic, daca fiecare element intre 1 si N inclusiv apare in sir o data si numai o data.

[•stefi024]

     #include<iostream>
    using namespace std;
    int v[101],n,i,j,p;
    int main()
    {
     
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>v;
    for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++)
    if(v>v[j] )
    {
    int aux=v;
    v=v[j];
    v[j]=aux;
    }
    if(v=i)
    p=1;
    for(i=1;i<=n;i++)
    if(v!=i) p=0;
    if(p==1) cout<<"da";
    else cout<<"nu";
    return 0;
    }

Eu ma gandisem asa, dar nu este bine
Ce ar trebui sa adug sau sa modific?
Sincera sa fiu nu prea ma pricep, asa ca , va rog, nu ma judecati daca am scris o mare tampenie mai sus

[•ardeleanadrian]

De ce imi da pe primul test time limit exceeded?
Aveti vreo idee?

[•MareSite]

Faina problema   

[•razvand]

http://www.infoarena.ro/job_detail/1598125

Nu inteleg ce e gresit  , ma ajuta cineva  ?

[•1475369147896537415369]

salut. stie cineva care e diferenta dintre urmatoarele 2 surse?

http://www.infoarena.ro/job_detail/1905375
http://www.infoarena.ro/job_detail/1905376

liniile de cod care fac diferenta ar fi:

Cod:

for(int i = 0; prime[i] * prime[i] <= number; i++){
    while(number % prime[i] == 0){
        factor[prime[i]]++;
        number /= prime[i];
    }
}

si

Cod:

while(number % 2 == 0){
    factor[2]++;
    number /= 2;
}
for(int i = 3; i * i <= number; i += 2){
    while(number % i == 0){
        factor[i]++;
        number /= i;
    }
}

in prima varianta iteram numai prin numere prime pana la
radical din x, crezand ca e o idee mai buna. aproape ca iasa
din limita de timp, cand ma asteptam sa scot unul mai bun.
nu inteleg de ce e asa..