infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Martie 09, 2010, 13:32:41



Titlul: 985 Livada
Scris de: Andrei Grigorean din Martie 09, 2010, 13:32:41
Aici puteti discuta despre problema Livada (http://infoarena.ro/problema/livada).


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 09, 2010, 14:02:06
Nu se poate vedea problema " Nu ai permisiuni suficiente pentru a executa aceasta actiune! Te redirectez ..."


Titlul: Răspuns: 985 Livada
Scris de: Simoiu Robert din Martie 09, 2010, 16:31:34
S-a rezolvat  8)


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 00:48:02
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.


Titlul: Răspuns: 985 Livada
Scris de: Alex Palcuie din Martie 10, 2010, 01:20:56
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  :-k


Titlul: Răspuns: 985 Livada
Scris de: Simoiu Robert din Martie 10, 2010, 09:20:59
Zimi ce declari, cum declari (adica vectorii/matricele si pentru ce le folosesti) ....


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 15:06:13
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.


Titlul: Răspuns: 985 Livada
Scris de: Vlad Eugen Dornescu din Martie 10, 2010, 15:07:14
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 :winner2:


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 15:08:08
pai p practic nici nu-l folosesc


Titlul: Răspuns: 985 Livada
Scris de: Vlad Eugen Dornescu din Martie 10, 2010, 15:09:25
nici eu nu-l folosesc, dar daca nu il declari destul de mare....il citesti oricum.... si citeste cu scanf


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 15:11:42
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


Titlul: Răspuns: 985 Livada
Scris de: Vlad Eugen Dornescu din Martie 10, 2010, 15:17:44
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


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 15:22:53
am pus si long long p si tot nu merge  ](*,)


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 10, 2010, 15:37:40
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.


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 15:48:01
am incercat initializarea asa si imi da eroare.


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 15:52:38
am facut initializarea cum ai zis tu si tot 30 de pt primesc. La restul primesc Killed by Signall 11


Titlul: Răspuns: 985 Livada
Scris de: Finaru Andrei Emanuel din Martie 10, 2010, 15:59:49
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 (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


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 16:03:20
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


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 10, 2010, 16:11:50
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 2x, si fiindca 231 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.


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 16:14:16
ok dar forul ala nu cred ca explica killed by signal 11. Cred ca ar trebui sa imi dea TLE


Titlul: Răspuns: 985 Livada
Scris de: Finaru Andrei Emanuel din Martie 10, 2010, 16:17:36
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;
   }


Titlul: Răspuns: 985 Livada
Scris de: Vlad Eugen Dornescu din Martie 10, 2010, 16:18:57
@ 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 :winner2:


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 10, 2010, 16:22:26
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 (http://infoarena.ro/job_detail/414802)


Titlul: Răspuns: 985 Livada
Scris de: Finaru Andrei Emanuel din Martie 10, 2010, 16:32:19
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.


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 10, 2010, 17:02:31
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. :D


Titlul: Răspuns: 985 Livada
Scris de: Macarescu Sebastian din Martie 10, 2010, 21:07:37
Nu va mai chinuiti sa imi evaluati sursa. Am luat 100 pt  :winner1: . Am descoperit greseala.


Titlul: Răspuns: 985 Livada
Scris de: Bagu Alexandru din Martie 11, 2010, 09:57:02
De ce iau doar 90puncte? 1 test = TLE

Cod:
#include<stdio.h>
#include<map>
using namespace std;
int main()
{
    FILE *fin=fopen("livada.in","r");
    FILE *fout=fopen("livada.out","w");
    int m,n,p;
    fscanf(fin,"%d %d %d",&m,&n,&p);
    int mcon = 0, con = 0, last = -1, msoi = 0;
    int need = n / 2 + 1;
    for(int c = 0; c < m; c++)
    {
        last = -1;
        con = 0;
        map<int, int> v;
        int more = 1;
        for(int a = 0; a < n; a++)
        {
            int soi;
            fscanf(fin, "%d", &soi);
            if(more)
            {
                if(v.count(soi) == 0)
                {
                    v.insert(pair<int,int>(soi,1));
                }
                else
                {
                    v[soi] = v[soi] + 1;
                    if(v[soi] >= need)
                    {
                        more = 0;
                        msoi++;
                    }
                }
            }
            if(last != -1 && last == soi)
            {
                con++;
                if(con > mcon)
                    mcon = con;
            }
            else
                con = 1;
            last = soi;
        }
    }
    fprintf(fout,"%d\n%d",msoi,mcon);
    fclose(fin);
    fclose(fout);
    return 0;
}



Titlul: Răspuns: 985 Livada
Scris de: Simoiu Robert din Martie 11, 2010, 10:07:21
Ori nu e eficient algoritmul, ori ai o bucla infinita, incearca testele OJI.


Titlul: Răspuns: 985 Livada
Scris de: Andrei Misarca din Martie 11, 2010, 13:08:40
Nu am citit foarte atent sursa, dar am văzut că folosești la un moment dat un map. Ai grijă că această structură este un mare consumator de timp și memorie, iar dacă o poți înlocui cu altceva, nu ezita. :)


Titlul: Răspuns: 985 Livada
Scris de: Tataranu Vlad din Martie 11, 2010, 19:03:04
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 2x, si fiindca 231 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.
Ai grija ca, dupa cum ai zis si tu 231 iese din int, dar expresia e evaluata tot pe int.
Castarea la unsigned ar rezolva problema.
Cod:
((unsigned int)1 << 31)-1


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 12, 2010, 09:06:29
@Vlad Chiar daca (1<<31) iese din int el asa va arata in baza 2 100....00(31 zerouri) care este perceput ca -231. Imediat ce scazi 1, iar depeseste limita int(de data asta cea inferioara) si ia valoare pe care o vreau.A stfel ca la (1<<31) adunam -1
(1<<31):10000000000000000000000000000000
(-1):      11111111111111111111111111111111
rezultat: 01111111111111111111111111111111

Observam ca primul bit(cel de semn) a fost adunat ca si ceilalti biti si s-a redus. Vreau sa marchez faptul ca indiferent cat de mari sunt numerele cu care faci operatii pe int, ele se vor executa ca si celelalte doar ca nu se vor tine cont de ceilalti biti.
Aceste apelari nu sunt gresite(eu sincer le folosesc mereu cand nu trebuie sa adun maximul undeva).
Ex: MAXT=(1<<31)-1;
     MINT=MAXT+1;(ne intoarcem inapoi in -231)
La MINT am atribuit valoarea asa fiindca nu imi da mereu cum trebuie daca pun MINT=(1<<31);


Titlul: Răspuns: 985 Livada
Scris de: Bagu Alexandru din Martie 12, 2010, 10:10:40
Citat
Ori nu e eficient algoritmul, ori ai o bucla infinita, incearca testele OJI.
Apoi, cu algoritmu meu iau 100 de pct pe testele de la OJI...

Citat
Nu am citit foarte atent sursa, dar am văzut că folosești la un moment dat un map. Ai grijă că această structură este un mare consumator de timp și memorie, iar dacă o poți înlocui cu altceva, nu ezita.

Ai vreo idee cu ce as putea inlocui map-u?


Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Martie 12, 2010, 10:56:27
Mai complicat: ai putea inlocui map-ul cu un hash(daca nu stii ce inseamna iti sugerez sa rezolvi problema hashuri de la arhiva educationala) sau mult mai simplu sa te folosesti de faptul ca diferenta dintre cel mai mare si cel mai mic de pe un rand este de 250.000. Daca stii count sort il poti modifica un pic(scazand din toate numerele minimul) si astfel ai complexitate O(n*m).
Map-ul are complexitate logaritmica asa ca e de preferat sa nu o folosesti in situatii in care poti folosi altceva mai rapid.


Titlul: Răspuns: 985 Livada
Scris de: A Cosmina - vechi din Martie 14, 2010, 16:10:32
Primesc o eroare pe care n-am mai intalnit-o pana acum Killed by signal 6(SIGABRT) - http://infoarena.ro/job_detail/417582 . Ma asteptam sa ia in jur de 40 de puncte, sau mai putin (rezolv numai prima cerinta deocamdata).

E vreo problema la mine sau are ceva evaluatorul ?  :?


Titlul: Răspuns: 985 Livada
Scris de: Cosmin-Mihai Tutunaru din Martie 14, 2010, 16:35:34
Problema e la tine.
Din câte știu, e cauzată de împărtiri la 0....dar nu sunt sigur.
Poți căuta pe forum/goagăl.


Titlul: Răspuns: 985 Livada
Scris de: A Cosmina - vechi din Martie 14, 2010, 16:43:21
Nu era de la impartirea cu 0. Faceam de doua ori fclose(g); , imi cer scuze ca am postat aiurea.  :oops:


Titlul: Răspuns: 985 Livada
Scris de: Simoiu Robert din Iunie 22, 2010, 17:20:59
Se poate totusi lua in Pascal 100 pct .... fara citire parsata ( nu am incercat inca ) ?

[LE] Iau 80 cu citire parsata, cu un TLE si MLE, fara iau 3 TLE, adica 70 pct.
[LE2] Am luat 100, am facut citirea parsata pe bucati ...


Titlul: Răspuns: 985 Livada
Scris de: Preda Rares Mihai din Februarie 06, 2011, 16:46:12
Ce poate sa aiba tesul 9 ca iau TLE si pe restu imi intra frumos de tot in timp..maxim 280 ms si limita e la 0.6 s ?
http://infoarena.ro/job_detail/529958

testele sunt aceleasi ca si cele de la OJI ?


Titlul: Răspuns: 985 Livada
Scris de: Mihai Visuian din Ianuarie 17, 2012, 16:11:56
Incearca sa mai optimizezi putin algoritmul.
Complexitatea e O(n).


Titlul: Răspuns: 985 Livada
Scris de: Petru Trimbitas din Ianuarie 17, 2012, 16:53:57
Ce poate sa aiba tesul 9 ca iau TLE si pe restu imi intra frumos de tot in timp..maxim 280 ms si limita e la 0.6 s ?
http://infoarena.ro/job_detail/529958

testele sunt aceleasi ca si cele de la OJI ?

Limitele sunt super lejere, nu inteleg cum poti lua tle. O solutie cu sort din stl ia 100. Iti recomand sa citesti articolul asta http://infoarena.ro/problema-majoritatii-votului , e foarte bine scris si interesant.


Titlul: Răspuns: 985 Livada
Scris de: Mihai Calancea din Ianuarie 17, 2012, 19:49:02
Si voi doi aveti un pic de TLE. Omul n-a mai intrat pe forum de pe 27 mai.


Titlul: Răspuns: 985 Livada
Scris de: FMI Razvan Birisan din Iunie 27, 2012, 09:43:19
Mai sunt limitele de timp așa lejere? :-'


Titlul: Răspuns: 985 Livada
Scris de: Stefan Eniceicu din Iunie 27, 2012, 12:48:16
Limita e ok, depinde cu ce citesti probabil...(si fara cin/cout ca is de 2 ori mai lente :thumbdown:)

LE: si eu folosesc tot fstreamuri pt citire, dar din cate am auzit cin/cout sunt slabute...(cred ca wef a comentat asta la o problema mai demult)


Titlul: Răspuns: 985 Livada
Scris de: FMI Razvan Birisan din Iunie 27, 2012, 18:56:09
De acum am să folosesc numai scanf/printf. :shock:



Titlul: Răspuns: 985 Livada
Scris de: Adrian Budau din Iunie 27, 2012, 23:15:30
Nu sunt de 2 ori mai lente. Eu sincer folosesc ifstream/ofstream si imi merge foarte bine(foarte rar chiar mai repede). Majoritatea problemelor sunt facute astfel incat sa intre citirea oricum ar fi ea. La asta de exemplu am citit/afisat cu streamuri.

L.E: Vad ca tu folosesti freopen cu cin/cout. De la o anumita versiune de gcc/g++ s-a implementat o chestie numita sync_with_stdin care strica aceasta pereche. Folosesti fie streamuri, fie freopen + scanf/print, fie cauti pe net cum sa dezactivezi sync_with_stdin



Titlul: Răspuns: 985 Livada
Scris de: FMI Razvan Birisan din Iunie 28, 2012, 09:48:55
Mulțumesc pentru sfat. :ok: