201 Lupul Urias si Rau

[ditzone]

Aici puteţi discuta despre problema Lupul Urias si Rau.

[•raduzer]

Cum se face problema asta???

[•wefgef]

http://infoarena.ro/preoni-2006/finala/solutii

[•raduzer]

merci mult

[•Andreid91]

1   0ms   8kb   OK                                   4
2   0ms   12kb   Killed by signal 11(SIGSEGV).   0
3   0ms   12kb   OK                                   4
4   4ms   12kb   Killed by signal 11(SIGSEGV).   0
5   4ms   12kb   Killed by signal 11(SIGSEGV).   0
6   0ms   12kb   Killed by signal 11(SIGSEGV).   0
7   0ms   8kb   Killed by signal 11(SIGSEGV).   0
8   0ms   12kb   Killed by signal 11(SIGSEGV).   0
9   0ms   12kb   Killed by signal 11(SIGSEGV).   0
10   0ms   8kb   Killed by signal 11(SIGSEGV).   0
11   4ms   8kb   Killed by signal 11(SIGSEGV).   0
12   16ms   504kb   Killed by signal 11(SIGSEGV).   0
13   148ms   1904kb   Killed by signal 11(SIGSEGV).   0
14   104ms   1524kb   Killed by signal 11(SIGSEGV).   0
15   56ms   968kb   Killed by signal 11(SIGSEGV).   0
16   88ms   1364kb   Killed by signal 11(SIGSEGV).   0
17   116ms   1516kb   Killed by signal 11(SIGSEGV).   0
18   124ms   1732kb   Killed by signal 11(SIGSEGV).   0
19   116ms   1600kb   Killed by signal 11(SIGSEGV).   0
20   168ms   1912kb   Killed by signal 11(SIGSEGV).   0
21   144ms   1908kb   Killed by signal 11(SIGSEGV).   0
22   132ms   1988kb   OK                                  4
23   260ms   3452kb   OK                                   4
24   276ms   3452kb   OK                                   4
25   100ms   1516kb   Killed by signal 11(SIGSEGV).   0

Lucrez cu pointeri....si probabil acolo ar putea fi bug-ul. Nu stiu...

[•sigrid]

Poate ca accesezi o zona de memorie inexistenta sau poate ca aloci mai mult decat iti permite memoria s-o faci  .

"11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc."

http://infoarena.ro/documentatie/evaluator

[•devilkind]

@ Ciocan Andrei: Poate ca nu sunt eu persoana cea mai in masura care sa iti spuna cum sa iti identezi sursele, dar sunt destul de sigur ca nu e bine sa lasi cate un rand dupa fiecare instructiune. Am incercat sa ma uit pe ea si cand am vazut ca 70% din sursa sunt linii goale si cat de intinsa e am renuntat. Incearca sa iti scrii sursele in asa fel incat fiecare bucata de cod care face un anumit lucru sa o poti vedea intrun ecran.

[•AnDrEwBoY]

Nu inteleg ce gresesc de primesc doar 8 puncte pe aceasta problema.
Ce fac?
Simplu :
1. Calculez intr`un vector T pasul maxim la care o oaie i poate sa fie luata de lup.
2. Sortez aceste valori
3. Pentru fiecare pas extrag valorile din vectorul sortat cu cei mai multi pasi disponibili si ii adaug intr`un alt vector ce reprezinta un heap
4. La fiecare pas extrag maximul din vector(radacina si o adaug la solutie), elimin valoarea din arbore si reconstruiesc heapul.

Daca cineva are rabdare sa se uite pe sursa raman dator
http://infoarena.ro/job_detail/330588?action=view-source

Cam asa arata HeapDown`ul (sift)

Cod:

void heapDown(long long int v)
{
	long long int w = v*2;
	while(w < k)
	{
		if(w+1 < k && Heap[w+1] > Heap[w]) w++;
		if(Heap[v] >= Heap[w]) return;
		
		Heap[w] ^= Heap[v] ^= Heap[w] ^= Heap[v];
		v = w;
		w *= 2;
	}
}

[•jupanubv92]

  Trimite-mi un PM cu sursa ta si o sa incerc sa vad ce ai gresit ... Acum am scos-o si eu de 100 de p in timp ce citeam mesajul tau mi-am dat seama ce e gresit in sursa mea (pentru cei care iau 88 de p cu incorect pe testele 10,17 si 20 cand extrag maximul din heap sa se intrebe mai intai daca heapul nu este gol (eu din cauza asta luam incorect)) .
  Am problema proaspata in minte si as putea sa te ajut .

[•AnDrEwBoY]

Multumesc de ajutor

[•irene_m]

Nu stiu de ce iau doar 80p.
Retin pentru fiecare timp maxim, indicii pentru care se obtine. Apoi iau fiecare valoare i de la T_max la 1 si adaug in heap toate cantitatile care au timpul maxim = i, dupa care extrag maximul din heap si il adun la solutie.
Mai exista cazuri particulare sau altceva de luat in calcul? 

[•xtreme]

Nu stiu de ce iau doar 80p.
Retin pentru fiecare timp maxim, indicii pentru care se obtine. Apoi iau fiecare valoare i de la T_max la 1 si adaug in heap toate cantitatile care au timpul maxim = i, dupa care extrag maximul din heap si il adun la solutie.
Mai exista cazuri particulare sau altceva de luat in calcul? 

Vezi ca rezultatul trebuie sa fie pe long long int.Eu luam 80 de puncte pentru ca variabila in care tineam rezultatul nu era pe long long int.

[•irene_m]

Asta era!  MulÅ£am frumos !

[•S7012MY]

am 2 probleme : *ce inseamna Killed by signal 6(SIGABRT).
*am rezolvat chiar cu solutia oficiala si nu ma incadrez in timp. Unde gresesc?

[•superman_01]

cat va da pe testul urmator
3 6 2
4 6
4 10
6 8
mie cu sursa de 100 imi da 18 si cred ca raspunsul corect ar fi 16 .

[•repp4radu]

E 18 raspunsul corect. Prima data va fi luata oaia 3(e la distanta 6, deci e ok), iar mai apoi oaia 2(e si ea la distanta 6, deci e ok).

[•superman_01]

a..am  inteles eu gresit o chestie  din enunt   

[•gapdan]

Imi spune si mie cineva care e diferenta intre functiile astea doua de comparare?
struct oaie
{
    int t,l;
}v[NMAX];

bool cmp(oaie p,oaie r)
{
    if (p.t<r.t) return 0;
    return 1;
}//prima

bool cmp(oaie a,oaie b)
{
    return (a.t>b.t);
}// a doua

Folosind prima functie iau 16p(cu TLE pe majoritatea testelor), iar cu cea de a doua iau 100... De ce?  

[•klamathix]

FuncÈ›ia de comparare trebuie să întoarcă True dacă primul element ar trebui să apară înaintea celui de al doilea în sortare. Dacă tu zici că A trebuie să ajunga în faÈ›a lui B atunci când A >= B, se poate întâmpla ca sort-ul să apeleze È™i cmp(A, B) È™i cmp(B, A) È™i să-i dea ambele True, which is a big no-no, din motive destul de evidente  .

[•gapdan]

Interesant, mersi mult

[•japjappedulap]

http://www.infoarena.ro/job_detail/1294725?action=view-source

Rog pe cineva sa se uite peste sursa mea, sa imi spuna de ce iau doar 12 puncte cand orice test facut manual merge.

[•PlayLikeNeverB4]

Cum de nu s-a facut niciun test cu distanta maxima a oilor 2^31 - 1? Majoritatea surselor de 100 iau TLE pe un astfel de test. Mai sunt si multe surse de 100 care ar trebui sa ia WA.

[•klamathix]

Probabil vei întâlni situația asta la foarte multe probleme vechi de pe infoarena/din România. Noi suntem obișnuiți acum cu TC, CF, ACM-ICPC, știm că o greșeală de genul ăsta te poate costa totul și ne e ușor să intrăm pe challenge mode. Impresia mea, posibil să greșesc totuși, e că testarea era mult mai lejeră pe vremuri. Se vede chestia asta și din tradiția cu 10-20 de teste, număr care mie îmi pare acum periculos de mic în 90% din cazuri.