Cod sursa(job #1274959)

Utilizator lokixdSebastian lokixd Data 24 noiembrie 2014 16:55:23
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include "stdio.h"
#include "stdlib.h"
#include <algorithm>
using namespace std;
 
#define MAX 100000001
 
FILE *f, *g;
int nr[101];
int S;
int N;
 
typedef struct number {
    int i;
    int j;
    int k;
    int sum;
};
 
number n[1000001];
int index, size;
int ok;
 
int compare(number a, number b)
{
    return (a.sum < b.sum);
}
 
int main()
{
    f = fopen("loto.in", "r");
    g = fopen("loto.out", "w");
 
    fscanf(f, "%d", &N);
    fscanf(f, "%d", &S);
 
    for(int i = 1; i <= N; i++)
        fscanf(f, "%d", &nr[i]);
 
    index = 1;
 
    for(int i = 1; i <= N; i++)
        for(int j = i; j <= N; j++)
            for(int k = j; k <= N; k++)
            {
                n[index].i = nr[i];
                n[index].j = nr[j];
                n[index].k = nr[k];
                n[index].sum = nr[i] + nr[j] + nr[k];
                index++;
            }
 
    size = index - 1;
 
    // sort
    sort(n + 1, n + 1 + size, compare);
 
    ok = 1;
 
    for(int i = 1; i <= size; i++)
    {
        int sum = S - n[i].sum;
        int a = 1;
        int b = size;
 
        for(;a<=b&&ok;)
        {
            int middle = (a+b) / 2;
            if(n[middle].sum == sum)
            {
                fprintf(g, "%d %d %d %d %d %d", n[i].i, n[i].j, n[i].k, n[middle].i, n[middle].j, n[middle].k);
                ok = 0;
            }
            if(n[middle].sum > sum)
                b = middle - 1;
            if(n[middle].sum < sum)
                a = middle + 1;
        }
    }
 
    if(ok)
        fprintf(g, "-1");
 
    fclose(f);
    fclose(g);
    return 0;
}