Cod sursa(job #854059)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 12 ianuarie 2013 18:40:48
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<algorithm>

using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");

int n, S, i, j, k, v[101], sum, w, sol;

struct sp {int a, b, s;};
sp sume[1000001];

int comp(sp x, sp y) 
{
	return x.s < y.s;
}

int cautbin(int st, int dr, int x)
{
	if( st < dr )
	{
		int m= (st+dr)/2;
		if( sume[m].s == x )
			return m;
		else
		{
			if( sume[m].s > x )
				cautbin(1, m-1, x);
			else
				cautbin(m+1, dr, x);
		}
	}
    return -1;
}
int main()
{
    f>>n>>S;
    for(i=1;i<=n;i++)
		f>>v[i];
	
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                sum=v[i]+v[j]+v[k];
                w++;
                sume[w].a=v[i];
                sume[w].b=v[j];
                sume[w].s=sum;
            }
			
    sort(sume+1,sume+w+1,comp);
	
    for(i=1;i<=w;i++)
    {
        sum=S-sume[i].s;
        sol=cautbin(1, w, sum);
        if( sol != -1)
        {
			g<<sume[i].a<<" "<<sume[i].b<<" "<<sume[i].s-sume[i].a-sume[i].b<<" "<<sume[sol].a<<" "<<sume[sol].b<<" "<<sume[sol].s-sume[sol].a-sume[sol].b;
            return 0;
        }
    }
    g<<-1;
    return 0;
}