Cod sursa(job #1009820)

Utilizator nod_softwareBudisteanu Ionut Alexandru nod_software Data 13 octombrie 2013 21:26:43
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

std::vector<int>_vTickets;

struct TSuma
{
    int iSuma,iIndex1,iIndex2,iIndex3;

    TSuma(int iNewSuma, int iNewIndex1, int iNewIndex2,int iNewIndex3)
    {
       iSuma=iNewSuma;
       iIndex1=iNewIndex1; iIndex2=iNewIndex2;
       iIndex3=iNewIndex3;
    }
    bool operator<(const TSuma& another) const
    {
        return iSuma<another.iSuma;
    }
    bool operator==(const TSuma& another) const
    {
        return iSuma==another.iSuma;
    }
};

std::vector <TSuma> _vSumTriplets;

//----------------------------------------------------
void PrintSumTriplets()
{
    std::vector<TSuma>::iterator it;

    it=_vSumTriplets.begin();
    while (it!=_vSumTriplets.end())
    {
       TSuma el=*it;
       printf("%d %d %d %d \n",el.iSuma,el.iIndex1,el.iIndex2,el.iIndex3);

       it++;
    }
}
//----------------------------------------------------
void citire(int *iSuma)
{
    FILE * fin = fopen("loto.in","r");
    int iN;

    fscanf(fin,"%d %d",&iN,iSuma);
    int iNumber;

    for (int i=0; i<iN; i++)
    {
       fscanf(fin,"%d",&iNumber);
       if (iNumber <= *iSuma)
          _vTickets.push_back(iNumber);
    }

    fclose(fin);
}
//----------------------------------------------------
int binary_search2(int iIndexLeft, int iIndexRight, int iSum)
{
    if (iIndexLeft==iIndexRight)
    {
        if (_vSumTriplets[iIndexLeft].iSuma==iSum)
            return iIndexLeft;
        else
            return -1;

    } else
    {
        if (iSum<=_vSumTriplets[(iIndexLeft+iIndexRight) / 2].iSuma)
            return binary_search2(iIndexLeft,((iIndexLeft+iIndexRight) / 2),iSum);
        else
            return binary_search2(((iIndexLeft+iIndexRight) / 2)+1,iIndexRight,iSum);
    }
}
//----------------------------------------------------
int main()
{
    int iSuma;
    citire(&iSuma);
    int i,j,q,iS,iS2,iS3;
    for (i=0; i<_vTickets.size(); i++)
        for (j=0; j<_vTickets.size(); j++)
        {
            iS2=_vTickets[i]+_vTickets[j];

            if (iS2<=iSuma)
            for (q=0; q<_vTickets.size(); q++)
            {
               iS=iS2+_vTickets[q];

               if (iS<=iSuma)
               {
                  TSuma NewElement=TSuma(iS,i,j,q);

                  _vSumTriplets.push_back(NewElement);
               }
            }
        }

    sort(_vSumTriplets.begin(),_vSumTriplets.end());

    FILE * fout = fopen("loto.out","w");
    //PrintSumTriplets();

    int iDiff;
    for (i=0; i<_vTickets.size(); i++)
        for (j=0; j<_vTickets.size(); j++)
            for (q=0; q<_vTickets.size(); q++)
            {
               iS=_vTickets[i]+_vTickets[j]+_vTickets[q];

               iDiff=iSuma-iS;

               //fara binary_search din STL pt scoala
               //TSuma elElement=TSuma(iDiff,1,1,1);
               //binary_search(_vTickets.begin(),_vTickets.end(),elElement);
               //if (it!=_vSumTriplets.end())



               int iIndex=binary_search2(0,_vSumTriplets.size()-1,iDiff);
               if (iIndex!=-1)
               {
                   //elElement=*it;
                   fprintf(fout,"%d %d %d %d %d %d",_vTickets[i],_vTickets[j],_vTickets[q],
                           _vTickets[_vSumTriplets[iIndex].iIndex1],_vTickets[_vSumTriplets[iIndex].iIndex2],
                           _vTickets[_vSumTriplets[iIndex].iIndex3]);

                   fclose(fout);

                   return 0;
               }

            }

    fprintf(fout,"-1");
    fclose(fout);

    return 0;
}