Cod sursa(job #2289378)

Utilizator sabinpocrisSabin P sabinpocris Data 24 noiembrie 2018 15:11:10
Problema Loto Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> theNumbers;
vector<int> allSums;
bool itWorkedLeft = false;
bool itWorkedRight = false;
int nr, lucky;
string leftTicket = "";
string rightTicket = "";

ifstream in("loto.in");
ofstream out("loto.out");

void findSums(){
    int temp;
    for(int item1 : theNumbers)
        for (int item2 : theNumbers)
            for (int item3 : theNumbers){
                allSums.push_back(item1+ item2 + item3);
            }


    sort( allSums.begin(), allSums.end() );
    allSums.erase( unique( allSums.begin(), allSums.end() ), allSums.end() );
}

void findSum(int sum, string past, int limit, bool &test, char parte){

    if (sum > lucky || limit < 0 || test)
        return;
    
    if (sum == lucky && limit == 0){
        if (parte == 'l')
            leftTicket = past;
        else
            rightTicket = past;
        test = true;
        return;
    }

    for (int item : theNumbers){
        int temp = sum + item;
        string str;
        
        if (past == ""){
            str = to_string(item);
        } else {
            str = past + " " + to_string(item);
        }

        findSum(temp, str, limit - 1, test, parte);
    }
}

int main(){
    int n, temp;

    in >> n >> nr;
    while(n--){
        in >> temp;
        theNumbers.push_back(temp);
    }

    findSums();

    for (int i = 0, j = allSums.size() - 1; i <= j; ){
        if (allSums[j] > nr){
            j--;
        }
        
        int temp = allSums[i] + allSums[j];
        if (temp == nr){
            lucky = allSums[i];
            findSum(0, "", 3, itWorkedLeft, 'l');
            lucky = allSums[j];
            findSum(0, "", 3, itWorkedRight, 'r');
            if (itWorkedLeft && itWorkedRight){
                out << leftTicket << " " << rightTicket << endl;
                return 0;
            } else {
                itWorkedLeft = false;
                itWorkedRight = false;
                i++;
            }
        }

        if (temp > nr){
            j--;
        }

        if (temp < nr){
            i++;
        }
    }

    out << "-1\n";

    return 0;
}