Cod sursa(job #1772)

Utilizator flo_demonBunau Florin flo_demon Data 14 decembrie 2006 18:42:47
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MAX 50006

long long a[MAX];
long long s, sum, saux;
int n, R, semne[MAX];;

void Write();
void ReSeed();

int main()
{
    srand ( time(NULL) );
    FILE *fin = fopen("semne.in", "r");
    fscanf(fin, "%d%lld", &n, &s);
    for (int i = 1; i <= n; ++i)
        fscanf(fin, "%lld", &a[i]);
    fclose(fin);
    
    ReSeed();
    
    int aux;
    while (1)
    {
        if (sum == s) { Write(); break; }
        else
        {
            saux = sum - s;
            if (saux > 0)
            {
                R = (rand()%n) + 1;
                while(semne[R] == -1)
                    R = (rand()%n) + 1;
                aux = a[R];
                sum -= 2*aux;
                semne[R] = -1;
            }
            else
            {
                if (saux < 0)
                {
                    R = (rand()%n) + 1;
                    while(semne[R] == 1)
                        R = (rand()%n) + 1;
                    aux = a[R];
                    sum += 2*aux;
                    semne[R] = 1;
                }
            }
        }
    }
    
    return 0;
}

void Write()
{
    FILE *fout = fopen("semne.out", "w");
    for (int i = 1; i <= n; ++i)
    {
        if (semne[i] == -1)
            fprintf(fout, "-");
        else
            if (semne[i] == 1)
                fprintf(fout, "+");
    }
    fclose(fout);
}

void ReSeed()
{
    for (int i = 1; i <= n; ++i)
    {
        if (i % 2 == 0)
            semne[i] = -1;
        if (i % 2 == 1)
            semne[i] = 1;
        sum += a[i] * semne[i];
    }
}