Cod sursa(job #102000)

Utilizator astronomyAirinei Adrian astronomy Data 13 noiembrie 2007 22:57:05
Problema Economie Scor Ascuns
Compilator c Status done
Runda Marime 1.96 kb
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

#define MAXVAL 51000
#define MAXN 1024

int N, res, A[MAXN], sol[MAXN];
char ok[MAXVAL], am[MAXVAL];

void solve(void)
{
    int i, j, k;

    for(i = 1; i <= N; i++)
     for(j = i+1; j <= N; j++)
      if(A[i] > A[j])
        A[i] ^= A[j], A[j] ^= A[i], A[i] ^= A[j];

    for(ok[0] = 1, i = 1; i <= N; i++)
     if(ok[A[i]] != 1)
        for(sol[++res] = A[i], j = A[i]; j < MAXVAL; j++)
         if(ok[j-A[i]] == 1)
          ok[j] = 1;
}

void read_data(void)
{
    int i;
    scanf("%d ", &N);
    for(i = 1; i <= N; i++)
        scanf("%d ", &A[i]), am[A[i]] = 1;
}

void write_data(void)
{
    int i;
    
    printf("%d\n", res);
    for(i = 1; i <= res; i++)
        printf("%d ", sol[i]);
    printf("\n");
}

int K, val;

int main(void)
{
    int i, j;

    freopen("economie.in", "rt", stdin);
    freopen("economie.out", "wt", stdout);

    
    read_data();
    solve();
    write_data();

   /* freopen("economie.out", "rt", stdin);
    scanf("%d", &K);
    if(K != res)
    {
        fprintf(stdout, "0\n");
        fprintf(stderr, "L-ai dezamagit pe Vultur:(\n");
        exit(0);
    }
    memset(ok, 0, sizeof(ok));
    ok[0] = 1;
    
    for(i = 1; i <= K; i++)
    {
        scanf("%d ", &val);

//        assert(val < 1);
//        assert(val > 50000);
        
        if(!am[val])
        {
            fprintf(stdout, "0\n");
            fprintf(stderr, "L-ai dezamagit pe Vultur:(\n");
            exit(0);
        }
        for(j = val; j < MAXVAL; j++)
         if(ok[j-val] == 1)
            ok[j] = 1;

    }

    for(i = 1; i <= N; i++)
     if(ok[A[i]] != 1)
     {
        fprintf(stdout, "0\n");
        fprintf(stderr, "L-ai dezamagit pe Vultur:(\n");
        exit(0);
     }
    
    fprintf(stdout, "10\n");
    fprintf(stderr, "L-ai salvat pe Vultur:)\n"); */
    
    return 0;
}