Cod sursa(job #1951695)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 3 aprilie 2017 19:08:55
Problema Semne Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<time.h>
#include<stdlib.h>
#include<vector>
using namespace std;
ifstream fi("semne.in");
ofstream fo("semne.out");
vector<int> Plus,Minus;
char R[50001];
int A[50001],i,n,S,s,poz;
int main()
{
    srand(time(NULL));
    fi>>n>>S;
    for(i=1; i<=n; i++)
    {
        fi>>A[i];
        //initial peste tot este +
        Plus.push_back(i);
        s+=A[i];
        R[i]='+';
    }
    while(s!=S)
    {
        //transform un plus in minus
        if(s>S)
        {
            poz=rand()%Plus.size();
            Minus.push_back(Plus[poz]);
            s=s-2*A[Plus[poz]];
            R[Plus[poz]]='-';
            Plus[poz]=Plus.back();
            Plus.pop_back();
        }
        //altfel, transform un minus in plus
        else
        {
            poz=rand()%Minus.size();
            Plus.push_back(Minus[poz]);
            s=s+2*A[Minus[poz]];
            R[Minus[poz]]='+';
            Minus[poz]=Minus.back();
            Minus.pop_back();
        }
    }
    fo<<R+1<<"\n";
    fi.close();
    fo.close();
    return 0;
}