Cod sursa(job #854067)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 12 ianuarie 2013 19:05:44
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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 crit(sp x, sp y) 
{
	return x.s < y.s;
}

int cautbin(int x)
{
    int l=1, r = w, m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(sume[m].s==x) return m;
        if(sume[m].s>x) r=m-1;
        if(sume[m].s<x) l=m+1;
    }
    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,crit);
	
    for(i=1;i<=w;i++)
    {
        sum=S-sume[i].s;
        sol=cautbin(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;
}