Cod sursa(job #1424632)

Utilizator dm1sevenDan Marius dm1seven Data 25 aprilie 2015 09:05:45
Problema Loto Scor 80
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;
    if (numbers * v[pos] < S) return false;
    
    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;
                else a = m + 1;
            }

            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";

    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();

    //sort the numbers
    std::sort(v.begin(), v.end());
    
    //win the lottery
    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();
}