Cod sursa(job #290175)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 27 martie 2009 16:34:51
Problema Semne Scor 100
Compilator cpp Status done
Runda aa Marime 2.43 kb
// 95 - 100 puncte :))      
#include <stdio.h>      
#include <time.h>      
#include <stdlib.h>      
     
#define FIN "semne.in"      
#define FOUT "semne.out"      
#define NMAX 50001      
     
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;      
}