Centrul de greutate are ca, coordonate x=media aritmetica a x-ilor si y=media aritmetica a y-ilor

Salut.Am facut si eu cautare binara+verificare prin programare dinamica la problema asta.Iau 60 pct cu wa.As avea cateva intrebari daca binevoieste cineva sa-mi raspunda.
1)Orice solutie se considera a fi corecta?
2)Daca s-a asigurat nr minim de L de litri de lapte de tip A si B pt un anumit timp T si T e minim cu aceasta proprietate, se prespune ca prietenii lui Haralambie trebuie sa bea in continuare lapte pe tot parcursul lui T sau pot sa nu bea deloc?
3)eventuale alte cazuri particulare
Mersi anticipat! 

Am luat 100 pct fara normalizare. Eu afisez cost[TMAX], TMAX=timpul maxim.Avand in vedere ca programul ia 100 pct, inseamna ca TMAX nu depaseste niciodata 2^17(atat am declarat eu vectorul).Cred ca ar trebui refacute o parte din teste 

Testele la problema asta sunt prost date. Am scos 100 pct : http://infoarena.ro/job_detail/353044 cu o sursa in care aveam complexitate O(n*m*k) cu cate un bellman ford pt fiecare oras de tip fortareata.  Ar fi bine daca ar putea cineva sa le mai schimbe.

Salut.Am o nelamurire la problema asta.Eu m-am gandit cam asa:
E clar ca daca |f(1)| + |f(2)| + .. |f(n)| =S exista fix S din cele n valori din domeniu egale cu 1 sau -1 si mai sunt deci n-S valori de 0.Ca functiile cautate sa fie sigur surjective Aleg cate o valoare de 1 si de -1(e garantat faptul ca vor fi zerouri).Sunt n*(n-1)posibilitati de alegere a celor 2 valori de 1 si -1.Pe urma au mai ramas S-2 valori de 1 sau -1 de pus.Sunt comb[n-2][S-2] metode de a alege o configuratie de S-2 valori din n-2 posibile.Pentru fiecare configuratie sunt 2^(S-2) metode de a alege 1 sau -1.
Ca urmare => rezultatul cautat ar trebui sa fie : n*(n-1)*comb[n-2][S-2]*2^(S-2) ,avand grija la operatiile in modul. Pe exemplu n=5,S=3 => inlocuind: 5*4*comb[3][1]*2^1=5*4*3*2=120 ,nu 60. Poate cineva sa ma lamureasca unde gresesc in rationament? 

Salut. Am incercat si eu problema asta si nu inteleg de ce iau killed by signal 11 pe multe teste. Eu fac ciurul pt patratele numerelor prime pana in sqrt(b) si pe urma impart intervalul [a,b] in intervale de maxim 10^6 numere care reunite dau intervalul [a,b](cv de genu: [a,b]=[a,a+10^6-1] reunit cu [a+10^6, a+2*10^6-1] reunit cu... [a+k*10^6,b] si pt fiecare ciur pe un interval mic folosesc un vector de char de dimensiune 2^20 (>10^6) Ma lamureste cineva va rog ce gresesc? Mersi anticipat!

Later edit:Tot ce greseam era o singura linie: poz2=(poz/nr[j]+1)*nr[j];  poz2 putea depasi int.Las comentariul in caz ca mai are cineva vreodata problema asta.

Salut! Am incercat si eu sa fac problema cu dinamica si as vrea daca se poate sa-mi spuna cineva ce gresesc in rationament. Fac v[j]=cate nr de i cifre au ultimele j cifre consecutive de 0. Cum pe prima pozitie nu se poate pune 0,v[1][0]=(b-1).
Am observat recurenta: v[j]=(v[i-1][0]+v[i-1][1]+...+v[i-1][b-1])*(b-1),daca j=0 si v[j]=v[i-1][j-1] altfel.
Raspunsul pt pct.a) este: v[l][0]+...+v[l][p] ,iar pt pct b) v[l][q]+...+v[l][l-1]. Mersi anticipat 

[Ce nu inteleg e de ce merge prima varianta de aflare a lui poz,in timp ce a 2-a merge]

poz l-am initializat cu 0 si e de tip int.
Problema nu e ce se intampla mai incolo cu 1<<poz (desi oricum poz nu ajunge sa depaseasca 30 niciodata din cauza restrictiilor : x<=15000).Ce nu inteleg e de ce merge prima varianta de aflare a lui poz,in timp ce a 2-a merge.

Ma lamureste si pe mine cineva dc astea 2 fragmente de cod pentru aflarea pozitiei celui mai nesemnificativ bit de 1 nu sunt echilvalente:
1)

Cod:

		while (x%2==0)
		{
			poz++;
			x/=2;
		}

2)

Cod:

while(!(x&(1<<poz))) 
	 poz++; 

Mersi anticipat!

[editat] foloseste tag-ul "code" cand postezi cod pe forum

Poate cineva va rog sa se uite pe sursa mea?
http://infoarena.ro/job_detail/330398 Am citit articolul despre AIB si am facut exact ce spunea acolo.Exemplul merge,dar iau incorect pe toate testele
Mersi anticipat! 

Poti sa fii putin mai explicit? Uite cum fac eu citirea caracter cu caracter:

Cod:

while (scanf("%c",&x)!=EOF)
	{
		if (r==8)
		{
			caractere++;
			rezolva();
			r=0;
		}
		if ((int)x>=48 && (int)x<=49)
		{
			v[++r]=x-'0';
			continue;
		}
		else
			continue;
	}
	if (r)
	{
		caractere++;
		rezolva();
	}

Foloseste tag-ul [ code ] cand postezi cod.

Salut.Am incercat sa fac si eu problema asta,dar iau incorect pe 4 teste.Testele sunt cele de la oji?Am incercat toate testele de la oji si imi merg.Am incercat sa fac citirea si cu fgets si caracter cu caracter,dar oricum ar fi raman incorecturile,deci nu cred ca-i de la citire.Ce ar putea fi? 

sunt putin nedumerit la problema asta.iau tle pe toate testele....Am facut asa:
1.calculez cu 2 foruri valorile pt a4*x4^3+a5*x5^3 si le retin intr-un vector.Sortez vectorul cu sort din stl
2.Fac 3 foruri si vad sumele S=a1*x1^3+a2*x2^3+a3*x3^3.Pe urma caut binar in vectorul calculat anterior pt fiecare suma S , -S.
3.dupa ce gasesc pozitia cea mai mare pt care v[poz]=-S, merg inapoi si vad pana la ce pozitie v[poz]=-S,iar apoi actualizez rezultatul final
Sper ca am fost destul de clar. Ma lamureste si pe mine cineva unde-i problema va rog?

later edit: asa se intampla daca nu scrii corect numele fisierelor de intrare si de iesire ) .scz pt post

Am o nelamurire...Iau 0 pct pe problema asta,desi imi dau bn toate testele de la oji.Sa fie ceva de la citire?Citirea o fac cu fgets...Astept sfaturi.
Mersi anticipat

Ma chinui de cv timp la problema asta....Iau 80 pct cu incorect pe testele 7 si 10.Ca sa gasesc rezultatul fac (n+d)-(n%d)(operatiile pe nr mari). Chestia e ca eu nu am inteles articolul cu ideea lui radu berinde pt implementarea pe nr mari si am incercat sa le fac eu(mult mai complicat si probabil mai ineficient). Se pare ca fac suma si restul bn(cel putin asa cred).In schimb la scadere cred ca gresesc undeva. Daca poate cineva sa ma lamureasca si pe mn ce-i gresit in functia asta dau o bere 

Cod:

void scadere()
{
	long long i,j,poz,k;
	for (i=1; i<=q; i++) // e clar ca (n%d) are mai putine cifre ca n+d
	{
		poz=i;
		if (c[i]>=w[i])
			c[i]=c[i]-w[i];
		else
		{
			for (j=poz+1; j<=l_sir; j++)
				if (c[j])
				{
					c[j]--;
					for (k=j-1; k>i; k--)
						c[i]=9;
					break;
				}
			c[i]=(10+c[i])-w[i];
		}
	}
	poz=0;
	for (j=l_sir; j>=1; j--)
		if (c[j]==0)
			poz++;
		else
			break;
	for (j=l_sir-poz; j>=1; j--)
		printf("%d",c[j]);
}

unde c=(n+d) si w=n%d,l_sir=lungimea lui c,q= lungimea lui w

Mersi anticipat!
[editat de moderator] Foloseste tag-ul "code" cand postezi cod pe forum.

later edit: Am luat 100 in sfarsit  .Chestia e ca faceam: for (k=j-1; k>i; k--)
                  c=9; si nu era i, era k.greseala stupida

Poate sa imi dea si mie cineva niste teste? Nu imi dau seama ce gresesc de iau numai 10 pct.  Multumesc anticipat

Am si eu o nelamurire legata de teste.Stiu ca a trecut destul de mult de la ultimul post pe forumul acestei probleme,dar ma intrebam asa...Am luat 100 pct pe problema asta http://infoarena.ro/job_detail/256082 si totusi exista teste pe care imi da gresit.Pe unul din testele postate de Andrei Purice:
in:
10 54353 64 65764 99999 499999 4352 53453 76576 8564 32341 6 423143 34534 8665 4124 54235 111111 12 432432 3232 53454 65424 4234 423432 65 8452 76542 85432 43533 78543
ar trebui sa dea:
out:
9  5 12
iar mie imi da 9 4 12.Am facut pe hartie un calcul si intr-adevar programul meu calculeaza gresit.Problema apare la secventa de nr:
 6 423143 34534 8665 4124 54235 111111
(care sunt de forma 3k+2,3k+1,3k+1,3k+2,3k+1, 3k) .Conform programului meu aceste nr sunt grupate astfel: am 3 variabile care numara nr de nr de o anumita paritate in functie de 3. Ex:nr1 reprezinta cate nr din secventa dau restul 1 la imparitrea la 3. Pe acest caz:
   nr1=3, nr2=2, nr3=1. rezultatul il calculez in felul urmator: rez=nr3+nr1/3*3+nr2/3*3,dupa care nr1 si nr 2 devin: nr1=nr1%3, nr2=nr2%3 si adun la rez 2*min(nr1,nr2). deci pe acest exemplu rez=1+3+0=4.O alegere mai comvenabila(prin care se obtinea rezultatul 5) : {3k;  3k+1;  3k+2;  3k+1; 3k+2} . Sper ca asta sa ajute la imbunatatirea testelor

Nu e asta.As fi luat kbs daca era asa.Ma gandesc ca singurul lucru ineficient ar putea fi ca am facut 2 vectori,intr-unul retin cifrele de dupa virgula si in altul resturile partiale...Tu nu tot asa ai facut?

Iau 80 puncte pe problema asta si chiar nu reusesc sa-mi dau seama ce caz as putea sa ratez(iau tle pe 2 teste) http://infoarena.ro/job_detail/249761 Daca poate cineva sa-mi dea o idee cat de mica ii raman dator

Deci e ceva dubios cu testele...Am stat cu 50 puncte peste 1 luna,cu tle pe testul 7 http://infoarena.ro/job_detail/238653  ,fara sa-mi dau seama unde buseste.Am descarcat si testele date la oji si mi-a mers pe toate testele programul. Pe testul 7 imi intra pe ciclu infinit cred...Dupa multe incercari  mi-am dat seama ca greseala este la functia de calculare a codului soldatilor(am calculat cel mai mic nr care se poate forma cu cifrele nr respectiv).Pe urma am schimbat functia codului cu una asemanatoare in care calculez cel mai mic nr care se poate calcula cu cifrele de la 1 la 9 ale nr si la sfarsit adaugam cifrele de 0.Si asa am scapat de tle si am luat 100 puncte    http://infoarena.ro/job_detail/247680
Daca cineva poate sa-mi spuna ce era gresit initial raman indatorat,desi eu tot cred ca e ceva dubios cu testele.

Deci initial am facut functia asa:

Cod:

int codul(int x)   
{   
    int a[10],i,j,r,minim=10,nr=0;   
    for (i=0; i<=9; i++)   
        a[i]=0;   
    do  
    {   
        r=x%10;   
        a[r]++;   
        if (r && r<minim)   
            minim=r;   
        x/=10;   
    }   
    while (x);   
    nr=minim;   
    a[minim]--;   
    for (i=0; i<=9; i++)   
        for (j=1; j<=a[i]; j++)   
            nr=nr*10+i;   
    return nr;   
}

si pe urma:

Cod:

int codul(int x)   
{   
    int a[10]={0},r=0;   
    do{   
        ++a[x%10];   
        x/=10;   
    }while(x);   
    for(int i=1;i<=9;++i)   
        while(a[i]--)   
            r=r*10+i;   
    while(a[0]--)   
        r*=10;   
    return r;   
} 

Am si eu o intrebare la problema asta.Cred ca am gandit bine,desi iau 0 puncte pe ea:http://infoarena.ro/job_detail/242510 
Rationamentul meu e urmatorul:
Fie cele 2 nr initiale:a,b. Daca a si b sunt ambele impare,sau unul e par si unul e impar am considerat ca sa pot obtine toate nr<=max(a,b),deci nr de mutari este max(a,b)-2.Asta ar inseamna ca castigatorul depinde de paritatea lui max(a,b).Daca e par am zis ca castiga Denisa,daca e impar castiga Dalila.Pentru cazul cand a,b sunt ambele pare am gandit asemanator cu exceptia ca |a-b| va fi intotdeauna par pt orice nr din multime.

Daca poate cineva sa-mi zica ce e gresit in rationament sau sa-mi dea cateva exemple raman indatorat 
Atasez si sursa ca sa exemplific rationamentul: