Cod sursa(job #14743)

Utilizator vlad_popaVlad Popa vlad_popa Data 9 februarie 2007 17:55:22
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define FIN "semne.in"
#define FOUT "semne.out"
#define NMAX 50001

int N, a[NMAX], s[NMAX], tip[NMAX], K;
long long sol;

void dec ()
{
  int i = 1;
  while (sol > K && i <= N)
    {
      if (tip[i])
       {
         tip[i] = 0;
         sol -= 2*a[i];
       }
      i++;
    }
}

void inc ()
{
  int i = 1;
  while (sol < K && i <= N)
    {
      if (!tip[i])
       {
         tip[i] = 1;
         sol += 2*a[i];
       }
      i++;
    }
}

int
 main ()
{
  int i, P = 0, j;
  srand (time(0));
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d%d", &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 <= 100; ++ 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;
}