Cod sursa(job #2674230)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 18 noiembrie 2020 20:36:40
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <bits/stdc++.h>
#define NMAX 6500000
using namespace std;

/**************************************************/
/// INPUT / OUTPUT

ifstream f("loto.in");
ofstream g("loto.out");
/**************************************************/
/// GLOBAL DELCARATIONS

int n, target, foundSum = -1;
int sum, diff;
int arr[105];

bool freq[NMAX];

vector < int > ans;
/**************************************************/
///-----------------------------------------------------------------
inline void ReadInput()
{
    f >> n >> target;
    for(int i = 1 ; i <= n ; ++ i) f >> arr[i];
}
///-----------------------------------------------------------------
inline void FindFirstSum()
{
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = i ; j <= n ; ++ j)
        {
            for(int k = j ; k <= n ; ++ k)
            {
                sum = arr[i] + arr[j] + arr[k];
                diff = target - sum;
                if(freq[diff])
                {
                    foundSum = diff;
                    ans.push_back(arr[i]);
                    ans.push_back(arr[j]);
                    ans.push_back(arr[k]);
                    return;
                }
                else
                {
                    if(!freq[sum]) freq[sum] = 1;
                }
            }
        }
    }
}
///-----------------------------------------------------------------
inline void FindSecondSum()
{
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = i ; j <= n ; ++ j)
        {
            for(int k = j ; k <= n ; ++ k)
            {
                sum = arr[i] + arr[j] + arr[k];
                if(sum == foundSum)
                {
                    ans.push_back(arr[i]);
                    ans.push_back(arr[j]);
                    ans.push_back(arr[k]);
                    return;
                }
            }
        }
    }
}
///-----------------------------------------------------------------
inline void Solution()
{
    /// get every sum possible
    FindFirstSum();
    if(foundSum == -1) return;
    /// find the sum that 'completes' the other half
    FindSecondSum();
}
///-----------------------------------------------------------------
inline void Output()
{
    if(foundSum == -1) g << "-1";
    for(auto it: ans) g << it << " ";
}
///-----------------------------------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}