Diferențe pentru problema/cursuri între reviziile #2 si #9

== include(page="template/taskheader" task_id="cursuri") ==

_Notă: problema este punctată ușor diferit față de original din cauza restricțiilor impuse de evaluatorul NerdArena._
 

Într-o tabără de vară se programează susținerea unor cursuri în $K$ săli de clasă. Sunt $N$ profesori care și-au exprimat dorința de a participa, fiecare dintre ei specificând intervalul de timp $[a[~i~], b[~i~]]$ în care își poate susține cursul. Programarea pe săli a profesorilor trebuie să țină cont de faptul că într-o clasă, la un moment dat, nu poate preda decât un singur profesor.
h2. Cerințe

1) Numărul maxim de cursuri care pot fi programate în cele $K$ săli de clasă, ținând cont de restricția indicată.
2) În dorința de a programa toate cursurile, în cele $K$ săli, organizatorii decid să modifice durata cursurilor, păstrând însă neschimbată ora de început a lor. Astfel, ei hotărăsc ca toate cursurile să dureze un interval egal de timp, care însă nu va depăși durata celui mai lung curs propus inițial de unul dintre cei $N$ profesori. Determinați care poate fi durata maximă pe care o pot avea cursurile în aceste condiții.

h2. Date de intrare
În fișierul de intrare $cursuri.in$ se găsește pe prima linie un număr natural [$C$]. Pentru toate testele, $C$ poate lua numai valorile $1$ sau [$2$]. Pe linia a doua se găsește o pereche de numere naturale $N K$, separate printr-un spațiu, reprezentând numărul profesorilor și numărul de săli de clasă. Pe următoarele $N$ linii se găsesc perechi de numere naturale $a[~i~] b[~i~]$, care reprezintă intervalele de timp în care cei $N$ profesori își susțin cursurile. Numerele în cadrul unei linii sunt separate printr-un spațiu.
h2. Date de ieșire

Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire $cursuri.out$ va conține pe prima linie un număr natural reprezentând numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.
Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire $cursuri.out$ va conține pe prima linie un număr natural reprezentând durata maximă pe care o pot avea cele N cursuri, astfel încât toate să poată fi susținute în cele K săli disponibile.

Dacă valoarea lui $C$ este [$1$], se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire $cursuri.out$ va conține pe prima linie un număr natural reprezentând numărul maxim de cursuri care pot fi programate în cele $K$ săli de clasă, ținând cont de restricția indicată.
Dacă valoarea lui $C$ este [$2$], se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire $cursuri.out$ va conține pe prima linie un număr natural reprezentând durata maximă pe care o pot avea cele $N$ cursuri, astfel încât toate să poată fi susținute în cele $K$ săli disponibile.

h2. Restricții
* $1 ≤ N ≤ 1 000$
* $1 ≤ K ≤ 1 000$

* $1 ≤ ai ≤ bi ≤ 100 000, unde  1 ≤ i ≤ N$

* $1 &le; a[~i~] < b[~i~] &le; 100 000, unde  1 &le; i &le; N$

* În cazul cerinței 2) se garantează că pentru toate testele există soluție

* Pentru rezolvarea corectă a primei cerințe se acordă 45 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 de puncte. Se acordă 10 puncte din oficiu.

* Pentru rezolvarea corectă a primei cerințe se acordă -45- 52 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă -45- 48 de puncte. -Se acordă 10 puncte din oficiu.-

h2. Exemplu

table(example).
|_. cursuri.in |_. cursuri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

table(example).
|_. cursuri.in |_. cursuri.out |_. Explicație |
| 1
4 2
2 16
1 3
3 18
1 20
| 3
| O variantă de programare optimă este următoarea:
-	în prima sală se vor susține cursurile programate între [1,3] și [3,18]
-	în a doua clasă se susține cursul programat între [1,20] |
| 2
4 2
5 12
9 18
1 3
1 7
| 4
| Durata maximă pe care o pot avea toate cursurile este 4.
Cursul al treilea se va mări și se va desfășura între [1,5], celelalte se vor micșora.
Cursurile vor fi distribuite în cele două săli astfel:
 
Sala 1: al treilea și primul profesor programați între [1,5] respectiv [5,9];
Sala 2: al patrulea și al doilea profesor programați între [1,5] respectiv [9,13];

|

h3. Explicație
 
...
 

== include(page="template/taskfooter" task_id="cursuri") ==