Cod sursa(job #735948)

Utilizator Theorytheo .c Theory Data 17 aprilie 2012 16:11:40
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define n1 102
#define n2 10002
#define n3 1000005
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
int i, j, v[n1], a[3][n2] , b[4][n3], n, S, k, Nr, poz ,ok =0;
int bs(int x)
{
    int  p =1, u = Nr;
    int m;
    while( p <= u)
    {
        m = ( p+ u )/2;
        if(x >= b[0][m])

            p = m + 1;

        else
            u = m - 1;
    }
    m = (p + u)/2;
    if(x<b[0][m])
        --m;
    if(x==b[0][m])
        return m;
        return 0;
}

void read()
{
    fin >>n >>S;
    for(i = 1 ;i <= n; i++)
        fin>> v[i];
    for(i =1; i <= n ;i++)
    {

        for(j = 1 ; j <= n; j++)
        {
            a[0][++k] = v[i] + v[j];
            a[1][k] = v[i];
            a[2][k] = v[j];
            //fout<< a[k][0] <<" ";
        }
    }
     for(i =1; i <= k ;i++)
    {

        for(j = 1 ; j <= n; j++)
        {
            b[0][++Nr] = a[0][i] + v[j];
            b[1][Nr] = a[1][i];
            b[2][Nr] = a[2][i];
            b[3][Nr] = v[j];

        }
    }
    sort(b[0] + 1 ,b[0] + 1 +Nr);
    for(i = 1 ;i <= Nr; i++)
    {
        poz =  bs(S - b[0][i]);

        if( poz)
        {
            fout << b[1][poz] <<" " << b[2][poz] <<" " <<b[3][poz];
            fout << " " << b[1][i] <<" " << b[2][i] <<" "<< b[3][i] ;
            ok = 1;
            break;
        }
    }
    if(!ok)
    fout << -1;



}
int main()
{
    read();
    fin.close();
    fout.close();
    return 0;

}