307 Maxsecv

[•DITzoneC]

Aici puteţi discuta despre problema Maxsecv.

[•pocaitu]

         De ce nu da bine la pb asta daca caut cele mai lungi doua subsecvente de 1 si afisez suma lor ??

[•filipb]

Trebuie sa ai grija la cum actualizezi maximele celor doua subsecvente. Daca max1 si max2 sunt cele doua maxime si l lungimea secventei curente, trebuie sa faci cam asa:

Cod:

if (l >= max1) max2 = max1, max1 = l;
else if (l > max2) max2 = l;

Aici s-ar putea sa gresesti.

[•BlackElf]

exact ideea asta am folosit si eu... singura problema e ca la primele 6 imi da OK dar apoi... TLE...

sincer nu am habar cum ar putea fi mai rapid

idei?

[•cos_min]

incearca direct din citire...fara sa folosesti alte siruri ... altceva nu vad sa fie
spor 

[•Tabara]

exact ideea asta am folosit si eu... singura problema e ca la primele 6 imi da OK dar apoi... TLE...

sincer nu am habar cum ar putea fi mai rapid

idei?

Ce complexitate ai la program ?
Merge de 100 si daca nu faci direct din citire.Idee este sa ai neaparat complexitate liniara. 

 

[•BlackElf]

Da, am incercat sa fac o data cu citirea. De fapt... uite sursa:

Cod:

#include <iostream.h>
#include <fstream.h>

ifstream in ("maxsecv.in");
ofstream out ("maxsecv.out");

int main ()
{
int max1=0,max2=0,N,*a;
register int i,k=0;

a=new int [1000000];

in>>N;
for (i=0;i<N;i++)
 {
 in>>a[i];
 if (!a[i])
   k=0;
  else
   k++;
 if (k>max1)
  max1=k;
 else
  if (k>max2)
   max2=k;
 }

out<<max1+max2;

delete [] a;
return 0;
}

Poate imi scapa ceva... oricum de corect e corect ... 6/10

[•Tabara]

Da, am incercat sa fac o data cu citirea. De fapt... uite sursa:

Cod:

#include <iostream.h>
#include <fstream.h>

ifstream in ("maxsecv.in");
ofstream out ("maxsecv.out");

int main ()
{
int max1=0,max2=0,N,*a;
register int i,k=0;

a=new int [1000000];

in>>N;
for (i=0;i<N;i++)
 {
 in>>a[i];
 if (!a[i])
   k=0;
  else
   k++;
 if (k>max1)
  max1=k;
 else
  if (k>max2)
   max2=k;
 }

out<<max1+max2;

delete [] a;
return 0;
}

Poate imi scapa ceva... oricum de corect e corect ... 6/10

Incearca sa faci fara alocare dinamica. 

[•cos_min]

nu ai nevoie de sirul ala. se poate usor si fara. Citeste mai bine o variabila de n ori

[•BlackElf]

nu ai nevoie de sirul ala. se poate usor si fara. Citeste mai bine o variabila de n ori

Doamne... frate... de ce m-am complicat?

Mda... no comment

Edit: tot 6/10... 0_O la 10-20 ms... fara vector si fara alocare dinamica.

[•Tabara]

nu ai nevoie de sirul ala. se poate usor si fara. Citeste mai bine o variabila de n ori

Doamne... frate... de ce m-am complicat?

Mda... no comment

Edit: tot 6/10... 0_O la 10-20 ms... fara vector si fara alocare dinamica.

Schimba atunci citirea.Fa-o in C.

[•astronomy]

Faza e ca programul tau e gresit, nu ai fost atent la ce zis filipb intr-un post mai sus.

[•devilkind]

Cod:

 if (k>max1)
  max1=k;
 else
  if (k>max2)
   max2=k;

secventa asta e gresita
vezi asa

Cod:

if (k>max1) {max2=max1;max1=k;}
   else (if k>max2) max2=k;

[•Tabara]

Faza e ca programul tau e gresit, nu ai fost atent la ce zis filipb intr-un post mai sus.

El intrebase cum sa evite TLE-ul. 
Daca isi rezolva faza cu tle-ul o sa ia maxim 90 de puncte. ( Si eu am gresit acolo  )
( M-am cam mirat si eu ca a luat 60 cu codul ala  ).

[•marius21]

faci comparatia numai cand ai un 0 si k-ul<>0 (adica cand iesi dentr-o secventa de 1-uri :1 1 1 0 0
Mie imi da

[•jdv]

Ati putea pune cateva teste pe forum?

[•devilkind]

testele oficiale nu se fac publice. Daca vrei sa iti testezi programu incearca :

1 0 0 1 1 1 0 0 0 1 1

raspunsu e 5.

[•jdv]

Intr-adevar e 5...si programul merge bine...

Nu ma asteptam la testele oficiale...ci doar niste exemple...( poate imi scapa ceva )

[•astronomy]

Poate pierzi ceva caz particular gen: 000 sau 100
Daca nu, fa un program in complexitate mare dar care furnizeaza sigur raspunsul corect, genereaza teste aleatoare si cand gasesti unul pe care programul tau da raspuns diferit baga un debug.

[•jdv]

Pe testele care le-am incercat am obtinut raspunsuri bune...

Oare unde e greseala?

A mai patit cineva asa...?

Nu am pierdut cazurile elementare...

Si nu reusesc sa gasesc nici greseala...

[Editat de moderator: NU mai posta de 3 ori consecutiv]

[•cos_min]

umpic de cod nu ar strica sau nush explica ce faci exact...altfel nu imi dau seama 

[•jdv]

Cod:

max1:=0;  max2:=0;
    assign(f,'maxsecv.in');  reset(f);
      readln(f,n);
    while not eof(f) do begin
         read(f,n1);
        while n1='0' do read(f,n1);
                       k:=0;
                     while n1='1' do begin
                              inc(k);
                            read(f,n1);
                                      end;
     if k>=max1 then begin
            max2:=max1;
            max1:=k;
                            end
             else if k>max2 then max2:=k;
                       end;
        close(f);

Caut cele mai lungi 2 secv de 1 din citire direct...

Secventa aceasta de cod imi gaseste cele doua maxime...

[•cos_min]

25
1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1

raspunsul corect : 5

[•jdv]

Am verificat testul asta si imi da rezultat corect...
Si toate testele care le-am verificat imi dau rezultat corect...
Nu are cineva vreo idee...? E vreo eroare in cod, sau care e problema aici?

La evaluator primesc incorect la toate testele...unde sa fie greseala?

[•DITzoneC]

Nu prea inteleg ce faci tu pe-acolo si cum ti-a mers pe exemplu din enunt sau pe exemplul de mai sus.

Din cate vad eu acolo n1 e de tip caracter (compari n1='0'). Si tu citest read(f,n1). In fisier intre cifre se afla si spatii pe care tu le citesti tot in acel n1. Deci tu mereu gasesti cea mai lunga secventa de 1 ca fiind de lungime 1(datorita spatiilor). Esti sigur ca nu ai raspuns 2 pe toate testele ?
Ah si inca ceva nu ar trebui sa verifici in interiorul fiecarui while chestia cu eof ?