Diferente pentru problema/spectacole intre reviziile #5 si #26

Nu exista diferente intre titluri.

Diferente intre continut:

_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 perioada de timp despre care vorbim în această problemă, $K[i]$, şi $K[i]$ perechi de câte două numere întregi $(a, b)$, reprezentând timpul de început al spectacolului, respectiv timpul de sfârşit.
Se dau $N$ săli de spectacole si $M$ spectacole. Pentru fiecare din cele $M$ spectacole se dau $3$ numere $s{~i~}$, $x{~i~}$ si $y{~i~}$ reprezentând sala unde se ţine spectacolul, timpul de început, respectiv timpul de sfârşit. Se ştie că pentru a se deplasa intre sali Antonio trebuie sa se deplaseze printr-o sală centrală, iar drumurile din această sală centrală spre o sală de spectacol şi drumurile inverse nu sunt identice. Mai exact durata de deplasare dinspre sala cu numarul $i$ si sala centrală este $A{~i~}$, iar dinspre sala centrală spre sala i este $B{~i~}$. Nu exista altă metoda pentru Antonio să se deplaseze între 2 sali $i$ şi $j$, astfel, pentru a se deplasa de la sala $i$ la sala $j$ Antonio are nevoie de $A{~i~} + B{~j~}$ momente de timp. 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 $T$, 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 $T$.
** Poate pleca la momentul $T$ către oricare sală $j (i diferit de j)$, ajungând în sala $j$ la momentul de timp $T + A{~i~} + B{~j~}$. Astfel, acesta poate viziona orice spectacol care rulează în sala $j$ şi are timpul de început mai mare sau egal cu $T + A{~i~} + B{~j~}$.
h2. Date de intrare
Fişierul de intrare $spectacole.in$ ...
Fişierul de intrare $spectacole.in$ conţine două numere naturale $N$ şi $M$, reprezentând numărul sălilor de spectacol, respectiv numarul de spectacole. Urmatorul rand va contine $N$ numere reprezentand valorile $A{~1~}$, $A{~2~}$, ..., respectiv $A{~N~}$. Al treilea rand va contine inca $N$ numere reprezentand valorile $B{~1~}$, $B{~2~}$, ..., respectiv $B{~N~}$.
Urmatoarele $M$ linii vor contine cate $3$ valori intregi fiecare. A $i$-a dintre aceste linii va contine valorile $s{~i~}$, $x{~i~}$ si $y{~i~}$.
h2. Date de ieşire
În fişierul de ieşire $spectacole.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 2000$
* $1 ≤ M ≤ 20000$
* $1 ≤ s{~i~} ≤ N$
* $0 ≤ x{~i~} < y{~i~} ≤ 1.000.000.000$
* $0 ≤ A{~i~}, B{~i~} ≤ 1.000.000.000$
* $Se garantează că nu există două spectacole care să ruleze simultan în aceeaşi sală.$
* $Pentru teste in valoare de *30* de puncte *N ≤ 100* si y{~i~} ≤ 1.250$
* $Pentru teste in valoare de inca *20* de puncte *N ≤ 500* si y{~i~} ≤ 1.250$
* $Pentru teste in valoare de *20* de puncte (dar nu neaparat altele decat cele 30 + 20 de mai sus) A{~i~} = B{~i~} = 0$
h2. Exemplu
table(example). |_. spectacole.in |_. spectacole.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 2 4
2 2
3 3
1 0 5
1 5 13
2 10 15
2 15 20
| 3
|
h3. Explicaţie
...
Antonio va viziona primul spectacol care are loc in sala $1$. La momentul de timp $5$ va pleca către sala $2$, unde va viziona spectacolele $3$ si $4$.
== include(page="template/taskfooter" task_id="spectacole") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.