Cod sursa(job #1697530)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 2 mai 2016 13:01:55
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100

int v[MAXN], c3[MAXN*MAXN*MAXN][4];
void myqsort(int begin, int end){
    int b=begin, e=end, pivot=c3[(b+e)/2][0];
    while(b<=e){
        while(c3[b][0]<pivot) b++;
        while(c3[e][0]>pivot) e--;
        if(b<=e){
            int i;
            for(i=0;i<4;i++){
                int aux=c3[b][i];
                c3[b][i]=c3[e][i];
                c3[e][i]=aux;
            }
            b++; e--;
        }
    }
    if(b<end) myqsort(b, end);
    if(begin<e) myqsort(begin, e);
}

int main(){
    int n, s, i, j, k;
    FILE*fi,*fo;
    fi=fopen("loto.in","r");
    fo=fopen("loto.out","w");
    fscanf(fi,"%d%d", &n, &s);
    for(i=0;i<n;i++)
        fscanf(fi,"%d", &v[i]);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            for(k=0;k<n;k++){
                c3[i*n*n+j*n+k][0]=v[i]+v[j]+v[k];
                c3[i*n*n+j*n+k][1]=v[i];
                c3[i*n*n+j*n+k][2]=v[j];
                c3[i*n*n+j*n+k][3]=v[k];
            }
    myqsort(0, n*n*n-1);
    for(i=0;i<n*n*n-1;i++){
        if(s-c3[i][0]>=c3[0][0] && s-c3[i][0]<=c3[n*n*n-1][0]){
            int st=0, dr=n*n*n-1;
            while(dr-st>1){
                int m=(dr+st)/2;
                if(c3[m][0]>s-c3[i][0])
                    dr=m-1;
                else
                    st=m;
            }
            if(c3[st][0]==s-c3[i][0]){
                fprintf(fo,"%d %d %d %d %d %d", c3[i][1], c3[i][2], c3[i][3], c3[st][1], c3[st][2], c3[st][3]);
                return 0;
            }
            if(c3[dr][0]==s-c3[i][0]){
                fprintf(fo,"%d %d %d %d %d %d", c3[i][1], c3[i][2], c3[i][3], c3[dr][1], c3[dr][2], c3[dr][3]);
                return 0;
            }
        }
    }
    fprintf(fo,"-1");
    fclose(fi);
    fclose(fo);
    return 0;
}