Fișierul intrare/ieșire | cursuri.in, cursuri.out | Sursă | OJI 2017, clasa a 7-a |
---|---|---|---|
Autor | Dana Lica | Adăugată de | Tudor Mocioi • tgm000 |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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ă
4552 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă4548 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]; |