Cod sursa(job #286305)

Utilizator holleraaaa vvvv holler Data 23 martie 2009 17:33:06
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 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;   
}