Cod sursa(job #1584990)

Utilizator hrazvanHarsan Razvan hrazvan Data 30 ianuarie 2016 17:48:12
Problema Semne Scor 95
Compilator c Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 50000
int v[MAXN], p1[MAXN], p2[MAXN], d1, d2;
char semn[MAXN + 1];

int main(){
  srand(time(0));
  FILE *in = fopen("semne.in", "r");
  int n, i, x;
  long long sc = 0, s;
  fscanf(in, "%d%lld", &n, &s);
  for(i = 0; i < n; i++){
    fscanf(in, "%d", &v[i]);
    sc += v[i];
    p1[i] = i;
  }
  fclose(in);
  d1 = n;
  while(sc != s){
    while(sc > s){
      x = rand() % d1;
      sc -= 2 * v[p1[x]];
      p2[d2] = p1[x];
      d2++;
      p1[x] = p1[d1 - 1];
      d1--;
    }
    while(sc < s){
      x = rand() % d2;
      sc += 2 * v[p2[x]];
      p1[d1] = p2[x];
      d1++;
      p2[x] = p2[d2 - 1];
      d2--;
    }
  }
  for(i = 0; i < d1; i++)
    semn[p1[i]] = '+';
  for(i = 0; i < d2; i++)
    semn[p2[i]] = '-';
  semn[n] = 0;
  FILE *out = fopen("semne.out", "w");
  fputs(semn, out);
  fclose(out);
  return 0;
}