860 Bere

[•DITzoneC]

Aici puteţi discuta despre problema Bere.

[•andrici_cezar]

Am facut problema am luat 60 pct... Am incercat alta metoda tot 60 pct am luat... Am incercat o alte idee care zic eu ca e mai buna, dar imi da Killed by signal 9 ce inseamna? si de la ce vine?

[•toni2007]

Iei SIGKILL pentru ca declari prea multa memorie. Nu iti intra o matrice de 15000 pe 15000 de long long (ai 16 mega).

[•andrici_cezar]

Ms

[•miculprogramator]

Nu-mi dau seama cum sa-l fac de 60,iau numai 30 de pct pe el... Apare killed by signal 11,stiu ca am probleme cu memoria.

Nu stiu insa cum pot remedia.

Si inca o intrebare: Daca iau 30 de puncte inseamna ca algoritmul este corect si am probleme doar la date,sau algoritmul poate fi si incorect? 

[•klamathix]

Poate fi incorect , dar in cazul de fata nu e destul de rapid.

Din cate tin minte pentru 60p sortezi query-urile dupa k  si pentru un k(i) iterezi o singura data pentru toate cererile asociate lui .
Mie mi se pare cam aiurea . E ok ca idee de optimizare minora, dar ai mai multe de invatat din solutia de 100p . As trece direct la ea.

[•pauldb]

Si inca o intrebare: Daca iau 30 de puncte inseamna ca algoritmul este corect si am probleme doar la date,sau algoritmul poate fi si incorect? 

Uneori nu e suficient sa gasesti un algoritm corect, ci trebuie sa fie si eficient din punctul de vedere al timpului pe care il consuma pana gaseste raspunsul corect. Din acest motiv, fiecare problema are o limita de timp. Cand programul tau depaseste aceasta limita, in borderoul de evaluare va aparea mesajul "Time limit exceeded" (cum e cazul tau acum).

Pentru a intelege mai mult cand un algoritm iti va intra in timp si cand nu, ar trebui sa citesti despre complexitate timp. Asta masoara numarul de operatii pe care il executa programul tau. In principiu, poti estima ca evaluatorul infoarena poate executa aproximativ 50 000 000 de operatii pe secunda. Din pacate articolul de pe wikipedia e cam stufos si cam dificil. Daca stie cineva un loc unde acest subiect este tratat mai pentru incepatori, ar fi bine sa il posteze.

[•miculprogramator]

Va multumesc amandurora pentru feedback. 

@klamathix, vreau sa o iau pe pasi cum se spune... "Nu trebuie sa vezi de la inceput toata scara.Doar paseste..."

@d. Paul, acum citesc articolul dat de tine. "Time limit exceeded" apare pe ultima sursa in care am incercat eu ceva la dimensiunile vectorilor, la sursele de 30 pct aveam killed by signal 11.
Ar merge sa discutam subiectul la sectiunea "Informatica", sau in cel mai drastic caz la "Offtopic".

[•pauldb]

Asa e, nu suntem tocmai la subiect. Acum am cautat pe forum si am gasit ceva topicuri unde se discuta asta. Incearca sa le citesti si poate mai prinzi ceva. Daca ai intrebari, poti sa le pui acolo.

[•Leocrux]

Inainte de toate, Salut! Sunt nou pe infoarena si sper sa ne intelegem bine:)
Dupa 2 tentative, am obtinut la a3a sursa trimisa 30 de puncte   , mai departe depasesc timpul de executie
Daca nu adorm, citesc articolul dat de Paul.

[•Addy.]

Nu se (mai) pot trimite solutii la aceasta problema.

de ce?

[•toni2007]

Nu se (mai) pot trimite solutii la aceasta problema.

de ce?

Se poate. Poate nu erai tu logat.

[•Bunicool]

M-am uitat la rezolvarea de 100 de puncte si mi se pare mult mai grea si mai time-consuming decat cea de 30 care pare mai scurta.
O seara la un pahar de bere n-ar trebui sa fie asa de complicata.

[•blasterz]

Deobicei complexitatea algoritmului e invers proportionala cu marimea sursei (adica cu cat e mai rapid algoritmul, cu atat e mai mare sursa).
... evident...depinde de caz

[•SpiderMan]

Nu totdeauna, uneori o sursa mica poate face furori 

[•wefgef]

Deci putem trage concluzia că mărimea sursei nu contează...

Hai să nu ne îndepărtăm prea mult de la subiect!

[•andunhill]

Va rog frumos puteti sa ma ajutati si pe mine. http://infoarena.ro/job_detail/429277 asta e borderoul. Nu inteleg de ce imi da WA.
Cod:

Cod:

void cinste(int i)
{ beri=0; long urm=0,j; bool gas=0;
 if(c[a[i][1]]>=a[i][2]) { g<<0<<'\n'; gas=0; }
  else { a[i][2]-=c[a[i][1]]; beri++; gas=1; }
 if(gas==1) 
 { j=a[i][1];
 if(j==n) urm=1; else urm=j+1;
  while(a[i][2]>=0&&a[i][2]>=c[urm]&&urm!=j)
  { a[i][2]-=c[urm]; beri++; urm++;
   if(urm==n+1) urm=1;
  }
  g<<beri<<'\n';
 }
}

Va rog sa ma scuzati daca sursa e prea explicita si puteti sa o stergeti.

[•toni2007]

Problema se face cu cautare binara.

[•andunhill]

bun dar de ce imi da mie gresit? Ca doar algoritmul merge perfect. Pur si simplu nu inteleg de ce imi da WA.

Edit:

Cod:

void iterare(int i)
{ s=0;
	s+=c[pb[i][1]]; long j,urm; beri=0; 
  j=pb[i][1];
  if(s>pb[i][2]) g<<0<<'\n';
  else
  { if(j==n) urm=1;
  else urm=j+1;
	beri=1;
	while(urm!=j&&s<=pb[i][2])
	{ s=s+c[urm]; 
	urm++; 
    if(urm==n+1) 
	urm=1; 
	beri++;
	if(s+c[urm]>pb[i][2]) break;
	else
	 if(urm==j-1&&pb[i][2]>s) { beri=n; break; }
	}
  g<<beri<<'\n';
  }
}

Va rog sa ma scuzati din nou ca am postat o sursa de 10 pt dar nu stiu ce sa mai fac. In primul caz am scazut din banii prietenului pana cand ajungea din nou la el sau pana cand i se terminau.
In a doua sursa am adunat costurile berilor pana cand imi depasea banii prietenului respectiv sau pana cand ajunge din nou la el. Daca testele sunt aceleasi de la Oni inseamna ca s-ar putea sa fie in neregula. Ca eu am luat testele de la ONI si imi da corect.

Editat de moderator : Nu mai posta consecutiv, editeaza-ti mesajele anterioare.

[•stocarul]

Dacă zici ca pe toate testele de la ONI îți dă bine iar aici primești doar 10 pct (cu WA), cel mai probabil este de la comanda de compilare.
Compilează-ți sursa cu comenzile folosite de evaluatorul InfoArena, și testează din nou pe testele de la ONI:
http://infoarena.ro/documentatie/evaluator

Spor 

[•andunhill]

pai ca sa vad ce imi da gresit mi-am facut un eval propriu care ia outul si ok si citesc 1 nr din fiecare si le compar daca gasesc 2 elemente diferite afisez linia. Problema ca inainte sa le folosesc la evaluator fisierele rezultate din rularea sursei bere sunt bune si cand le bag imi afiseaza mii de linii gresite. Si cand le verif vad ca sunt modificate. Dar nu inteleg de ce nu imi merge algoritmul. Va rog ajutor

[•mateisirghe]

e cam imposibile     

[•andreiPC]

Problema ok.Bravo,dar este super grea.
Mai incerc.......................................