Cod sursa(job #1058087)

Utilizator vlad233Dragan Vlad vlad233 Data 15 decembrie 2013 01:30:57
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
 
using namespace std;
 
long long v[101];
struct nr
{
    int a,b,c,sum;
};
 
void merge(int st, int x, int dr)
{
    int i,j,nr=0,a[500001];
    i=st;
    j=x+1;
    while (i<=x && j<=dr)
    {
        if (v[i]<v[j])
        {
            a[++nr]=v[i];
            i++;
        }
        else
        {
            a[++nr]=v[j];
            j++;
        }
    }
    while (i<=x)
    {
        a[++nr]=v[i];
        i++;
    }
    while (j<=dr)
    {
        a[++nr]=v[j];
        j++;
    }
    nr=0;
    for (i=st;i<=dr;i++)
        v[i]=a[++nr];
}
 
void mergesort(int s, int d)
{
    int x;
    if ((d-s)<1)
        return;
    else
    {
        x=(s+d)/2;
        mergesort(s,x);
        mergesort(x+1,d);
        merge(s,x,d);
    }
}
 
int cb(nr v[], int n, int x)
{
    int st=1,dr=n,m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x==v[m].sum)
            return m;
        else
            if(x<v[m].sum)
                dr=m-1;
            else
                st=m+1;
    }
    return -1;
}
 
int main()
{
    int n,i,j,k,s,x,p=0,ok=0;
    nr e[500001];
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>s;
	for (i=1;i<=n;i++)
		f>>v[i];
    mergesort(1,n);
    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++)
            {
                p++;
                e[p].a=v[i];
                e[p].b=v[j];
                e[p].c=v[k];
                e[p].sum=v[i]+v[j]+v[k];
            }
    for (i=1;i<=p && ok==0;i++)
    {
        x=cb(e,p,s-e[i].sum);
        if (x!=-1)
        {
            g<<e[i].a<<" "<<e[i].b<<" "<<e[i].c<<" "<<e[x].a<<" "<<e[x].b<<" "<<e[x].c;
            ok=1;
        }
    }
    if (ok==0)
        g<<-1;
    f.close();
    g.close();
    return 0;
}