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()