Cod sursa(job #1950146)

Utilizator andreiudilaUdila Andrei andreiudila Data 2 aprilie 2017 19:00:19
Problema Semne Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <string>
#include <algorithm>
#include <time.h>
#include<cstring>
#include<stdlib.h>
using namespace std;
ifstream cin("semne.in");
ofstream cout("semne.out");
long long v[50000], q,i,j,n,s;
string sol;
int aux[50000];

string getRandom(int n, int k){

  if (n<0) n=-n;

  long long sum=0;
  int neg=0;
  int poz=0;

  for (int i=1; i<=k; ++i)
   if (rand() % 2) {
      sum+=v[i];
      aux[i]=1;
      ++poz;
   }
   else {
        sum-=v[i];
        aux[i]=0;
        ++neg;
   }

   int nrit=0;
   int r=0;
   while (sum!=n && nrit<10000) {

     if (sum>n) {
            if(poz!=0)
         r=rand()%poz+1;
        int cnt=0;
        int pos=0;

        for (int i=1; i<=k; ++i)
        if (aux[i]==1) {
            ++cnt;
            pos=i;
            if (cnt==r) break;
        }

        sum-=v[pos]*(long long)2;
        aux[pos]=0;
        --poz;
        ++neg;
     }
     else if(sum<n){
        if(neg!=0)
         r=rand()%neg+1;
        int cnt=0;
        int pos=0;

        for (int i=1; i<=k; ++i)
        if (aux[i]==0) {
            ++cnt;
            pos=i;
            if (cnt==r) break;
        }

        sum+=v[pos]*(long long)2;
        aux[pos]=1;
        ++poz;
        --neg;
     }
     else break;

    ++nrit;
   }

   string sol="";

   if (sum!=n) return sol;

   for (int i=1; i<=k; ++i)
    if (aux[i]==0) sol+='-';
    else sol+='+';

   return sol;
}

int main()
{
    srand(time(NULL));

    cin>>n>>s;
    for(i=1;i<=n;++i) cin>>v[i];


        string sol=getRandom(s,n);

        cout<<sol;

    return 0;
}