Cod sursa(job #50901)

Utilizator gigi_becaliGigi Becali gigi_becali Data 9 aprilie 2007 12:52:34
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <time.h>

#define Nmax 50002
#define MOD 1236667891
#define key 1236661

int a[Nmax], b[Nmax], v[Nmax];
int r, p;
char s[Nmax];

void srand(int seed)
 {
  r = 1+seed;      
 }

int rand()
 {
  r+=key;
  if(r>MOD)
   r -= MOD; 
  return r;         
 }

int main()
 {
  freopen("semne.in","r",stdin);
  freopen("semne.out","w",stdout);         
  
  int i,n,S=0, A=0,B=0;
  
  srand((int)time(0));
  
          
  scanf("%d%d", &n,&S);
  
  for(i=1;i<=n;++i)
   {
    scanf("%d", v+i);
    if(A - B <= S)
     {
      a[++a[0]] = i;
      A += v[i];
      s[i] = '+';
      } 
      else
     {
      b[++b[0]] = i;
      B += v[i];
      s[i] = '-';
     } 
   }  

  while(A-B != S)
   { 
    if(A-B > S) 
     {
      // mut din A in B     
      int tmp = (rand()%a[0])+1; 
      b[++b[0]] = a[tmp];
      A -= v[a[tmp]];     
      B += v[a[tmp]];
      s[a[tmp]] = '-';      
      a[tmp] = a[a[0]--];            
     }
    if(A-B < S)
     {
      // mut din B in A     
      int tmp = (rand()%b[0])+1; 
      a[++a[0]] = b[tmp];
      A += v[b[tmp]];     
      B -= v[b[tmp]];
      s[b[tmp]] = '+';
      b[tmp] = b[b[0]--];            
     }    
     
    if(b[0] == 0 && A-B != S) 
     {
      // mut din A in B     
      int tmp = (rand()%a[0])+1; 
      b[++b[0]] = a[tmp];
      A -= v[a[tmp]];     
      B += v[a[tmp]];
      s[a[tmp]] = '-';      
      a[tmp] = a[a[0]--];            
     }
     
    if(a[0] == 0 && A-B != S) 
     {
      // mut din B in A     
      int tmp = (rand()%b[0])+1; 
      a[++a[0]] = b[tmp];
      A += v[b[tmp]];     
      B -= v[b[tmp]];
      s[b[tmp]] = '+';
      b[tmp] = b[b[0]--];            
     }        
   }
   
  for(i=1;i<=n;++i)
   printf("%c", s[i]);
     

  return 0;         
 }