Cod sursa(job #1692)

Utilizator flo_demonBunau Florin flo_demon Data 14 decembrie 2006 15:49:17
Problema Semne Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <map>

using namespace std;

#define MAX 50006

int a[MAX];
int R, n, s, sum, semne[MAX], saux;
int countt;
int* it;

void Write();
void ReSeed();

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

            }
            else
            {
                if (saux < 0)
                {
                    saux *= -1;
                    saux /= 2;
                    it = lower_bound(a+1, a+n+1, saux);
                    while ((*it) == 1)
                    {
                        it++;
                        if (it - a == n+1) break;
                    }
                    aux = (*it);
                    semne[it-a] = 1;
                    
                    sum += 2*aux;
                }
            }
        }
    }
    
    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()
{
    sum = 0;
    countt = 0;
    for (int i = 1; i <= n; ++i)
    {
        R = rand()%2;
        if (R == 0)
            semne[i] = -1;
        if (R == 1)
            semne[i] = 1;
        sum += a[i] * semne[i];
    }
}