Cod sursa(job #1315368)

Utilizator VictorDumitrescuDumitrescu Victor VictorDumitrescu Data 12 ianuarie 2015 19:32:03
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <algorithm>
#define MAX 1000001
using namespace std;

FILE *f,*g;
int a[101], i, n, s, k, j, nr, x, ok1, ok2, ok;

int sum[MAX];

void sume(){
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            for(k = 1; k <= n; k++){
                nr++;
                sum[nr] = a[i] + a[j] + a[k];
            }
    sort(sum + 1, sum + 1 + nr);
}
bool caut(int val)
{
    int i = 0, pas = 1 << 19;
    while (pas != 0)
    {
        if (i + pas <= nr && sum[i + pas] <= val)
            i += pas;
        pas >>= 1;
    }
    return val == sum[i];
}

void caut2(int x){

            for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++)
                    for(k = 1; k <= n; k++)
                        if(a[i] + a[j] + a[k] == x){
                            fprintf(g, "%d %d %d\n", a[i], a[j], a[k]);
                        }
            fclose(g);
}

/*void cb(){
    for(i = 1; i <= nr; i++){
        int k = s - sum[i].s1;
        int left = 1, right = nr;
        while(left <= right){
            int mid = (left + right) / 2;
            if(sum[mid].s1 < k)
                left = mid + 1;
            else if (sum[mid].s1 > k)
                    right = mid - 1;
            else {
                fprintf(g, "%d %d %d %d %d %d\n", sum[i].a, sum[i].b, sum[i].c, sum[mid].a, sum[mid].b, sum[mid].c);
                return;
            }
        }
    }
    fprintf(g, "-1\n");
    return;
}*/

int main()
{
    f = fopen("loto.in", "r");
    g = fopen("loto.out", "w");
    fscanf(f, "%d%d", &n, &s);
    for(i = 1; i <= n; i++){
        fscanf(f, "%d", &a[i]);
    }
    fclose(f);
    sume();
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            for(k = 1; k <= n; k++)
                if(caut(s-a[i]-a[j]-a[k]))
                {
                    fprintf(g, "%d %d %d ", a[i], a[j], a[k]);
                    caut2(s-a[i]-a[j]-a[k]);
                    return 0;
                }
    fprintf(g,"-1\n");
    return 0;
}