# PBinfo #4301 – gustare – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
A venit ora mesei pentru Por Costel (masa dintre prânz și cină). Scormonind printr-o grădină, el descoperă un număr de N coceni de porumb și M mere. Masa lui Por Costel va consta în exact un cocean și un măr. Însă, mai nou, fanii săi l-au atenționat că trebuie să aibă grijă ce mănâncă. Fiecare cocean și fiecare măr are o valoare nutritivă. Valoarea nutritivă a mesei va fi valoarea nutritivă a coceanului ales + valoarea nutritiva a mărului ales. Dându-se valorile nutritive ale cocenilor și ale merelor, Por Costel vă întreabă dacă există o masă pe care o poate lua cu valoare nutritivă X. Pentru că Por Costel vrea sa mănânce de mai multe ori între prânz și cină, el va vă pune T întrebări de forma aceasta.
(Întrebările sunt independente între ele, a nu se considera că după o întrebare se elimină perechea cocean-mar aleasă).

Date de intrare
Pe prima linie a fișierului gustare.in se găsește un număr natural N: numărul de coceni. Pe a doua linie se găsește o secvență de N numere naturale separate prin câte un spațiu (valorile nutritive ale cocenilor). Pe a treia linie se găsește un număr natural M: numărul de mere. Pe a patra linie se găsește o secvență de M numere naturale separate prin câte un spațiu (valorile nutritive ale merelor). Pe a cincea linie se găsește un număr natural T, numărul de întrebări ale lui Por Costel. Pe a sasea linie se gasește o secvență de T numere naturale separate prin câte un spațiu, al i-lea număr fiind valoarea dorită pentru cea de a i-a masă.

Date de ieșire
În fișierul gustare.out se vor scrie T linii corespunzătoare celor T întrebări. A i-a linie va conține mesajul DA dacă se poate forma valoarea nutritivă pentru a i-a masă și NU în caz contrar.

Restricții și precizări

N, M ≤ 500.000
T ≤ 100
0 ≤ valoare nutritiva a unui aliment ≤ 1.000.000.000
0 ≤ valoarea X a unei intrebari ≤ 2.000.000.000
Pentru 20 de puncte, N, M ≤ 1000
Pentru alte 50 de puncte, T ≤ 20

Exemplu:
gustare.in

4
2 2 3 5
3
2 4 6
5
6 20 10 11 7
gustare.out

DA
NU
NU
DA
DA

## Cod sursă C++

```cpp
/*
Solutie de 70 puncte. Complexitate O(T*N*logM + MlogM)
- sortare + cautare binara pe fiecare linie
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const char InFile[]="gustare.in";
const char OutFile[]="gustare.out";
const int MaxN=100111;
int N,M,T;
int V1[MaxN],V2[MaxN];
int X;
inline void Precompute()
{
    sort(V2+1,V2+1+M);
}
inline bool BinarySearch(const int &val)
{
    int first=0;
    int step=1<<16;
    for(;step;step>>=1)
    {
        int index=first+step;
        if(index<=M)
        {
            if(V2[index]<=val)
            {
                first=index;
            }
        }
    }
    if(first==0)
    {
        return false;
    }
    return val==V2[first];
}
inline bool Query(const int &val)
{
    for(int i=1;i<=N;++i)
    {
        if(BinarySearch(val-V1[i]))
        {
            return true;
        }
    }
    return false;
}
int main()
{
    freopen(InFile,"r",stdin);
    freopen(OutFile,"w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
    {
        scanf("%d",V1+i);
    }
    scanf("%d",&M);
    for(int i=1;i<=M;++i)
    {
        scanf("%d",V2+i);
    }
    Precompute();
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        scanf("%d",&X);
        if(Query(X))
        {
            printf("DA\n");
        }
        else
        {
            printf("NU\n");
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4301)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4301/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4301/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)