Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | spectacole.in, spectacole.out | Sursă | Algoritmiada 2015 Runda 1 |
| Autor | Marius Dumitran, Teodor Plop | Adăugată de |  Teodor Plop •Teodor94 |
| Timp execuţie pe test | 0.325 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Spectacole
Până şi Antonio a auzit de problema spectacolelor. Fiind însă o problemă deja foarte bine cunoscută şi mult prea "clasică" pentru gusturile lui Antonio, acesta vă propune să rezolvaţi următoarea problema a spectacolelor. Succes!
Se dau N săli de spectacole. Pentru fiecare sală i din cele N săli, se cunoaşte numărul de spectacole care rulează în ziua de astăzi, K[i], şi K[i] perechi de câte două numere naturale (a, b), reprezentând timpul de început al spectacolului, respectiv timpul de sfârşit. Se ştie că distanţa de timp între oricare două săli i şi j din cele N, cu i diferit de j, este egală cu un număr natural T. Antonio vrea să vadă cât mai multe spectacole, respectând următoarele reguli:
- Antonio va vedea doar spectacole complete. Altfel spus, Antonio nu are voie să părăsească sala decât în momentul terminării spectacolului.
- Dacă Antonio se află în sala i vizionând un spectacol care se termină la momentul de timp B, acesta are în continuare două opţiuni:
- Poate rămâne în sala i, urmând să vizioneze după bunul său plac orice spectacol care începe la un moment de timp mai mare sau egal decât B.
- Poate pleca la momentul B către oricare sală j (i diferit de j), ajungând în sala j la momentul de timp B + T. Astfel, acesta poate viziona orice spectacol care rulează în sala j şi are timpul de început mai mare sau egal cu B + T.
Date de intrare
Fişierul de intrare spectacole.in conţine două numere naturale N şi T, reprezentând numărul sălilor de spectacol, respectiv distanţa de timp între oricare două săli distincte. Pentru fiecare sală i din cele N, pe prima linie se va găsi un număr natural K[i], reprezentând numărul de spectacole ce rulează în sala i, urmat de K[i] linii. Pe fiecare linie j din aceste K[i] linii se va găsi o pereche (a, b), reprezentând timpul de start şi timpul de final al spectacolului j din sala i.
Date de ieşire
În fişierul de ieşire spectacole.out se va găsi un singur număr natural, reprezentând numărul maxim de spectacole pe care le poate vedea Antonio, respectând regulile de mai sus.
Restricţii
- 1 ≤ N ≤ 100
- 1 ≤ K[i] ≤ 100
- 0 ≤ a < b ≤ 24 * 60 = 1.440
- 0 ≤ T ≤ 1.440
- Se garantează că nu există două spectacole care să ruleze simultan în aceeaşi sală.
Exemplu
| spectacole.in | spectacole.out |
|---|---|
| 2 5 2 0 5 5 13 2 10 15 15 20 | 3 |
Explicaţie
Antonio va viziona primul spectacol din sala 1. La momentul de timp 5 va pleca către sala 2, unde va viziona primele două spectacole.
