Cod sursa(job #2267026)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 23 octombrie 2018 09:52:34
Problema Loto Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
const int MAX_SIZE = 102;
int v[MAX_SIZE];
int binarySearch(int n, int value){
    int left = 1, right = n, middle;
    while(left <= right){
        middle = (left + right) / 2;
        if(v[middle] == value)
            return middle;
        if(v[middle] < value)
            left = middle + 1;
        else
            right = middle - 1;
    }
    return -1;
}
void solve(int n, int sum){
    int f;
    for(int a=1;a<=n && 6*v[a] <= sum;a++)
        for(int b=1;b<=n && v[a]+v[b] <= sum;b++)
            for(int c=1;c<=n && v[a]+v[b]+v[c] <= sum;c++)
                for(int d=1;d<=n && v[a]+v[b]+v[c]+v[d] <= sum;d++)
                    for(int e=1;e<=n && v[a]+v[b]+v[c]+v[d]+v[e] <= sum;e++){
                        f = binarySearch(n,sum - (v[a]+v[b]+v[c]+v[d]+v[e]));
                        if(f != -1){
                            out<<v[a]<<" "<<v[b]<<" "<<v[c]<<" "<<v[d]<<" "<<v[e]<<" "<<v[f]<<"\n";
                            return ;
                        }
                    }
    out<<"-1\n";
}
int main()
{
    int n, sum;
    bool found = false;
    in>>n>>sum;
    for(int i=1;i<=n;i++){
        in>>v[i];
        if(v[i] * 6 == sum){
            for(int j=1;j<=6;j++)
                out<<v[i]<<" ";
            found = true;
        }
    }
    in.close();
    if(found == false){
        sort(v+1,v+n+1);
        if(v[1] * 6 > sum || v[n] * 6 < sum)
            out<<"-1\n";
        else
            solve(n,sum);
    }
    out.close();
    return 0;
}