1063 - Arme

Cerința

Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j. Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.

Date de intrare

Fișierul de intrare arme.in conține pe prima linie numerele naturale N M, reprezentând numărul de arme pe care le are la brâu, respectiv numărul de arme aflate în camera armelor. Pe a doua linie se află N numere naturale pb1 pb2 … pbN reprezentând în ordine puterile armelor pe care Vasile le are la brâu. Pe a treia linie se află M numere naturale pc1 pc2 … pcM reprezentând în ordine puterile armelor aflate în camera armelor. Numerele scrise pe aceeaşi linie sunt separate prin spaţiu.

Date de ieșire

Fișierul de ieșire arme.out va conține o singură linie pe care va fi scrisă suma maximă a puterilor armelor de la brâul lui Vasile, după efectuarea înlocuirilor.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Puterile armelor sunt numere naturale ≤ 10.000.
• Greutatea și valoarea fiecărei arme sunt numere întregi pozitive

Exemplu 1

Intrare

4
2 3
3 4
4 5
5 6
5

Iesire

7

Rezolvare

<syntaxhighlight lang="python" line> def main():

   with open("arme.in", "r") as f:
       # Citim dimensiunile N și M
       N, M = map(int, f.readline().strip().split())
       
       # Citim puterile armelor de la brâu
       puteri_brau = list(map(int, f.readline().strip().split()))
       
       # Citim puterile armelor din camera armelor
       puteri_camera = list(map(int, f.readline().strip().split()))

   # Restricții și precizări
   assert 1 <= N <= 1000, "N trebuie să fie între 1 și 1000"
   assert 1 <= M <= 1000, "M trebuie să fie între 1 și 1000"
   assert all(1 <= pb <= 10000 for pb in puteri_brau), "Puterea armelor de la brâu trebuie să fie între 1 și 10000"
   assert all(1 <= pc <= 10000 for pc in puteri_camera), "Puterea armelor din cameră trebuie să fie între 1 și 10000"

   # Sortăm puterile armelor de la brâu în ordine crescătoare
   puteri_brau.sort()

   # Sortăm puterile armelor din cameră în ordine descrescătoare
   puteri_camera.sort(reverse=True)

   # Înlocuim armele de la brâu cu cele din cameră
   for i in range(min(N, M)):
       if puteri_camera[i] > puteri_brau[i]:
           puteri_brau[i] = puteri_camera[i]
       else:
           break

   # Calculăm suma maximă a puterilor armelor de la brâu
   suma_maxima = sum(puteri_brau)

   with open("arme.out", "w") as f:
       f.write(f"{suma_maxima}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>