651 Carnati

[•DITzoneC]

Aici puteţi discuta despre problema Carnati.

[•Florian]

Am o rezolvare ca in articol. Pt fiecare client i fac o dinamica ca sa aflu profitul maxim in caz ca aleg pretul produsului egal cu P. Cu toate acestea, iau 90 de pcte cu un wa pe testul 9. Care sa fie problema?

[•anna_bozianu]

Si la mine tot testul 9 pica. Am testat si daca profitul scos de algoritm e negativ situatie in care afisez 0 (adica magazinul ramane inchis). Se pare ca Gigel iese oricum in profit. Din marimea rezultatului nu cred sa fie problema ca si daca toti clientii cumpara la pret maxim si angajatul primeste minim profitul tot nu are cum sa depaseasca 2000000000 deci intra pe long. Ma alatur si eu intrebarii. Ce are testul 9 de nu iese?

[•filipb]

M-am uitat pe testul 9 si mi se pare ca e generat random . In plus, raspunsul e pozitiv si pana in 20 de milioane, deci incape in 32 de biti.

[•cos_min]

Cod:

Relatia de recurenta se observa usor A[i]= max(A[i]-1-(T[i]-T[i-1])*C+G,G-C), unde G este X pentru X ≤ Pi sau 0 in caz contrar

Relatia de recurenta pentru X > Pi nu ar trebui sa fie de genul:

Cod:

A[i] = max(0,A[i]-1-(T[i]-T[i-1])*C );

[•anna_bozianu]

Nu cred ca ar fi o problema. Oricum un astfel de A [ i ] poate influenta solutia problemei numai daca A [ i ] =A[i-1]-(T [ i ]-T[i-1])*C > 0 dupa principiul ca daca la un moment dat profitul e negativ mai bine inchid pravalia . Sau gandind altfel pentru un pret fixat clientii cu pret mic decat pretul fixat pot fi ignorati

[•Florian]

Poate ca e destul de explicit codul urmator, dar din moment ce exista si solutie oficiala, nu cred ca e vreo problema. In caz contrar, rog un moderator sa il stearga.

Cod:

 for(i=1;i<=n;++i)  
      {  
      old=0;  
      for(j=1;j<=n;++j)  
        {  
   
        if(a[ j ].p>=a[ i ].p) G=a[ i ].p;  
   
        else G=0;  
   
        news=old-(a[ j ].t-a[ j-1 ].t)*c+G;  
   
        if(news<G-c) news=G-c;  
   
        if(news>max) max=news;  
          
        old=news;  
       }  
   
      }  

-in a [ i ] . t am timpul pt al i-lea client [echivalentul lui T [ i ] dupa solutie...]
-in a [ i ]. p am pretul dispus sa`l plateasca clientul i [ echivalentul lui P [ i ] ]
-in news am echivalentul lui A [ i ], iar in old am echivalentul lui A [ i-1 ]. [am retinut doar ultimile doua valori pt dinamica cu A [] - ul  ]
-in max am solutia.

Problema e ca iau un WA pe testul numarul 9, si as vrea, daca are cineva chef si putin timp liber, sa se uite putin peste, sa imi zica si mie ce e gresit. Ca nu prea ma prind... dinamica mi se pare corecta...la fel si solutia oficiala...   

[•Robytzza]

are ceva special testul 8 si 5 .. ca vad ca nu sunt singurul care greseste pe ele ..  

[•tm_radu]

anna_bozianu : mie mi-a trecut testul 9 in momentul in care am zis ca a[0] = t[0] = -10

[•ciprianf]

Eu am rezolvat problema cu 2 foruri ...destul de simpla ideea , dar iau 80 de pcte cu 2 *wa. Am luat un for i=1,n presupunand ca pretul pus de vanzator este pret(i) ; dupa am luat for j=1,n si am facut subsecventa de suma maxima( neuitand sa-l platesc si pe vanzator) ....mai exact

Cod:

for(i=1;i<=n;i++){
		s=0;
		poz=1;
		if(v[i].b-c>max) max=v[i].b-c;
		for(j=1;j<=n;j++){
			if(v[j].b>=v[i].b) s+=v[i].b;
			if(s-( v[j].a - v[poz].a + 1)*c>max) 
				max=s-(v[j].a-v[poz].a+1)*c;
			if(s-(v[j].a-v[poz].a+1)*c<0) { s=0; poz=j+1; }
		}
	}

imi poate spune si mie cineva unde am gresit? sau sa-mi dea un exemplu pe care nu functioneaza acest algoritm? multumesc anticipat

[•filipb]

TLE inseamna time limit exceeded, nu inseamna neaparat ca raspunsurile tale sunt gresite. Trebuie sa cauti o solutie mai rapida.

[•ciprianf]

pf...am scris gresit. nu iau 2 tle, iau 2 wa:D

Hai mai chiar nu stie nimeni?

LE: M-am uitat si la solutiile oficiale, dar nu am inteles ce sa fac cu acel vector H si ce intrebuintare are

LLE: Never mind! am rezolvat-o

[•SebiSebi]

Imi da Incorect pe testul 5. Nu am nici o idee, va rog ajutati-ma cu ceva . Multumesc anticipat!

Este ceva special la testul 5?