Cod sursa(job #1873)
Utilizator | Data | 15 decembrie 2006 08:02:49 | |
---|---|---|---|
Problema | Semne | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.06 kb |
#include<stdio.h>
#include<stdlib.h>
#define M 50001
long S , S1 ,S2, k;
long s;
long a[M] , sume[M];
long n , i , j;
int semn,nr;
long sol[50001];
long ssol[50001];
int main()
{
freopen("semne.in","r",stdin);
freopen("semne.out","w",stdout);
scanf("%ld%ld",&n,&S);
for (i = 1 ; i <= n ; i++)
{
scanf("%ld",&a[i]);
sume[i] += sume[i-1] + a[i];
}
while(1)
{
s = 0;
S1 = 0;
S2 = 0;
semn = 1;//1 - plus , -1 - minus
sol[0] = 0;
k = 0;
int ind = 1;
while (s<=n)
{
while(1)
{
k = rand()%n;
if (k!=0)
break;
}
sol[0]++;
sol[sol[0]] = k;
ssol[sol[0]] = ssol[sol[0]-1] + k;
if (s+k >= n)
{
sol[sol[0]] = n - s;
ssol[sol[0]] = n;
s = n;
k = 0;
S1 = sume[sol[1]];
S2 = -S1;
semn = -1;
for (i = 2 ; i <= sol[0] ; i++)
{
S1 += (sume[ssol[i]] - sume[ssol[i-1]])*semn;
S2 +=(-(sume[ssol[i]] - sume[ssol[i-1]]))*semn;
if (semn==-1)
semn = 1;
else
semn = -1;
}
if (S1 == S)
{
for (i = 1 ; i <= sol[0] ; i++)
{
for (j = 1 ; j <= sol[i] ; j++)
{
if (i%2==1)
printf("+");
else
printf("-");
}
}
ind = 0;
return 0;
}
if (S2 == S)
{
for (i = 1 ; i <= sol[0] ; i++)
{
for (j = 1 ; j <= sol[i] ; j++)
{
if (i%2==1)
printf("-");
else
printf("+");
}
}
ind = 0;
return 0;
}
s = 0;
break;
}
s+=k;
}
if (ind==0)
break;
}
return 0;
}