Cod sursa(job #475968)

Utilizator andra23Laura Draghici andra23 Data 9 august 2010 14:33:34
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

int a[105];
int sum[1000010], l;

int bsearch(int p, int u, int x){
    int m, poz = -1;
    while ( p <= u){
        m = (p+u)/2;   
        if (sum[m] <= x){
            poz = m;
            p = m+1;
        }
        else
            u = m-1;
    }   
    if (poz == -1 || sum[poz] != x)
        return -1;
    return poz;
}

int main(){
    ifstream f("loto.in");
    ofstream g("loto.out");
    int n, s, i, j, k;
    f>>n>>s;
    
    for (i = 0; i < n; i++)
        f>>a[i]; 
        
    l = 0;  
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            for (k = 0; k < n; k++){
                sum[l] = a[i]+a[j]+a[k];
                l++;
            }
            
    sort(sum, sum+l);
    
    int poz, s1, s2 = -1;            
    for (i = 0; i < l; i++)
        if (sum[i] < s){
            s1 = s - sum[i];
            poz = bsearch(0, l-1, s1);  
            if ( poz != -1){
                s2 = sum[i];
                break;
            }
        }
        else 
            break;
            
    if (s2 == -1)
        g<<s2<<'\n';
    else {
        int cod1 = 0, cod2 = 0;
        for (i = 0; i < n; i++){
            for (j = 0; j < n; j++){
                for (k = 0; k < n; k++){
                    if (cod1 == 0 && s1 == a[i]+a[j]+a[k]){
                        g<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
                        cod1 = 1;
                    }
                    if (cod2 == 0 && s2 == a[i]+a[j]+a[k]){
                        g<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
                        cod2 = 1;
                    }
                    if (cod1*cod2 == 1)
                        break;
                }
                if (cod1*cod2 == 1)
                    break;
            }
            if (cod1*cod2 == 1)
                break;
        }
    }
    g<<'\n';
    
    return 0;
}