Cod sursa(job #1969916)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 18 aprilie 2017 18:44:53
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdint.h>
#include <fstream>
#include <string.h>
#define nmax 101
#define smax 600000001
using namespace std;
fstream f1("loto.in", ios::in);
fstream f2("loto.out", ios::out);
int32_t a[nmax], nr, suma;
int16_t n, ok;
struct sumaa
{
    int32_t x, y, z, s;
}v[1000001], aux;
void cauta(int32_t st, int32_t dr, int32_t val, int32_t in)
{
    if(st<=dr)
    {
       int32_t mijl=(st+dr)/2;
       if(v[mijl].s==val) {ok=1; f2<<v[in].x<<" "<<v[in].y<<" "<<v[in].z<<" "<<v[mijl].x<<" "<<v[mijl].y<<" "<<v[mijl].z;}
       else if(v[mijl].s<val) cauta(mijl+1, dr, val, in);
            else cauta(st, mijl-1, val, in);
    }
}
int main()
{
    int32_t i, j, k, gap, val;
    f1>>n>>suma;
    for(i=1; i<=n; i++)
        f1>>a[i];
    for(i=1; i<=n; i++)
        for(j=i; j<=n; j++)
            for(k=j; k<=n; k++)
    {
        nr++;
        v[nr].s=a[i]+a[j]+a[k];
        v[nr].x=a[i];
        v[nr].y=a[j];
        v[nr].z=a[k];
    }
    ///sortezi cresc sumele
    for(gap=nr/2; gap>=1; gap/=2)
        for(i=gap+1; i<=nr; i++)
    {
        aux=v[i];
        for(j=i-gap; (j>=1)&&(v[j].s>v[i].s); j-=gap)
            v[j+gap]=v[j];
        v[j+gap]=aux;
    }
    ok=0;
    ///v[i].s<v[j].s
    for(i=1; (i<=nr)&&(!ok); i++)
    {
        val=suma-v[i].s;///valoare de cautat
        if(val<v[i].s) break;///nu ai solutie

        ///cauti binar val in intervalul i->nr
        cauta(i, nr, val, i);
    }

    if(!ok) f2<<-1;
    return 0;
}