Cod sursa(job #854775)

Utilizator TripluYOlteanu Costin TripluY Data 13 ianuarie 2013 23:26:23
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

unsigned int n,numere[100];
long long s;


struct set
{
    long long suma;
    unsigned int primul_numar,doilea_numar;
};
vector <set> sume;

inline void citire()
{
    ifstream f("loto.in");
    f>>n>>s;
    for(unsigned int i=0;i<n;++i)
        f>>numere[i];
    f.close();
}

void qsort(int start,int sfarsit)
{
    int i=start,j=sfarsit,pivot=(sfarsit-start)/2;
    if(start>=sfarsit || sfarsit-start==1)
        return;
    while(i<=j)
    {
        if(numere[i]<numere[pivot])
            {++i;continue;}
        while(j>pivot && numere[j]>numere[pivot])
            {--j;continue;}
            swap(numere[i],numere[j]);
        ++i;--j;
    }
    qsort(start,j);
    qsort(i,sfarsit);
}

inline void cautare()
{
    int start=0,sfarsit=sume.size()-1,cauta;
    while(start<=sfarsit)
    {
        cout<<start<<" "<<sfarsit<<endl;
        if(sume[start].suma + sume[sfarsit].suma == s)
        {
            ofstream g("loto.out");
            g<<sume[start].primul_numar<<" "<<sume[start].doilea_numar<<" "<<sume[start].suma-sume[start].primul_numar-sume[start].doilea_numar<<" "<<sume[sfarsit].primul_numar<<" "<<sume[sfarsit].doilea_numar<<" "<<sume[sfarsit].suma-sume[sfarsit].primul_numar-sume[sfarsit].doilea_numar;
            g.close();
            return;
        }
        if(sfarsit == 0)
            break;
        if(sume[start].suma + sume[sfarsit].suma  < s)
        {
            cauta = start<<1;
            if(sume[cauta].suma + sume[cauta].suma <= s && start!=0)
                start = cauta;
            else
                ++start;
            continue;
        }
        cauta = sfarsit>>1;
        if(sume[start].suma + sume[cauta].suma >= s)
            sfarsit = cauta;
        else
            --sfarsit;
    }
    ofstream g("loto.out");
    g<<"-1";
    g.close();
}

int main()
{
    citire();
    qsort(0,n-1);
    set inserare;
    unsigned int i,j,k;
    for(i=0;i<n;++i)
        for(j=i;j<n;++j)
            for(k=j;k<n;++k)
            {
                inserare.primul_numar=numere[i];
                inserare.doilea_numar=numere[j];
                inserare.suma=numere[i]+numere[j]+numere[k];
                sume.push_back(inserare);
            }
    cautare();
    return 0;
}