Cod sursa(job #1294889)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 18 decembrie 2014 13:49:53
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, sum, j, nr, p, u, mid, k, c;
int v[101], sol[7];
struct sp{
    int suma;
    int a;
    int b;
    int c;
};
int cmp(sp a, sp b){
    return a.suma < b.suma;
}
sp s[1100001];
ifstream fin("loto.in");
ofstream fout("loto.out");
int main(){
    fin>> n >> sum;
    for(i = 1; i <= n; i++){
        fin>> v[i];
    }
    for(i = 1; i <= n; i++){
        for(j = i; j <= n; j++){
            for(k = j; k <= n; k++){
                nr++;
                s[nr].suma = v[i] + v[j] + v[k];
                s[nr].a = v[i];
                s[nr].b = v[j];
                s[nr].c = v[k];
            }
        }
    }
    sort(s + 1, s + nr + 1, cmp);
    for(i = 1; i <= nr; i++){
        c = sum - s[i].suma;
        p = 1;
        u = nr;
        while(p <= u){
            mid = (p + u) / 2;
            if(s[mid].suma == c){
                break;
            }
            else{
                if(s[mid].suma > c){
                    u = mid - 1;
                }
                else{
                    p = mid + 1;
                }
            }
        }
        if(p <= u){
            sol[1] = s[i].a;
            sol[2] = s[i].b;
            sol[3] = s[i].c;
            sol[4] = s[mid].a;
            sol[5] = s[mid].b;
            sol[6] = s[mid].c;
            sort(sol + 1, sol + 7);
            for(j = 1; j <= 6; j++){
                fout<< sol[j] <<" ";
            }
            return 0;
        }
    }
    fout<< -1;
    return 0;
}