3540 - Ambuscada

Cerința

N soldați, numerotați de la 1 la N, sunt prinși într-o ambuscadă. Asupra lor se execută M atacuri de tun. Atacurile afectează nu doar un soldat, ci un interval de soldați, provocând fiecăruia dintre aceștia o anumită pierdere (damage). De exemplu, atacul (3,7,5) afectează soldații 3,4,5,6,7 cu 5 damage. La început, toți soldații au V vieți. Câți soldați rămân în viață după cele M atacuri?

Date de intrare

Fișierul de intrare ambuscada.in conține pe prima linie numerele naturale N, M și V separate prin spații. Pe următoarele M linii se află câte 3 numere naturale i j k separate cu un spațiu, cu semnificația de mai sus.

Date de ieșire

Fișierul de ieșire ambuscada.out va conține un singur număr natural reprezentând numărul de soldați rămași în viață.

Restricții și precizări

2 ≤ N ≤ 1.000.000.000, 1 ≤ M ≤ 100.000, 1 ≤ V ≤ 1.000.000.000
In toate testele, 1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ V
Pentru teste în valoare de 30 de puncte, N<=100.000 și M<=50

Exemplul 1

ambuscada.in: 6 4 10; 2 5 2; 1 3 7; 2 6 3; 3 5 6

ambuscada.out: 2

Explicație

Inițial toți soldații aveau 10 vieți. După prima tragere: 10 8 8 8 8 10 După a doua tragere: 3 1 1 8 8 10 După a treia tragere: 3 0 0 5 5 7 După a patra tragere: 3 0 0 0 0 7 In final, 2 soldați au rămas în viață: primul și ultimul.

Exemplul 2

ambuscada.in: 5 2; 2 7 8; 1

ambuscada.out: Date invalide: Linia 1 nu contine suficiente valori

Rezolvare

3540 Ambuscada

def verificare_date_intrare(N, M, V, atacuri):

 # Verificăm dacă N, M și V sunt în intervalul specificat
 if not (2 <= N <= 1000000000 and 1 <= M <= 100000 and 1 <= V <= 1000000000):
   return False
 
 # Verificăm fiecare atac
 for atac in atacuri:
   i, j, k = atac
   # Verificăm dacă i, j și k sunt în intervalul specificat
   if not (1 <= i <= j <= N and 1 <= k <= V):
     return False
 
 return True

def soldati_ramasii(N, M, V, atacuri):

 # Inițializăm un vector cu viețile soldaților
 soldati = [V] * N
 
 # Parcurgem fiecare atac și actualizăm starea soldaților afectați
 for atac in atacuri:
   i, j, k = atac
   for index in range(i-1, j):
     soldati[index] -= k
 
 # Numărăm câți soldați au vieți pozitive și returnăm rezultatul
 soldati_ramas = sum(1 for viata in soldati if viata > 0)
 return soldati_ramas

def main():

 # Citim datele de intrare din fișier
 with open('ambuscada.in', 'r') as f:
   linii = f.readlines()
 
 # Verificăm dacă există suficiente linii în fișierul de intrare
 if len(linii) < 2:
   # Scriem mesaj de date invalide în fișierul de ieșire
   with open('ambuscada.out', 'w') as f:
     f.write("Date invalide: Nu sunt suficiente date in fisierul de intrare")
   return
 
 # Extragem N, M și V din prima linie
 try:
   N, M, V = map(int, linii[0].split())
 except ValueError:
   # Scriem mesaj de date invalide în fișierul de ieșire
   with open('ambuscada.out', 'w') as f:
     f.write("Date invalide: Linia 1 nu contine suficiente valori")
   return
 
 # Verificăm dacă există suficiente atacuri în fișierul de intrare
 if len(linii) - 1 < M:
   # Scriem mesaj de date invalide în fișierul de ieșire
   with open('ambuscada.out', 'w') as f:
     f.write("Date invalide: Nu sunt suficiente atacuri in fisierul de intrare")
   return
 
 # Citim atacurile
 atacuri = [tuple(map(int, line.split())) for line in linii[1:M+1]]
 
 # Verificăm datele de intrare
 if not verificare_date_intrare(N, M, V, atacuri):
   # Scriem mesaj de date invalide în fișierul de ieșire
   with open('ambuscada.out', 'w') as f:
     f.write("Datele de intrare sunt invalide")
   return
 
 # Calculăm numărul de soldați rămași în viață
 soldati_ramas = soldati_ramasii(N, M, V, atacuri)
 
 # Scriem rezultatul în fișierul de ieșire
 with open('ambuscada.out', 'w') as f:
   f.write(str(soldati_ramas))

if __name__ == "__main__":

 main()

</syntaxhighlight>