1084 - Tren

Un elev în clasa a V-a, Rareş, s-a gândit să studieze mersul trenurilor ce trec prin gara din oraşul său, într-o zi. Gara are 2 linii, numerotate cu 1 şi 2, pe care sosesc şi pleacă trenurile. În acea zi, în gară sosesc T trenuri. Pentru fiecare tren din cele T, Rareş cunoaşte linia L pe care va sosi, momentul sosirii, adică ora H şi minutul M, precum şi durata de timp S de staţionare (exprimată în minute). El a decis ca perioada de studiu a celor T trenuri să înceapă cu momentul sosirii primului tren în gară din cele T şi să se încheie odată cu momentul plecării ultimului tren din cele T.

Din sala de aşteptare Rareş poate vedea cele 2 linii. Rareş are însă o problemă: atunci când un tren se află în gară pe linia 1, el nu poate vedea trenul staţionat în acelaşi timp pe linia 2. De exemplu, dacă un tren ajunge în gară pe linia 1 la ora 14:21 şi staţionează 5 minute atunci trenul va pleca din gară la ora 14:26. Astfel, în intervalul de timp [14:21-14:26], Rareş nu poate vedea ce se întâmplă pe linia 2. Trenul de pe linia 2 va putea fi vizibil începând cu minutul următor, adică de la 14:27.

Cerinţă

Scrieţi un program care să determine pentru un număr T de trenuri care trec prin gară în perioada de studiu din acea zi:

• numărul maxim de trenuri Z care au staţionat pe aceeaşi linie;
• numărul X de trenuri pe care Rareş le vede;
• durata de timp maximă Y (exprimată în număr de minute consecutive), din perioada de studiu, în care Rareş nu a văzut niciun tren.

Date de intrare

Fișierul de intrare tren.in conține pe prima linie numărul T de trenuri şi pe fiecare din următoarele T linii, în ordinea sosirii trenurilor în gară, câte patru numere naturale L, H, M şi S, separate prin câte un spaţiu, ce reprezintă linia L pe care soseşte trenul, momentul sosirii trenului (ora H şi minutul M) şi durata de timp S de staţionare.

Date de ieșire

Fișierul de ieșire tren.out va conține pe prima linie, separate prin câte un spaţiu, valorile cerute Z, X și Y (în această ordine).

Restricții și precizări

• 2 ≤ T ≤ 100; 0 ≤ H ≤ 23; 0 ≤ M ≤ 59; 1 ≤ S ≤ 9; T, H, M, S sunt numere naturale;
• în acelaşi moment de timp nu pot pleca/sosi mai multe trenuri; * în acelaşi moment de timp nu poate pleca un tren şi altul să sosească;
• pe aceeaşi linie nu pot staţiona mai multe trenuri în acelaşi moment de timp; * pentru aflarea corectă a numărului Z se acordă 20% din punctajul pe test; * pentru aflarea corectă a numărului X se acordă 40% din punctajul pe test; * pentru aflarea corectă a numărului Y se acordă 40% din punctajul pe test.

Exemplu:

tren.in

8
1 14 20 3
2 14 21 1
2 14 24 4
1 14 40 8
2 14 41 1
2 14 43 1
2 14 45 5
1 14 56 1

tren.out

5 5 11

Explicație

Pe linia 1 au staţionat 3 trenuri, iar pe linia 2 au staţionat 5 trenuri, astfel Z=5.

La ora 14:20 Rareş vede trenul care ajunge pe linia 1 şi va staţiona până la ora 14:23. El nu vede trenul care ajunge pe linia 2 la ora 14:21 şi pleacă la 14:22. El vede trenul care ajunge pe linia 2 la 14:24 pentru că în momentul sosirii nu se află tren pe linia 1. De asemenea, el vede trenul care ajunge la 14:40 pe linia 1, dar nu vede următoarele 2 trenuri care ajung pe linia 2 întrucât trenul de pe linia 1 pleacă la 14:48. Vede şi ultimul tren de pe linia 2 pentru că el soseşte înainte de plecarea trenului de pe linia 1 şi pleacă după acesta. În total a văzut 5 trenuri.

În intervalele de timp [14:29-14:39] şi [14:51-14:55], Rareş nu vede niciun tren, durata de timp maximă fiind de 11 minute (determinată de trenul care pleacă la 14:28 şi următorul tren care soseşte la 14:40).

<syntaxhighlight lang="python" line="1">

import sys

t1 = 0

x = 1

y = 0

z = 0

t = 0

l = 0

h = 0

m = 0

sta = 0

s = 0

p = 0

am2 = 0

p1 = 0

p2 = 0

u = 0

with open("tren.in", "r") as f:

  lines = f.readlines()

  t = int(lines[0])

  for i in range(1, t+1):

      l, h, m, sta = map(int, lines[i].split())

      s = h*60 + m

      p = s + sta

      if s - u > y:

          y = s - u

      if s > p1 + 1 and am2 == 1 and p2 > p1:

          x += 1

          am2 = 0

      if l == 1:

          x += 1

          t1 += 1

          p1 = p

      else:

          if s > p1:

              x += 1

              am2 = 0

              p2 = p

          elif p > p1:

              p2 = p

              am2 = 1

      u = max(p1, p2)

if am2:

  x += 1

z = max(t1, t - t1)

if y:

  y -= 1

with open("tren.out", "w") as g:

  g.write(str(z) + str(x) + str(y)) 

</syntaxhighlight>