Cod sursa(job #1851404)

Utilizator bobotheslayerBogdan Zaharia bobotheslayer Data 19 ianuarie 2017 18:26:03
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <fstream>
#include <algorithm>
using namespace std;

int v[101],suma[300000000],lungime=0,st=1,dr=300000000,mij=0,n,a=0,b=0,c=0;

void indici (int t)
{
    int i,j,k;
    for (i=1; i<=n; ++i)
    {
        for (j=i; j<=n; ++j)
        {
            for (k=j; k<=n; ++k)
            {
                if (v[i]+v[j]+v[k]==t)
                {
                    a=i;
                    b=j;
                    c=k;
                    return;
                }
            }
        }
    }
}

bool cautbin (int t)
{
    while(st<dr)
    {
        mij=(st+dr)/2;
        if (suma[mij]==t)
        {
            return true;
        }
        else
        {
            if (suma[mij]<t)
            {
                st=mij+1;
            }
            else
            {
                if (suma[mij]>t)
                {
                    dr=mij;
                }
            }
        }
    }
    if (suma[st]==t || suma[dr]==t)
        return true;
    return false;
}

int main()
{
    ifstream intrare("loto.in");
    ofstream iesire ("loto.out");
    int i,j,k,s,numsum=1,t=0;
    intrare>>n>>s;
    for (i=1; i<=n; ++i)
    {
        intrare>>v[i];
    }

    sort(v,v+n+1);

    for (i=1; i<=n; ++i)
    {
        for (j=i; j<=n; ++j)
        {
            for (k=j; k<=n; ++k)
            {
                suma[numsum]=v[i]+v[j]+v[k];
                numsum++;
                lungime++;
            }
        }
    }
    dr=lungime;
    sort(suma,suma+lungime);

    for (i=1; i<=n; ++i)
    {
        for (j=i; j<=n; ++j)
        {
            for (k=j; k<=n; ++k)
            {
                t=s-(v[i]+v[j]+v[k]);
                //cout<<t<<" "<<cautbin(t)<<"\n";
                if (cautbin(t)==true)
                {
                    indici(t);
                    iesire<<i<<" "<<j<<" "<<k<<" "<<a<<" "<<b<<" "<<c;
                    return 0;
                }
            }
        }
    }
    iesire<<"-1";
}