4301 - Gustare

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 gustarein.txt 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 gustareout.txt 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

Exemplul 1

gustarein.txt

4
2 2 3 5
3
2 4 6
5
6 20 10 11 7

gustareout.txt

Datele de intrare corespund restrictiilor impuse
DA
NU
NU
DA 
DA

Exemplul 2

gustarein.txt

jgjikfikm

gustareout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
def validare(n_validare, m_validare, t_validare, coceni_validare, mere_validare, intrebari_validare):
    if n_validare < 1 or n_validare > 500000:
        raise ValueError
    if m_validare < 1 or m_validare > 500000:
        raise ValueError
    if t_validare < 1 or t_validare > 100:
        raise ValueError
    for valoare in coceni_validare + mere_validare:
        if valoare < 0 or valoare > 1000000000:
            raise ValueError
    for x in intrebari_validare:
        if x < 0 or x > 2000000000:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse.\n")


# Funcția exista_masa verifică dacă există o masă cu valoare nutritivă X
def exista_masa(coceni, mere, intrebari):
    raspunsuri_creare = []
    for x in intrebari:
        exista = 'NU'
        for cocean in coceni:
            if x - cocean in mere:
                exista = 'DA'
                break
        raspunsuri_creare.append(exista)
    return raspunsuri_creare


if __name__ == '__main__':
    file_in = open("gustarein.txt", "r")
    file_out = open("gustareout.txt", "w")

    try:
        # Citim numărul de coceni, numărul de mere și numărul de întrebări
        n_main = int(file_in.readline())
        coceni_main = list(map(int, file_in.readline().split()))
        m_main = int(file_in.readline())
        mere_main = list(map(int, file_in.readline().split()))
        t_main = int(file_in.readline())
        intrebari_main = list(map(int, file_in.readline().split()))
        # Validăm datele de intrare
        validare(n_main, m_main, t_main, coceni_main, mere_main, intrebari_main)
        # Verificăm dacă există o masă cu valoare nutritivă X pentru fiecare întrebare
        raspunsuri = exista_masa(coceni_main, mere_main, intrebari_main)
        # Scriem răspunsurile în fișierul de ieșire
        for raspuns in raspunsuri:
            file_out.write(raspuns + '\n')

    # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")