Cod sursa(job #2784825)

Utilizator lolismekAlex Jerpelea lolismek Data 17 octombrie 2021 14:18:32
Problema Loto Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
/*
        _
      |>(|)<|
      .-'^'-.
     '/"'"^"\'
    :( *   * ):
    ::)  ,| (::
    '(       )'          _.
     '\ --- /'          / /
   .-'       '-.      .__D
 ,"      |      \    / : (=|
:   Y    |    \  \  /  : (=|
|   |o__/ \__o:   \/  " \ \
|   |          \     '   "-.
|    `.    ___ \:._.'
 ".__  "-" __ \ \
  .|''---''------|               _
  / -.          _""-.--.        C )
 '    '/.___.--'        '._    : |
|     --_   ^"--...__      ''-.' |
|        ''---.o)    ""._        |
 ^'--.._      |o)        '`-..._.
        '--.._|o)
              'O)

             /// MAIMUTA SACRA APARA ACEST COD!!! \\\
**/




#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

const int N = 100;
int loto[N];
int sume3[N * N * N];

int main()
{
    int n, s, i, j, k, len, st, dr ,mij, target, s1, s2, ok, sum_test, ok1, ok2;
    fin >> n >> s;
    for(i = 0; i < n; i++){
        fin >> loto[i];
    }
    len = 0;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            for(k = 0; k < n; k++){
                sume3[len] = loto[i] + loto[j] + loto[k];
                len++;
            }
        }
    }

    sort(sume3, sume3 + len);

    ok = 1;
    for(i = 0; i < len && ok == 1; i++){
        target = s - sume3[i];
        st = 0;
        dr = len;
        while(dr - st > 1){
            mij = (st + dr) / 2;
            if(sume3[mij] > target)
                dr = mij;
            else
                st = mij;
        }
        if(sume3[st] == target){
            s1 = sume3[i];
            s2 = sume3[st];
            ok = 0;
        }
    }
    if(ok == 1){
        fout << -1;
    }else{
        /// reconstituim s1 si s2
        ok = 0;
        ok1 = ok2 = 0;
        for(i = 0; i < n && ok < 2; i++){
            for(j = 0; j < n && ok < 2; j++){
                for(k = 0; k < n && ok < 2; k++){
                    sum_test = loto[i] + loto[j] + loto[k];
                    if(sum_test == s1 && ok1 == 0){
                        fout << loto[i] << " " << loto[j] << " " << loto[k] << " ";
                        ok++;
                        ok1 = 1;
                    }
                    if(sum_test == s2 && ok2 == 0){
                        fout << loto[i] << " " << loto[j] << " " << loto[k];
                        ok++;
                        ok2 = 1;
                    }
                }
            }
        }
    }
    return 0;
}