infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Ianuarie 27, 2007, 18:17:35

Titlul: 307 Maxsecv
Scris de: Adrian Diaconu din Ianuarie 27, 2007, 18:17:35

Aici puteţi discuta despre problema Maxsecv (http://infoarena.ro/problema/maxsecv).

Titlul: Răspuns: 307 Maxsecv
Scris de: David si Goliat din Ianuarie 30, 2007, 21:27:51

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Filip Cristian Buruiana din Ianuarie 30, 2007, 21:34:50

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.

Titlul: Răspuns: 307 Maxsecv
Scris de: Spulber Iosif din Februarie 01, 2007, 11:28:04

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Bondane Cosmin din Februarie 01, 2007, 11:48:10

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Tabara Mihai din Februarie 01, 2007, 13:40:40

Citat din mesajul lui: Spulber Iosif din Februarie 01, 2007, 11:28:04

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

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

:thumbup:

Titlul: Răspuns: 307 Maxsecv
Scris de: Spulber Iosif din Februarie 01, 2007, 13:45:03

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Tabara Mihai din Februarie 01, 2007, 13:48:32

Citat din mesajul lui: Spulber Iosif din Februarie 01, 2007, 13:45:03

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Bondane Cosmin din Februarie 01, 2007, 13:50:46

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Spulber Iosif din Februarie 01, 2007, 13:57:35

Citat din mesajul lui: Bondane Cosmin Cosi din Februarie 01, 2007, 13:50:46

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.

Titlul: Răspuns: 307 Maxsecv
Scris de: Tabara Mihai din Februarie 01, 2007, 14:02:10

Citat din mesajul lui: Spulber Iosif din Februarie 01, 2007, 13:57:35

Citat din mesajul lui: Bondane Cosmin Cosi din Februarie 01, 2007, 13:50:46

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.

Titlul: Răspuns: 307 Maxsecv
Scris de: Airinei Adrian din Februarie 01, 2007, 15:47:53

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Savin Tiberiu din Februarie 01, 2007, 16:04:35

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;

Titlul: Răspuns: 307 Maxsecv
Scris de: Tabara Mihai din Februarie 01, 2007, 18:33:25

Citat din mesajul lui: Airinei Adrian din Februarie 01, 2007, 15:47:53

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 :aha: )
( M-am cam mirat si eu ca a luat 60 cu codul ala :-k ).

Titlul: Răspuns: 307 Maxsecv
Scris de: Petcu Marius din Februarie 07, 2007, 10:14:28

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Jecan Daniel Valerian din Februarie 14, 2007, 21:38:09

Ati putea pune cateva teste pe forum?

Titlul: Răspuns: 307 Maxsecv
Scris de: Savin Tiberiu din Februarie 14, 2007, 21:39:32

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.

Titlul: Răspuns: 307 Maxsecv
Scris de: Jecan Daniel Valerian din Februarie 14, 2007, 21:56:17

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

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Airinei Adrian din Februarie 14, 2007, 22:03:58

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Jecan Daniel Valerian din Februarie 14, 2007, 22:07:43

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

Oare unde e greseala? :-k

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]

Titlul: Răspuns: 307 Maxsecv
Scris de: Bondane Cosmin din Februarie 14, 2007, 22:56:07

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Jecan Daniel Valerian din Februarie 15, 2007, 17:40:18

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Bondane Cosmin din Februarie 15, 2007, 18:16:50

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Jecan Daniel Valerian din Februarie 15, 2007, 21:25:42

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

Titlul: Răspuns: 307 Maxsecv
Scris de: Adrian Diaconu din Februarie 16, 2007, 00:27:59

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 ?

Titlul: Răspuns: 307 Maxsecv
Scris de: Savin Tiberiu din Februarie 16, 2007, 13:21:28

probabil ca el acasa scria testele de intrare fara spatii.

Titlul: Răspuns: 307 Maxsecv
Scris de: Jecan Daniel Valerian din Februarie 16, 2007, 14:12:39

Mersi...problema era cu spatiile...eu nu le-am pus... :)

Acum e perfect... :yahoo:
Multumesc pentru sfaturi...

Titlul: Răspuns: 307 Maxsecv
Scris de: Danci Emanuel Sebastian din Februarie 05, 2008, 16:24:39

am incercat prin 2 meode...si tot mai mult de 40 de pct nu iau

cu

Cod:

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

iau 40 de pct...primele 4 sunt ok iar restu...killed by signal

iar cu

Cod:

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

oare unde gresesc?? :-k

Titlul: Răspuns: 307 Maxsecv
Scris de: Gabriel Bitis din Februarie 05, 2008, 16:47:12

Prima varianta nu mi se pare buna pentru ca nu actualizezi max2 cand k > max1.
A doua varianta pare corecta.
Killed by signal nu cred ca iei din cauza conditiilor, ci pentru ca, probabil accesezi spatiu de memorie nedeclarat, depasesti limita unui vector, etc..

Titlul: Răspuns: 307 Maxsecv
Scris de: Andrici Cezar din Noiembrie 21, 2008, 20:10:51

ce inseamna asta!!! :angry: iau 10 puncte cu un program corect la toate testele din problema si de pe topic am luat corect ce nu merge? ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) ](*,) :angry: :angry: :angry: :angry: :angry: :angry: :readthis: :readthis: :readthis: :readthis:

Titlul: Răspuns: 307 Maxsecv
Scris de: Bogdan-Cristian Tataroiu din Noiembrie 21, 2008, 20:30:41

Nu mai posta asa suparat cu 20 de smileyuri enervante ca nu o sa se grabeasca nimeni sa-ti raspunda. Niciodata nu o sa iei 10 puncte cu o sursa corecta care chiar merge pe teste. Mai bine spui ce faci in programul tau, te uiti in topic sa vezi ce au gresit sau le-a scapat si altora.

M-am uitat pe sursa ta acum. Pe testul

Cod:

14
1 1 1 0 1 1 0 1 0 1 0 1 0 1

iti da 6 in loc de 5.

Verifica-ti sursele inainte sa te enervezi.

Titlul: Răspuns: 307 Maxsecv
Scris de: Andrici Cezar din Noiembrie 21, 2008, 20:44:33

ms de ajutor, eu nu faceam testul in caz ca nu era mai mare decat lungimele maxime la mn continua sa creasca. ACU MULTUMESC MULT MULT MULT. am luat 100 puncte :winner1: :winner1:

Titlul: Răspuns: 307 Maxsecv
Scris de: Mihai Calancea din Februarie 16, 2009, 23:01:39

Ok , va rog clarificati-mi si mie un lucru legat de cerinta. :-k
Pentru
14
1 1 0 0 0 1 1 1 1 0 0 1 1 1
Daca mutam secventa cu indicii(12,14) pe pozitia 3, nu vom obtine ceva de genul:
1 1 1 1 1 1 1 1 1 0 0 0 0 0 ?

Si solutia ar fi 9.

L.E.

Daca am inteles eu ceva gresit, si probabil asta e problema, ma scuzati :D

Ok, m-a luminat cineva.
Ar arata defapt:
1 1 1 1 1 0 0 0 1 1 1 1 0 0

My bad :)

Titlul: Răspuns: 307 Maxsecv
Scris de: A Cosmina - vechi din Octombrie 10, 2009, 18:10:02

Am aplicat aceeasi metoda ca si voi si nu pricep de ce iau incorect pe 9 teste. Pe toate testele date de mine si pe cele puse da voi da bine ...

Cod:

f>>n;
	for (i=0;i<n;++i)
	{
		f>>x;
		if (!x) nr=0;
			else nr++;
		if (nr>max1)
		{
			max2=max1;
			max1=nr;
		}
		else if (nr>max2) max2=nr;
	}
	f.close();
	g<<max1+max2<<"\n";
	g.close();

Stie cineva ce gresesc? :?

Titlul: Răspuns: 307 Maxsecv
Scris de: Andrei Misarca din Octombrie 10, 2009, 18:17:28

Încearcă un test de genu 111101, și vezi cât îți dă.

Titlul: Răspuns: 307 Maxsecv
Scris de: avram florin constantin din Februarie 05, 2010, 23:16:24

eu nu inteleg ce e gresit in rezolvarea mea,calculez la fel un max1 si un max2

Cod:

for(int i=1;i<=n;i++)
{
	scanf("%d" , &x);
	if(x)
		lg++,nr++;
		else
		lg=0;
		if(lg>=max1)
		{
		           max2=max1;
		           max1=lg;
		}
		else
		if(lg>max2)
			max2=lg;
}

am folosit acel nr pentru a verifica daca nu cumva toate elementele sunt 1.

Foloseste tag-ul [ code ] [/ code ] (fara spatii) cand postezi cod.

Titlul: Răspuns: 307 Maxsecv
Scris de: Macarescu Sebastian din Iunie 03, 2010, 10:29:47

O greseala in enunt

Citat

Johnie areun vector binar de N elemente.

Titlul: Răspuns: 307 Maxsecv
Scris de: Ilies Norbert din Februarie 29, 2012, 14:22:57

se poate un test mai... complicat? mie imi da corect pe toate testele din comentarii si totusi iau 10 puncte :-?

Titlul: Răspuns: 307 Maxsecv
Scris de: Barbu Dorel din Septembrie 13, 2013, 19:50:06

Dar pe exemplul al doilea, alegand o secventa formata dintr-un singur 1 si pozitionand-o intre secventa de 1 de lungime 3 si cea de lungime 4, nu se obtine o secventa de lungime 8?

Este aceasta alegere valida?

Titlul: Răspuns: 307 Maxsecv
Scris de: Alexandru Valeanu din Septembrie 13, 2013, 22:06:37

Intre secventa de lungime 3 si cea de 4 ai un zero. Acel zero nu dispare daca inserezi ceva pe langa el...nu poti inlocui o secventa cu o alta daca asta intrebi. Daca nu am raspuns la ce ai intrebat incearca sa mai detaliezi putin intrebarea ca nu cred ca am inteles-o prea bine.