Cod sursa(job #1424327)

Utilizator dm1sevenDan Marius dm1seven Data 23 aprilie 2015 23:27:29
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

typedef vector<int> container;

bool find_loto(container& v, int numbers, int S, int pos, container& sol)
{
    if (S == 0 && numbers != 0) return false;
    if (S > 0 && numbers <= 0) return false;
    if (S < 0) return false;
    if (S == 0 && numbers == 0) return true;
    
    bool found = false;
    
    int pos2 = pos;
    while (!found && pos2 >= 0) 
    {
        ///find the first id between pos and 0 such that v[pos2] <= S        
        while (pos2 >= 0 && v[pos2] > S) pos2--;
        if (pos2 < 0) return false;
        //perform binary search instead of while
//        if (v[pos2] > S) 
//        {
//            int a = 0, b = pos2;
//            while (a < b) 
//            {
//                int m = (a + b) / 2;
//                if (v[m] > S) b = m - 1;
//                else a = m;
//            }
//
//            if (a != b) return false;
//            else pos2 = b;
//        }
        
        found = find_loto(v, numbers - 1, S - v[pos2], pos2, sol);
        if (found) sol.push_back(v[pos2]);
        else pos2--;
    } 
    
    return found;
}

//int loto()
int main()
{
    string in_file = "loto.in";
    string out_file = "loto.out";
    
    const int MAX_N = 100;
    int N, S;
    
    container v;
        
    //read data from file
    ifstream ifs;
    ifs.open(in_file.c_str());
    ifs >> N >> S;
    v.resize(N);
    for (int i = 0; i < N; i++)  ifs >> v[i];
    ifs.close();

    //data available, now win the lottery
    std::sort(v.begin(), v.end());
    
    container sol;
    bool found = find_loto(v, 6, S, N-1, sol);
    
    ofstream ofs;
    ofs.open(out_file.c_str());
    if (!found) ofs << -1;
    else for (auto& a : sol) ofs << a << " ";
    ofs.close();
}