Cod sursa(job #340446)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 14 august 2009 18:14:29
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50010
int n,v[N],poz[N],neg[N],semn[N];
long long s,sum;
void read()
{
	scanf("%d%lld",&n,&s);
	int i;
	for (i=1; i<=n; i++)//fac citirea si incerc o alegere a semnelor ca sa obtin suma
	{
		scanf("%d",&v[i]);
		if (sum<s)
		{
			sum+=v[i];
			poz[++poz[0]]=i;//vector cu pozitiile nr luate cu semnul '+'
			semn[i]=1;
		}
		else
		{
			sum-=v[i];
			neg[++neg[0]]=i;//vector cu pozitiile nr luate cu semnul '-'
		}
	}
}
void solve()
{
	srand(time(0));
	int k;
	while (sum!=s)//schimb semne de '+' in '-' si invers si incerc sa obtin suma s
		if (sum<s)//inseamna ca trebuie sa schimb semnul unui nr luat cu '-' in '+'
		{
			k=rand() % neg[0]+1;//aleg la intamplare unul din nr luate cu '-'
			sum+=2*v[neg[k]];//updatez suma
			semn[neg[k]]=1;//schimb semnul nr ales
			poz[++poz[0]]=neg[k];//il adaug in vectorul cu nr pozitive
			neg[k]=neg[neg[0]];//updatez vectorul cu nr negative
			neg[0]--;
		}
		else//inseamna ca trebuie sa schimb semnul unui nr luat cu '+' in '-'
		{
			k=rand() % poz[0]+1;//aleg la intamplare unul din nr luate cu '+'
			sum-=2*v[poz[k]];//updatez suma
			semn[poz[k]]=0;//schimb semnul nr ales
			neg[++neg[0]]=poz[k];//il adaug in vectorul cu nr negative
			poz[k]=poz[poz[0]];//updatez vectorul cu nr pozitive
			poz[0]--;
		}
}
void show()
{
	int i;
	for (i=1; i<=n; i++)
		if (semn[i])//semn[i]=1 => '+'
			printf("+");
		else//semn[i]='0' => '-'
			printf("-");
	printf("\n");
}
int main()
{
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}