Cod sursa(job #2073775)

Utilizator edi_laitinLaitin Eduard edi_laitin Data 23 noiembrie 2017 18:22:58
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("semne.in");
ofstream fout("semne.out");

const int NMax = 50000;
int Sum,S,N,X[NMax + 5];
vector <int> Plus, Minus;
char Sign[NMax + 5];
void Read()
{
  fin >> N >> S;
  for(int i = 1; i <= N; ++i)
  {
    fin >> X[i];
    Plus.push_back(i);
    Sign[i] = '+';
    Sum += X[i];
  }
}

void Solve()
{
  srand(time(NULL));
  while(Sum != S)
  {
    if(Sum > S)
    {
      int i = rand() % Plus.size();
      Sum -= 2*X[Plus[i]];
      Sign[Plus[i]] = '-';
      Minus.push_back(Plus[i]);
      Plus[i] = Plus[Plus.size()-1];
      Plus.pop_back();
    }
    else
    {
      int i = rand() % Minus.size();
      Sum += 2*X[Minus[i]];
      Sign[Minus[i]] = '+';
      Plus.push_back(Minus[i]);
      Minus[i] = Minus[Minus.size()-1];
      Minus.pop_back();
    }
  }
}

void Print()
{
  for(int i = 1; i <= N; ++i)
    fout << Sign[i];
  fout << "\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}