Cod sursa(job #1099)

Utilizator alextheroTandrau Alexandru alexthero Data 12 decembrie 2006 18:27:01
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define nmax 50005

int a[nmax],b[nmax],v[nmax];

int randn(int a) {
    if(a==0) return 0;
	return rand() % (a+1);
}


int main() {
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);

	int n,x;
	long long s;

	srand(time(0)/123);

	scanf("%d %lld\n",&n,&s);
	int i;
	for(i=1;i<=n;i++) {
			scanf("%d ",&v[i]);
			if(randn(1)==0) a[++a[0]]=i;
			else b[++b[0]]=i;
	}
	long long s1=0;
	long long s2=0;
	for(i=1;i<=a[0];i++) s1+=v[a[i]];
	for(i=1;i<=b[0];i++) s2+=v[b[i]];

    // s1 - s2 = s
    
    while(s1-s!=s2) {
                    if(s1-s>s2) {
                                int x=randn(a[0]-1)+1;
                                s1-=v[a[x]];
                                s2+=v[a[x]];
                                b[++b[0]]=a[x];
                                a[x]=a[a[0]];
                                a[0]--;
                                }                
                    else {
                          int x=randn(b[0]-1)+1;
                          s2-=v[b[x]];
                          s1+=v[b[x]];
                          a[++a[0]]=b[x];
                          b[x]=b[b[0]];
                          b[0]--;
                         }      
    }
	int way[nmax];
	for(i=1;i<=a[0];i++) way[a[i]]=0;
	for(i=1;i<=b[0];i++) way[b[i]]=1;
	for(i=1;i<=n;i++)
			if(way[i]==0) printf("+");
			else printf("-");
	printf("\n");
	return 0;

}