Pagini recente » Cod sursa (job #2077344) | Cod sursa (job #1787467) | Cod sursa (job #2080237) | Cod sursa (job #806074) | Cod sursa (job #340446)
Cod sursa(job #340446)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50010
int n,v[N],poz[N],neg[N],semn[N];
long long s,sum;
void read()
{
scanf("%d%lld",&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;
}