Cod sursa(job #320605)
Utilizator | Data | 5 iunie 2009 10:59:08 | |
---|---|---|---|
Problema | Semne | Scor | 55 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.7 kb |
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define FIN "semne.in"
#define FOUT "semne.out"
#define NMAX 501
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;
}