Cod sursa(job #1795307)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 2 noiembrie 2016 10:46:11
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <time.h>

using namespace std;

vector<int> V;
int S, N;

void Read();
void Solve();
void RandomQuickSort(int left, int right);
void Swap(int &a, int &b) {     int c = a; a = b; b = c;    };

int main()
{
    Read();
    Solve();
    return 0;
}
void Solve() {
    bool found = 0;
    RandomQuickSort(1, N);
    for(int a = 1; a <= N && !found && 6*V[a] <= S; a++)
        if(V[a] + 5 * V[N] >= S)
        for(int b = a; b <= N && !found && V[a] + 5*V[b] <= S; b++)
            if(V[a] + V[b] + 4 * V[N] >= S)
            for(int c = b; c <= N && !found && V[a] + V[b] + 4*V[c] <= S; c++)
                if(V[a] + V[b] + V[c] + 3 * V[N] >= S)
                for(int d = c; d <= N && !found && V[a] + V[b] + V[c] + 3*V[d] <= S; d++)
                    if(V[a] + V[b] + V[c] + V[d] + 2 * V[N] >= S)
                    for(int e = d; e <= N && !found && V[a] + V[b] + V[c] + V[d] + 2*V[e] <= S; e++)
                        if(V[a] + V[b] + V[c] + V[d] + V[e] + V[N] >= S)
                        for(int f = e; f <= N && !found && V[a] + V[b] + V[c] + V[d] + V[e] + V[f] <= S; f++)
                            if(V[a] + V[b] + V[c] + V[d] + V[e] + V[f] == S) {
                                found = true;
                                cout << V[a] << ' ' << V[b] << ' ' << V[c] << ' ';
                                cout << V[d] << ' ' << V[e] << ' ' << V[f] << '\n';
                            }
    if(!found)
        cout << -1 << '\n';
}
void RandomQuickSort(int left, int right) {
    if(left >= right)
        return;
    int piv = rand() % (right - left + 1) + left;
    Swap(V[right], V[piv]);
    piv = left - 1;
    for(int j = left; j < right; j++)
        if(V[j] <= V[right]) {
            piv++;
            Swap(V[piv], V[j]);
        }
    piv++;
    Swap(V[piv], V[right]);
    RandomQuickSort(left, piv - 1);
    RandomQuickSort(piv + 1, right);
}
void Read() {
    freopen("loto.in", "rt", stdin);
    freopen("loto.out", "wt", stdout);
    scanf("%d%d", &N, &S);
    V.assign(N+2, 0);
    srand(time(NULL));
    for(int i = 1; i <= N; i++)
        scanf("%d", &V[i]);
}