Cod sursa(job #609303)

Utilizator maritimCristian Lambru maritim Data 20 august 2011 16:17:39
Problema Semne Scor 5
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.29 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.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)
		{
			assert(Minus[0]);
			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
		{
			assert(Plus[0]);
			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;
}