Cod sursa(job #320622)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 5 iunie 2009 11:36:44
Problema Semne Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <stdio.h>         
#include <time.h>         
#include <stdlib.h>         
        
#define FIN "semne.in"         
#define FOUT "semne.out"         
#define NMAX 20001

int a[NMAX], tip[NMAX];
long long sol, s[NMAX], K, N;
        
void dec ()         
{         
  int t = rand() % 10;         
  int i;         
  if (t)         
    i = 1;         
  else        
    i = N;         
  while (sol > K && i <= N)         
    {         
      if (tip[i])         
       {         
         tip[i] = 0;         
         sol -= 2*a[i];         
       }         
      if (!t)         
        -- i;         
      else        
        ++ i;         
    }         
}         
        
void inc ()         
{         
  int t = rand() % 10;         
  int i;         
  if (t)         
    i = 1;         
  else        
    i = N;         
  while (sol < K && i <= N)         
    {         
      if (!tip[i])         
       {         
         tip[i] = 1;         
         sol += 2*a[i];         
       }         
      if (!t)         
        -- i;         
      else        
        ++ i;         
    }         
}         
        
int        
 main ()         
{         
  int i, P = 0;         
  srand (time(0));         
  freopen (FIN, "rt", stdin);         
  freopen (FOUT, "wt", stdout);         
        
  scanf ("%lld%lld", &N, &K);         
  for (i = 1; i <= N; ++ i)         
    scanf ("%d", &a[i]);         
  s[N] = a[N];         
  for (i = N - 1; i >= 1; -- i)         
    s[i] = s[i + 1] + a[i];         
  while (!P)         
   {         
     sol = 0;         
     for (i = 1; i <= N; ++ i)         
      {         
        tip[i] = rand() % 2;         
        if (tip[i])         
          sol += a[i];         
        else        
          sol -= a[i];         
        if (sol + s[i + 1] < K && !tip[i])         
         {         
           sol += 2*a[i];         
           tip[i] = 1;         
         }         
        if (sol - s[i + 1] > K && tip[i])         
         {         
           sol -= 2*a[i];         
           tip[i] = 0;         
         }         
      }         
     for (i = 1; i <= 600; ++ i)         
      {         
        if (sol > K)         
          dec();         
        if (sol < K)         
          inc();         
      }         
     if (sol == K)         
      {         
        for (i = 1; i <= N; ++ i)         
          if (tip[i])         
            printf ("+");         
          else        
            printf ("-");         
        return 0;         
      }         
   }         
  return 0;         
}