Fișierul intrare/ieșire cursuri.in, cursuri.out Sursă OJI 2017, clasa a 7-a
Autor Dana Lica Adăugată de avatar tgm000 Tudor Mocioi tgm000
Timp de execuție pe test 0.2 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Cursuri (clasa a 7-a)

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 [ai, bi] î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.

Cerințe

Cunoscându-se faptul că organizatorii doresc susținerea a cât mai multor cursuri, să se determine:
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.

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 ai bi, 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.

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.

Restricții

  • 1 ≤ N ≤ 1 000
  • 1 ≤ K ≤ 1 000
  • 1 ≤ ai < bi ≤ 100 000, unde 1 ≤ i ≤ 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 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.

Exemplu

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];

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii