Pagini recente » Rating Ileana Gheorghisor (Ile_Gheo) | Cod sursa (job #1788683) | Istoria paginii runda/oni2009x1 | Cod sursa (job #2465131) | Cod sursa (job #609301)
Cod sursa(job #609301)
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MaxN 50100
#define ll long long
ll A[MaxN];
int B[MaxN];
int Plus[MaxN];
int Minus[MaxN];
int N;
ll S;
ll sum = 0;
void citire(void)
{
FILE *f = fopen("semne.in","r");
fscanf(f,"%d %llu",&N,&S);
for(int i=1;i<=N;i++)
fscanf(f,"%llu ",&A[i]);
fclose(f);
}
void FillSemn(void)
{
for(int i=1;i<=N;i++)
{
B[i] = rand()%2;
if(B[i])
{
sum += A[i];
Plus[++Plus[0]] = i;
}
else
{
sum -= A[i];
Minus[++Minus[0]] = i;
}
}
}
void solve(void)
{
FillSemn();
int random;
for(;sum != S;)
if(S >= sum)
{
random = rand()%Minus[0] + 1;
Plus[++Plus[0]] = Minus[random];
Minus[random] = Minus[Minus[0]--];
sum += 1LL*2*A[Plus[Plus[0]]];
B[Plus[Plus[0]]] = 1;
}
else
{
random = rand()%Plus[0] + 1;
Minus[++Minus[0]] = Plus[random];
Plus[random] = Plus[Plus[0]--];
sum -= 1LL*2*Minus[Minus[0]];
B[Minus[Minus[0]]] = 0;
}
// printf("%d\n",sum);
}
int main()
{
FILE *g = fopen("semne.out","w");
citire();
srand((unsigned)time(0));
solve();
for(int i=1;i<=N;i++)
if(B[i])
fprintf(g,"+");
else
fprintf(g,"-");
fclose(g);
return 0;
}