Pagini recente » Cod sursa (job #1226613) | Cod sursa (job #2795406) | Cod sursa (job #856538) | Cod sursa (job #1110206) | Cod sursa (job #340442)
Cod sursa(job #340442)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50005
int n,s,v[N],poz[N],neg[N],semn[N],sum;
void read()
{
scanf("%d%d",&n,&s);
int i;
for (i=1; i<=n; i++)//fac citirea si incerc o alegere a semnelor ca sa obtin suma
{
scanf("%d",&v[i]);
if (sum<s)
{
sum+=v[i];
poz[++poz[0]]=i;//vector cu pozitiile nr luate cu semnul '+'
semn[i]=1;
}
else
{
sum-=v[i];
neg[++neg[0]]=i;//vector cu pozitiile nr luate cu semnul '-'
}
}
}
void solve()
{
srand(time(0));
int k;
while (sum!=s)//schimb semne de '+' in '-' si invers si incerc sa obtin suma s
if (sum<s)//inseamna ca trebuie sa schimb semnul unui nr luat cu '-' in '+'
{
k=rand() % neg[0]+1;//aleg la intamplare unul din nr luate cu '-'
sum+=2*v[neg[k]];//updatez suma
semn[neg[k]]=1;//schimb semnul nr ales
poz[++poz[0]]=neg[k];//il adaug in vectorul cu nr pozitive
neg[k]=neg[neg[0]];//updatez vectorul cu nr negative
neg[0]--;
}
else//inseamna ca trebuie sa schimb semnul unui nr luat cu '+' in '-'
{
k=rand() % poz[0]+1;//aleg la intamplare unul din nr luate cu '+'
sum-=2*v[poz[k]];//updatez suma
semn[poz[k]]=0;//schimb semnul nr ales
neg[++neg[0]]=poz[k];//il adaug in vectorul cu nr negative
poz[k]=poz[poz[0]];//updatez vectorul cu nr pozitive
poz[0]--;
}
}
void show()
{
int i;
for (i=1; i<=n; i++)
if (semn[i])//semn[i]=1 => '+'
printf("+");
else//semn[i]='0' => '-'
printf("-");
printf("\n");
}
int main()
{
freopen("semne.in","r",stdin);
freopen("semne.out","w",stdout);
read();
solve();
show();
return 0;
}