Cod sursa(job #1022877)

Utilizator WyvernFMI Stanescu Leonard Wyvern Data 6 noiembrie 2013 08:17:23
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fi("loto.in");
ofstream fo("loto.out");
struct valori {
int a,b,c,suma;};
int v[101],s,x,y,nr;
short n;
valori w[1000002];

void qsort(int st, int dr)
{
      int i=st, j=dr;
      int piv = w[(st+dr)/2].suma;
      while (i <= j)
      {
            while (w[i].suma<piv)
                i++;
            while (w[j].suma>piv)
                j--;
            if (i<=j)
            {
                  swap(w[i].suma,w[j].suma);
                  i++;
                  j--;
            }
      }
      if (st<j) qsort(st, j);
      if (i<dr) qsort(i, dr);
}

int cautbin(int i,int j,int x) {
    int m=(i+j)/2;
    if (m==i) {
        if (w[m+1].suma==x)
            return m+1;
        else
            if (w[m].suma==x)
                return m;
            else
                return -1;
    }
    else {
        if (w[m].suma<x)
            cautbin(m,j,x);
        else
            cautbin(i,m,x);
    }

}

int main()
{
    fi>>n>>s;
    for (int i=1;i<=n;i++) {
        fi>>v[i];
        if (v[i]*6==s)
            x=v[i];
        if (v[i]>y)
            y=v[i];
    }
    if (x!=0)
        for (int i=1;i<=6;i++)
            fo<<x<<' ';
    else
        if (y*6<s)
            fo<<'-1';
        else {
            for (int i=1;i<=n;i++)
                for (int j=i;j<=n;j++)
                    for (int k=j;k<=n;k++)
                        if (v[i]+v[j]+v[k]<s-3) {
                            nr++;
                            w[nr].a=v[i];
                            w[nr].b=v[j];
                            w[nr].c=v[k];
                            w[nr].suma=v[i]+v[j]+v[k];
                    }
            x=0;y=0;
            qsort(1,nr);
            for (int i=nr;i>=1;i--)
                if (w[i].suma+w[cautbin(1,nr,s-w[i].suma)].suma==s) {
                    x=i;
                    y=cautbin(1,nr,s-w[i].suma);
                }
            if (x==0)
                fo<<-1;
            else
                fo<<w[x].a<<' '<<w[x].b<<' '<<w[x].c<<' '<<w[y].a<<' '<<w[y].b<<' '<<w[y].c;
        }
    return 0;
}