Cod sursa(job #14739)

Utilizator vlad_popaVlad Popa vlad_popa Data 9 februarie 2007 17:44:24
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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;

int
 main ()
{
  int i, P = 0, j;
  long long sol;
  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;
         }
      }
     i = 1;
     if (sol > K)
       while (sol > K && i <= N)
        {
          if (tip[i])
           {
             tip[i] = 0;
             sol -= 2*a[i];
           }
          i++;
        }
     i = 1;
     if (sol < K)
       while (sol < K && i <= N)
        {
          if (!tip[i])
           {
             tip[i] = 1;
             sol += 2*a[i];
           }
          i++;
        }
     if (sol == K)
      {
        for (i = 1; i <= N; ++ i)
          if (tip[i])
            printf ("+");
          else
            printf ("-");
        return 0;
      }
   }
  return 0;
}