1906 - Memory 007

Cerinţa

Agentul 007 a uitat cifrul seifului în care păstra documentele, însă ştie cum poate fi aflat. Are nişte cartonaşe pe care sunt notate n numere naturale distincte din intervalul [ a,b ]. Mai are o listă cu m numere naturale distincte care reprezintă anumite poziţii din şirul ordonat crescător al numerelor de pe cartonaşe. Însumând numerele aflate pe poziţiile din listă se determină un număr natural care reprezintă cifrul seifului. Cum Agentul 007 nu a mai programat din liceu, vă roagă pe voi să găsiţi cifrul în schimbul a 100 de … puncte.

Date de intrare

Fișierul de intrare memory007in.txt conține pe prima linie numerele n,m,a,b, pe a doua linie n numere naturale distincte separate prin spații reprezentând numerele de pe cartonaşe, iar pe a treia linie m numere naturale distincte reprezentând poziţiile din listă.

Date de ieşire

Fișierul de ieșire memory007out.txt va conține pe prima linie cifrul seifului.

Restricții și precizări

• 1 ⩽ m ⩽ n ⩽ 500.000
• numerele de pe cartonaşe vor fi distincte şi mai mici decât 1.000.000.000
• numerele din listă vor fi naturale nenule, distincte şi mai mici sau egale cu n, ordonate crescător
• 1 ⩽ a ⩽ b ⩽ 1.000.000.000
• n ⩽ b - a ⩽ 700.000

Exemplul 1

memory007in.txt

5 3 30 80
78 56 34 45 61
1 2 5

memory007out.txt

Datele de intrare corespund restrictiilor impuse.
157

Explicație

Numerele de pe cartonaşe sunt 78,56,34,45,61 şi sunt din intervalul [ 30,80 ]. Ordonate crescător formează şirul 34,45,56,61,78. Numerele din listă, adică 1,2,5, ne spun că cifrul se obţine însumând numerele de pe poziţiile 1, 2 şi 5 din şirul ordonat crescător al numerelor de pe cartonaşe, adică cifrul este 34+45+78=157.

Exemplul 2

memory007in.txt

rhgurhkfgrjg

memory007out.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, a_validare, b_validare, cartonase_validare, pozitii_validare):

   # Verificăm dacă n este în intervalul 1-500000
   if n_validare < 1 or n_validare > 500000:
       raise ValueError
   # Verificăm dacă m este în intervalul 1-n
   if m_validare < 1 or m_validare > n_validare:
       raise ValueError
   # Verificăm dacă a este în intervalul 1-1000000000
   if a_validare < 1 or a_validare > 1000000000:
       raise ValueError
   # Verificăm dacă b este în intervalul a-1000000000
   if b_validare < a_validare or b_validare > 1000000000:
       raise ValueError
   if n_validare > b_validare - a_validare or b_validare - a_validare > 700000:
       raise ValueError  # Ridicăm o eroare dacă aceste condiții nu sunt îndeplinite
   # Parcurgem lista de valori de pe cartonașe
   for valoare in cartonase_validare:
       # Verificăm dacă valoarea este în intervalul a-b
       if valoare < a_validare or valoare > b_validare:
           raise ValueError
   for pozitie in pozitii_validare:    # Parcurgem lista de poziții
       # Verificăm dacă poziția este în intervalul 1-n
       if pozitie < 1 or pozitie > n_validare:
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

1. Funcția cifru_seif calculează cifrul seifului

def cifru_seif(cartonase, pozitii):

   cartonase.sort()
   cifru_calcul = sum(cartonase[pozitie - 1] for pozitie in pozitii)
   return cifru_calcul

if __name__ == '__main__':

   file_in = open("memory007in.txt", "r")
   file_out = open("memory007out.txt", "w")

   try:
       # Citim numărul de cartonașe, numărul de poziții, limita inferioară și limita superioară a intervalului
       n_main, m_main, a_main, b_main = map(int, file_in.readline().split())
       # Citim valorile de pe cartonașe
       cartonase_main = list(map(int, file_in.readline().split()))
       # Citim pozițiile
       pozitii_main = list(map(int, file_in.readline().split()))
       # Validăm datele de intrare
       validare(n_main, m_main, a_main, b_main, cartonase_main, pozitii_main)
       # Calculăm cifrul seifului
       cifru = cifru_seif(cartonase_main, pozitii_main)
       # Scriem cifrul în fișierul de ieșire
       file_out.write(str(cifru) + '\n')

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>