View source for 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 <code>2</code> linii, numerotate cu <code>1</code> şi <code>2</code>, pe care sosesc şi pleacă trenurile. În acea zi, în gară sosesc <code>T</code> trenuri. Pentru fiecare tren din cele <code>T</code>, Rareş cunoaşte linia <code>L</code> pe care va sosi, momentul sosirii, adică ora <code>H</code> şi minutul <code>M</code>, precum şi durata de timp <code>S</code> de staţionare (exprimată în minute). El a decis ca perioada de studiu a celor <code>T</code> trenuri să înceapă cu momentul sosirii primului tren în gară din cele <code>T</code> şi să se încheie odată cu momentul plecării ultimului tren din cele <code>T</code>.

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

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

* numărul maxim de trenuri <code>Z</code> care au staţionat pe aceeaşi linie;
* numărul <code>X</code> de trenuri pe care Rareş le vede;
* durata de timp maximă <code>Y</code> (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 <code>tren.in</code> conține pe prima linie numărul <code>T</code> de trenuri şi pe fiecare din următoarele <code>T</code> linii, în ordinea sosirii trenurilor în gară, câte patru numere naturale <code>L</code>, <code>H</code>, <code>M</code> şi <code>S</code>, separate prin câte un spaţiu, ce reprezintă linia <code>L</code> pe care soseşte trenul, momentul sosirii trenului (ora <code>H</code> şi minutul <code>M</code>) şi durata de timp <code>S</code> de staţionare.

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

= Restricții și precizări =

* <code>2 ≤ T ≤ 100</code>; <code>0 ≤ H ≤ 23</code>; <code>0 ≤ M ≤ 59</code>; <code>1 ≤ S ≤ 9</code>;  <code>T</code>, <code>H</code>, <code>M</code>, <code>S</code> 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 <code>Z</code> se acordă 20% din punctajul pe test; * pentru aflarea corectă a numărului <code>X</code> se acordă 40% din punctajul pe test; * pentru aflarea corectă a numărului <code>Y</code> se acordă 40% din punctajul pe test.

= Exemplu: =
<code>tren.in</code>
 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
<code>tren.out</code>
 5 5 11

= Explicație =
Pe linia <code>1</code> au staţionat  <code>3</code> trenuri, iar pe linia <code>2</code> au staţionat <code>5</code> trenuri,  astfel <code>Z=5.</code>

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

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

<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("trenin.txt", "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("trenout.txt", "w") as g:

   g.write(str(z) + str(x) + str(y)) 
</syntaxhighlight>