Cod sursa(job #379289)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 31 decembrie 2009 16:09:08
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#define inf "loto.in"
#define outf "loto.out"
#define NMax 101
#define SMax 300000001
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int v[NMax];
int s[SMax];
int N,S,nr;

void Citire()
{
f>>N>>S;
for(int i=1;i<=N;i++)f>>v[i];
}

void Refa(int sum)
{
for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++)
        for(int k=1;k<=N;k++)
            if(v[i]+v[j]+v[k]==sum)
                {
                g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
                return;
                }
}

void Rezolva()
{
for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++)
        for(int k=1;k<=N;k++)s[++nr]=v[i]+v[j]+v[k];//fac toate sumele posibile cu 3 cifre
int li,ls,p;
for(int k=1;k<=nr;k++)
    {
    li=1;
    ls=nr;
    //cautare binara dupa S-s[k]
    while(li<=ls)
        {
        p=(li+ls)/2;
        if(s[p]==S-s[k])
            {//am gasit, refac sumele
            Refa(s[k]);
            Refa(S-s[k]);
            return;
            }
        else
            {
            if(S-s[k]<s[p])ls=p-1;
            else li=p+1;
            }
        }
    }
g<<"-1";
}

int main()
{
Citire();
Rezolva();
f.close();
g.close();
return 0;
}