Cod sursa(job #1481618)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 4 septembrie 2015 22:13:14
Problema Semne Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50000
int v[MAXN], p[MAXN], m[MAXN];
char ch[MAXN];
int main(){
    int n, s, x, i, a, b, poz;
    FILE *fin, *fout;
    fin=fopen("semne.in", "r");
    fout=fopen("semne.out", "w");
    fscanf(fin, "%d%d", &n, &s);
    x=0;
    for(i=0; i<n; i++){
        fscanf(fin, "%d", &v[i]);
        p[i]=i;
        x+=v[i];
    }
    a=n;
    b=0;
    while(x!=s){
        if(x<s){
            poz=(rand()*rand())%b;
            x+=2*v[m[poz]];
            p[a++]=m[poz];
            m[poz]=m[b-1];
            b--;
        }else{
            poz=(rand()*rand())%a;
            x-=2*v[p[poz]];
            m[b++]=p[poz];
            p[poz]=p[a-1];
            a--;
        }
    }
    for(i=0; i<a; i++){
        ch[p[i]]='+';
    }
    for(i=0; i<b; i++){
        ch[m[i]]='-';
    }
    for(i=0; i<n; i++){
        fputc(ch[i], fout);
    }
    fputc('\n', fout);
    fclose(fin);
    fclose(fout);
    return 0;
}