Cod sursa(job #422074)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 22 martie 2010 09:37:56
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#include<algorithm>
#include<cmath>

#define maxn 102
#define maxm 161704
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define INFI 2147483640
using namespace std;

struct lol{
    int s, poz;
    friend bool operator < (const lol &a, const lol &b){
        return a.s<b.s;}
};

int n, S, v[maxn], x[4], nrc=0;
//int sol[maxm][4];
lol a[maxm];

void citire();

void afis()
{
    nrc++;
    for(int i=1;i<=3;i++)
    {
        a[nrc].s+=v[x[i]];
        a[nrc].poz=nrc;
        sol[nrc][i]=x[i];
    }
}

void back(int k)
{
    if(k>3)
        afis();
    else
        for(int i=x[k-1]; i<=n;i++)
        {
            x[k]=i;
            back(k+1);
        }
}

void write()
{
    int i,j;
    for(i=1;i<=nrc;i++)
    {
        for(j=1;j<=3;j++)
            printf("%d ", sol[i][j]);
        printf(" = %d %d\n", a[i].s, a[i].poz);
    }
}

int cauta(int st, int dr, int X)
{
    int mij=(st+dr)/2;
    if(a[mij].s==X)
        return mij;
    else if(st==dr)
        return 0;
    else if(a[mij].s>X)
        return cauta(st, mij-1,X);
    else if(a[mij].s<X)
        return cauta(mij+1, dr,X);
}

void solve()
{
    int i,pp=0;
    for(i=1;i<=nrc && !pp;i++)
    {
        if(i>1 && a[i-1].s==a[i].s)
            i++;
        if(i<=n)
            pp=cauta(1,nrc,S-a[i].s);
    }
    if(pp)
    {
        i--;
        int p1=a[i].poz, p2=a[pp].poz;
        for(i=1;i<=3;i++)
            printf("%d ", v[sol[p1][i]]);
        for(i=1;i<=3;i++)
            printf("%d ", v[sol[p2][i]]);
    }
    else
        printf("-1");
}

int main()
{
    freopen("loto.out","w",stdout);
    citire();
    back(1);
    sort(a+1, a+nrc+1);
    //solve();
    return 0;
}

void citire()
{
    int i;
    ifstream fin("loto.in");
    fin>>n>>S;
    x[0]=1;
    for(i=1;i<=n;i++)
        fin>>v[i];
    sort(v+1, v+n+1);
    fin.close();
}