Cod sursa(job #1180485)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 30 aprilie 2014 18:22:10
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<cstdio>
#include<algorithm>
using namespace std;
class Loto{
    public:
        int sum,x1,x2,x3;
        bool operator <(const Loto&l)const{
            return this->sum<l.sum;
        }
};
const int N=100;
Loto v[N*N*N+1];
int sc[N+1];
int n,s;
void scan(){
    int i;
    scanf("%d%d",&n,&s);
    for(i=1;i<=n;i++)
        scanf("%d",&sc[i]);
}
void setV(){
    int i,j,k,l=0;
    sort(sc+1,sc+n+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++){
                v[++l].sum=sc[i]+sc[j]+sc[k];
                v[l].x1=i;
                v[l].x2=j;
                v[l].x3=k;
            }
}
int bSearch(int sum){
    int l=1,r=n*n*n,m;
    while(l<r-1){
        m=(l+r)/2;
        if(v[m].sum==sum)
            return m;
        if(v[m].sum<sum)
            l=m;
        else
            r=m;
    }
    if(v[l].sum==sum)
        return l;
    if(v[r].sum==sum)
        return r;
    return 0;
}
void solve(){
    int i,j,k,sum,p;
    bool f=false;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++){
                sum=sc[i]+sc[j]+sc[k];
                p=bSearch(s-sum);
                if(p!=0){
                    f=true;
                    printf("%d %d %d %d %d %d",i,j,k,v[p].x1,v[p].x2,v[p].x3);
                    return;
                }
            }
    if(!f)
        printf("-1");
}
void init(){
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scan();
    setV();
}
int main(){
    init();
    solve();
    return 0;
}