Cod sursa(job #731244)

Utilizator deneoAdrian Craciun deneo Data 7 aprilie 2012 19:54:37
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

ifstream fin("semne.in");
ofstream fout("semne.out");

#define MAXN 60000

long long curSum, sum;
int n, v[MAXN], poz[MAXN], neg[MAXN];
char semn[MAXN];
int main() {
    int i, p;
    srand(time(NULL));
    fin >> n >> sum;
    for (i = 1; i <= n; ++i) {
        fin >> v[i];
        switch(rand() % 2) {
            case 0: {
                neg[++neg[0]] = i;
                curSum -= v[i];
                semn[i] = '-';
                break;
            }
            case 1: {
                poz[++poz[0]] = i;
                curSum += v[i];
                semn[i] = '+';
                break;
            }
        }
    }
    while (curSum != sum) {
        if (curSum > sum) {
            p = rand() % poz[0] + 1;
            swap(poz[poz[0]], poz[p]);
            neg[++neg[0]] = poz[poz[0]];
            semn[poz[poz[0]]] = '-';
            curSum -= poz[poz[0]] * 2;
            --poz[0];
        }
        else {
            p = rand() % neg[0] + 1;
            swap(neg[neg[0]], neg[p]);
            poz[++poz[0]] = neg[neg[0]];
            semn[neg[neg[0]]] = '+';
            curSum += neg[neg[0]] * 2;
            --neg[0];
        }
    }
    for (i = 1; i <= n; ++i)
        fout << semn[i];
    fout.close();
    return 0;
}