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

<syntaxhighlight lang="python" line>

1. 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")

1. 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")

</syntaxhighlight>