Cod sursa(job #727271)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 27 martie 2012 20:26:11
Problema Semne Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include <cstring>
#include <cstdlib>
#include <ctime>


int n, i , sp , sm , poz , s,semn1;
long long sum;
int V[80010],P[1000000],M[1000000];
char semn[80010];

FILE*f=fopen("semne.in","r");
FILE*g=fopen("semne.out","w");

int main(){
	
	srand(time(0));
	
	fscanf(f,"%d%d",&n,&s);
	
	for(i=1;i<=n;i++){
		fscanf(f,"%d",&V[i]);
		semn1=rand()%2;
		if(semn1){
			sum-=V[i];
			semn[i]='-';
			M[++sm]=i;
		}
		else{
			sum+=V[i];
			semn[i]='+';
			P[++sp]=i;
		}
	}
	while(sum!=s){
		if(sum>s){
			do{
				poz=rand()%sp+1;
			}while(P[poz]<=0);
			sum-=V[P[poz]]*2;
			semn[P[poz]]='-';
			M[++sm]=P[poz];
			P[poz]=-1;
		}
		else{
			do{
				poz=rand()%sm+1;
			}while(M[poz]<=0);
			sum+=2*V[M[poz]];
			semn[M[poz]]='+';
			P[++sp]=M[poz];
			M[poz]=-1;
		}
	}
	fprintf(g,"%s",semn+1);
	return 0;
}