Cod sursa(job #34630)

Utilizator pocaituDavid si Goliat pocaitu Data 21 martie 2007 00:26:24
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<fstream.h>
#include<stdlib.h>
#define nmax 50002
unsigned int n,x,d,suma,i,j,s[nmax],v1[nmax],v2[nmax];

long sum;
int main()
{char semn[nmax];
randomize();
freopen("semne.in","r",stdin);
scanf("%u%u",&n,&suma);
for(i=1;i<=n;i++)
 scanf("%u",&s[i]);
for(i=1;i<=n;i++)
 {x=rand()%2;
  if(x)
	{sum+=s[i];
	 v1[++v1[0]]=i;
	 }
  else
	{sum-=s[i];
	 v2[++v2[0]]=i;
	 }
  }
//sum-=suma;
while(sum!=suma)
 {//randomize();
  if(sum<suma)
	{
	 d=(rand()%v2[0])+1;
	 sum+=2*s[v2[d]];
	 v1[++v1[0]]=v2[d];
	 v2[d]=v2[v2[0]--];
	 }
  else
	{d=(rand()%v1[0])+1;
	 sum-=2*s[v1[d]];
	 v2[++v2[0]]=v1[d];
	 v1[d]=v1[v1[0]--];
	 }
  }

ofstream g("semne.out");

for(i=1;i<=v1[0];i++)
 semn[v1[i]-1]='+';
for(i=1;i<=v2[0];i++)
 semn[v2[i]-1]='-';
semn[n]=NULL;
g<<semn;
g.close();
return 0;
}