Cod sursa(job #555068)

Utilizator acelasi7Tudor Maxim acelasi7 Data 15 martie 2011 11:34:21
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define nrn 105
#define ll long long

struct vec{ll val;int index;};
vec V[nrn];
int n,SOL[nrn];
ll k;

FILE *in=fopen("loto.in","r"),*out=fopen("loto.out","w");

int bun(int pas,int val)
{
    if(6-pas)
        return val/(6-pas);
    return 1;
}
void cbin(int pas)
{
    int lf=1,rt=n,mid;
    vec M;
    M.val=-1;
    while(lf<=rt)
    {
        mid=(rt+lf)/2;
        if(V[mid].val<=k&&V[mid].val>M.val)
        {
            if(pas<6&&!bun(pas,k-V[mid].val))
            {
                rt=mid-1;
                continue;
            }
            M=V[mid];
            lf=mid+1;
        }
        else
        {
            if(V[mid].val>k||!bun(pas,k-V[mid].val))
            rt=mid-1;
        }
    }
    k-=M.val;
    SOL[pas]=M.index;
}
int cmp(vec a,vec b)
{
    return a.val<b.val;
}
int main()
{
    int i;
    fscanf(in,"%d %lld",&n,&k);
    for(i=1;i<=n;++i)
    {
        fscanf(in,"%lld",&V[i].val);
        V[i].index=i;
    }
    sort(V+1,V+n+1,cmp);
    for(i=1;i<=6;++i)
        cbin(i);
    if(!k)
        for(i=1;i<=6;++i)
            fprintf(out,"%d ",SOL[i]);
    else fprintf(out,"-1 ");
    return 0;
}