Cod sursa(job #739472)

Utilizator Robert29FMI Tilica Robert Robert29 Data 23 aprilie 2012 10:10:56
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<cstdlib>
#include<ctime>
using namespace std;
FILE*f=fopen("semne.in","r");
FILE*g=fopen("semne.out","w");
char s[50002],ok;
int p,m,n,k,V[50002],v[50002],w[50002];
long long S,P,M;
int main()
{
	srand(time(NULL));
	fscanf(f,"%d%lld",&n,&S);
	for(int i=1;i<=n;++i)
	{
		fscanf(f,"%d",&V[i]);
		k=rand()%2;
		if(k)
		{
			v[++p]=i;
			s[i]=1;
			P+=V[i];
		}
		else
		{
			w[++m]=i;
			M+=V[i];
		}
	}
	
	while(!ok)
	{
		if(P-M<S)
		{
			k=rand()%m+1;
			M-=V[w[k]];
			P+=V[w[k]];
			s[w[k]]=1;
			v[++p]=w[k];
			w[k]=w[m--];		
		}
		else if(P-M>S)
		{
			k=rand()%p+1;
			M+=V[v[k]];
			P-=V[v[k]];
			s[v[k]]=0;
			w[++m]=v[k];
			v[k]=v[p--];
		}
		else
			ok=1;
	}
	
	for(int i=1;i<=n;++i)
		if(s[i])
			fprintf(g,"+");
		else
			fprintf(g,"-");
	
	fclose(f);
	fclose(g);
	return 0;
}