Fişierul intrare/ieşire:cursuri.in, cursuri.outSursăOJI 2017, clasa a 7-a
AutorDana LicaAdăugată detgm000Tudor Mocioi tgm000
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Cursuri(clasa a 7-a)

Notă: problema este punctată uşor diferit faţă de original din cauza restricţiilor impuse de evaluatorul infoarena.

Î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.incursuri.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici