985 Livada

[•wefgef]

Aici puteti discuta despre problema Livada.

[•freak93]

Nu se poate vedea problema " Nu ai permisiuni suficiente pentru a executa aceasta actiune! Te redirectez ..."

[•SpiderMan]

S-a rezolvat 

[•andunhill]

va rog frumos sa ma ajutati putin. Am trimis o sursa si la primele 3 teste imi da OK dar la restul killed by signal 11  . Ma chinui de ea de jumatate de zi si intruna imi da killed by signal 11. Va rog sa ma ajutati daca puteti.

[•palcuiealex]

Ai grija ca P-ul si valorile pe care le citesti pot ajunge la 998.000.000, iar tu nu declari un vector atat de lung [nici n-ai cum 

[•SpiderMan]

Zimi ce declari, cum declari (adica vectorii/matricele si pentru ce le folosesti) ....

[•andunhill]

pai am un vector de frecvente, dar inainte sa-l acutalizez caut minimul de pe un rand si scad din toate soiurile acel min. Dupa care fac actualizarea.
Cod:

Cod:

#include<fstream>
using namespace std;
ifstream f("livada.in"); ofstream g("livada.out");
int i,x[7000000],rd,max2,m,p,n,majoritar,cons,xc,j,min1,aux[7000000]; bool OK;
int citire()
{ min1 = 250000;
 for(i=1;i<=n;i++)
  { f>>x[i]; if(min1>=x[i]) min1=x[i]; }
 return 0;
}
int maj()
{ OK=0; cons=1;
  for(i=1;i<=n;i++)
  { aux[x[i]]++;
if(aux[x[i]]==xc)
OK=1;
for(j=1;j<=n&&OK==1;j++)
if(x[j]==x[j+1])
  cons++;
else
{ if(max2<=cons) max2=cons; cons=1; aux[x[j]]=0;  }
  }
  if(OK==0)
   { for(j=1;j<=n;j++)
aux[x[j]]=0;
   }
return OK&&max2;
}
int scadere()
{ for(i=1;i<=n;i++)
x[i]=x[i]-min1;
 return 0;
}
int main()
{ f>>m>>n>>p;
  xc=n/2+1;
 for(rd=1;rd<=m;rd++)
 { citire(); scadere();
   maj();
   if(OK==1)
majoritar++;
 }
 g<<majoritar<<'\n'<<max2;
 f.close(); g.close();
 return 0;
}

asta e sursa va rog sa  ma iertati daca nu am voie sa  o postez si sa o stergeti.

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•dornescuvlad]

pt inceput, baga long long la 'p', nu cred ca incape in int
edit: si citeste cu scanf("tip",variabila);
citind cu ifstream si ofstream, si eu luam doar 60p, imi dadea tle pe 4 teste

[•andunhill]

pai p practic nici nu-l folosesc

[•dornescuvlad]

nici eu nu-l folosesc, dar daca nu il declari destul de mare....il citesti oricum.... si citeste cu scanf

[•andunhill]

l-am declarat long p; si cu scanf nu stiu sa lucrez. Dar ar trebui sa mearga si la fel 30 pt iau pe ea. Dar nu inteleg, nu depasesc nici o limita la vectori

[•dornescuvlad]

l-am declarat long p; si cu scanf nu stiu sa lucrez. Dar ar trebui sa mearga si la fel 30 pt iau pe ea. Dar nu inteleg, nu depasesc nici o limita la vectori

long long p; eu la citire folosesc doar un vector de DimMax...ar trebui sa fie de ajuns

[•andunhill]

am pus si long long p si tot nu merge 

[•freak93]

Vezi k tu initializezi minimul cu 250.000, numerele pot fi toate mai mari decat 250.000 , de exemplu din intervalul 70.000.000 si 95.000.000.
Astfel tu din toate numerle scazi 250.000(min1 la tine ramane nemodificat) si vei accesa la un moment dat aux[70.000.000] care nu exista.
 Iti recomand sa initializezi minimul daca e int cu

Cod:

mint=(1<<31)-1;

sau daca e long long cu

Cod:

mint=(1LL<<63)-1;

L.E: @Dornescu Vlad, eu am pus totul int, si citesc cu streamuri si am sub 0.5 pe toate testele.

[•andunhill]

am incercat initializarea asa si imi da eroare.

[•andunhill]

am facut initializarea cum ai zis tu si tot 30 de pt primesc. La restul primesc Killed by Signall 11

[•andrei.finaru]

Adi, vezi ca nu toata lumea stie chestiile alea pe biti pe care le sugerezi. Pentru cei care nu sunt la info intensiv, el sugereaza valoarea maxima care incape in tipul respectiv de variabile. Se mai poate initializa cu 2147483647 (valoarea maxima pe care o poate lua un int) sau cu INT_MAX din biblioteca limits.h:
http://en.wikipedia.org/wiki/Limits.h
Daca ai KBS 11 vezi exact cum merg pointerii (i-ul,j-ul si ce mai ai pe acolo) in vectori . Si nu stiu daca ai voie sa declari 2 vectori de 7 000 000 sau cat sunt acolo, si mai ales amandoi de int. Incearca sa-l faci pe unul de charuri si sa-i declari doar de 250001

[•andunhill]

problema nu e de p ci ca imi da Killed by Signall fara motiv. La primele 3 merge iar la restul killed by signal 11. Puteti sa imi dati un test cu numere mari sa vad care e problema?
uitati borderoul http://infoarena.ro/job_detail/414800

[•freak93]

Am inlocuit

Cod:

min1=250000;

cu

Cod:

min1=(1<<31)-1;

si acum nu am primit decat cateva TLE si un Wrong answer. Vezi ca in functia maj ai un for in altul, complexitate O(n^2). Incearca sa reduci chestia asta si vei lua 100.
(1<<x) este egal cu 2^x, si fiindca 2³¹ iese din int, mai scadem 1.
Sper sa te ajute!:D

L.E: Am scos si cate un zero de la vectorii tai, ca nu intra in memorie.

[•andunhill]

ok dar forul ala nu cred ca explica killed by signal 11. Cred ca ar trebui sa imi dea TLE

[•andrei.finaru]

Un KBS nu apare fara motiv niciodata. Vezi ca trebuie sa mai pui la sfarsit inca un test pt. max2. Si daca am priceput bine ce face secventa aia, ar trebui sa scoti if-ul din ea:

Cod:

if(OK==0)
   { for(j=1;j<=n;j++)
aux[x[j]]=0;
   }

[•dornescuvlad]

@ Adrian
Inseamna ca ai o solutie mult mai buna decat a mea....Multi au luat mai putine pct am vazut, pt ca au citit cu ifstream

[•freak93]

Intocmai, nu forul a facut sa iei KBS si faptul ca ai initializat minimul gresit.
Initializeaza-l cu 2.000.000.000 daca ti se pare mai usor si vei vedea ca vei scapa de KBS.
Si mai trebuie sa faci aux de lungime 250.001(de la 0 la 250.000) si x de 700.001(de la 0 la 700.000).
Am incercat eu cu sursa ta si mi-a dat 54 de puncte
http://infoarena.ro/job_detail/414802

[•andrei.finaru]

Dar aici, ce pot sa fac? Am numa 4 puncte si ma dispera pt ca nu-i gasesc nici o hiba:(

Cod:

#include<fstream.h>
ifstream f("livada.in");
ofstream g("livada.out");
int v[250001];
char pomi[250001],t,t1;
int main()
{int nrp,n,m,i,j,maj,a,k,c,max,maxc;
long long p;
nrp=i=j=k=c=max=maxc=0;
f>>m>>n>>p;
maj=n/2+1;
for(i=1;i<=m;i++)
{maxc=0;
for(j=1;j<=n;j++)
{f>>t;
a=0;
for(k=1;k<=nrp;k++)
if(pomi[k]==t) {v[k]++;a=1;}
if(a==0) {nrp++; pomi[nrp]=t; v[nrp]=1;}
if(t==t1) maxc++;
else {if(maxc>max) max=maxc;
maxc=1;}
t1=t;
}
t1='0';
for(k=1;k<=nrp;k++) {if(v[k]>=maj) c++; v[k]=0;}
nrp=0;}
if(maxc>max) max=maxc;
g<<c<<'\n'<<max<<'\n';
f.close(); g.close();
return 0;
}

Daca e nevoie,il scot dar chiar sunt curios unde nu merge.

[•freak93]

Vezi ca daca cel mai lung sir de acelasi numar e fix la sfarsit programul tau nu-l gaseste, pentru ca nu merge in n+1 sa verifice cu n. Iti sugerez sa mai faci o verificare dupa forul de la 1 la n.
 Alta problema e ca trebuie sa reinitializezi t1=0 cand incepi fiecare din cei m pasi altfel ai putea compara cu ultimul element de pe linia anterioara ceea ce nu e corect.
A treia problema e faptul ca cei 250.000 de pomi ai tai sunt intr-un char. Tu acolo stochezi inaltimea lor, care depaseste cu mult 127 care e limita la char. Iti sugerez sa treci in int.
Sper sa te ajute.