Cod sursa(job #72218)

Utilizator info_arrandrei gigea info_arr Data 13 iulie 2007 00:23:22
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#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 <= 500; ++ 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;
}