Cod sursa(job #555221)

Utilizator acelasi7Tudor Maxim acelasi7 Data 15 martie 2011 12:44:43
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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;
bool ok=true;

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;
            else if(V[mid].val<=M.val)
            lf=mid+1;
        }
    }
    if(M.val>-1)
    {
        k-=M.val;
        SOL[pas]=M.index;
    }
    else ok=false;
}
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&&ok;++i)
        cbin(i);
    if(!k&&ok)
        for(i=1;i<=6;++i)
            fprintf(out,"%d ",V[SOL[i]].val);
    else fprintf(out,"-1 ");
    return 0;
}