Imprimă pagina - 948 Perle2

Titlul: 948 Perle2
Scris de: Stefan Istrate din Noiembrie 23, 2009, 19:46:52

Aici puteti discuta despre problema Perle2 (http://infoarena.ro/problema/perle2).

Titlul: Răspuns: 948 Perle2
Scris de: Posea Elena din Noiembrie 11, 2011, 21:38:14

are cineva vreo idee ce e cu testul 9? :'( ca iau tle pe ea, am incercat sa citesc intr-un buffer numerele si dupa aia sa parsez, dar merge chiar si mai incet. in general, am incercat cam tot ce mi-a trecut prin cap sa mearga mai rapid, dar tot tle iau....
asta e ceea ce fac:

Cod:

int x=n-1;
for(i=0;i<x;i++){
    if(diag[i]>0){
      //sunt pe linia i din "matrice"
      coloana[i]=diag[i];
      if(coloana[i]>max){max=coloana[i];}
      for(j=i+1;j<n;j++){
        coloana[j]=coloana[j-1]+diag[j];
        if(coloana[j]<=0)break;
        if(coloana[j]>max){
            max=coloana[j];
        }
      }
    }
}

datele le citesc cu stream-uri, in varianta care am vazut ca e cea mai rapida:
http://infoarena.ro/job_detail/631145

Titlul: Răspuns: 948 Perle2
Scris de: Paul-Dan Baltescu din Noiembrie 11, 2011, 22:11:08

Iei Time Limit Exceeded pentru ca nu ai complexitatea buna. Problema se rezolva in O(N). Niste indicatii gasesti aici (http://infoarena.ro/algoritmiada-2010/runda-1/solutii) si aici (http://infoarena.ro/problema/ssm).

Am scazut limita de timp si am reevaluat sursele. Nu era bine ca iti treceau 9 teste din 10 cu complexitate O(N^2).

Titlul: Răspuns: 948 Perle2
Scris de: Posea Elena din Noiembrie 11, 2011, 22:45:01

ok. mersi de linkuri, mi se paruse mie ca era prea usor sa fie asa:)

Titlul: Răspuns: 948 Perle2
Scris de: Vasilut Lucian din Aprilie 11, 2012, 08:52:09

Dacă valoarea maximă posibilă este negativă, atunci Laura va prefera sa nu aleagă nici o perlă.
raspunsul va fi 0 in acest caz? :-k

Titlul: Răspuns: 948 Perle2
Scris de: andreycurent din Aprilie 11, 2012, 09:19:03

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Stefan Istrate din Noiembrie 23, 2009, 19:46:52