Cod sursa(job #836772)

Utilizator stoicatheoFlirk Navok stoicatheo Data 16 decembrie 2012 18:35:22
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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;
 
}