Fişierul intrare/ieşire:ghizi.in, ghizi.outSursăONI 2003 - baraj
AutorMihai StroeAdăugată desilviugSilviu-Ionut Ganceanu silviug
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ghizi

Se caută ghizi pentru Olimpiada Naţională de Informatică. Deoarece la Olimpiadă participă K echipe, trebuie ca în fiecare moment de timp din intervalul [0, 100) să existe exact K ghizi. Pentru posturile de ghid s-au înscris N voluntari, care au fost numerotaţi distinct de la 1 la N. Fiecare dintre cei N voluntari a specificat un interval de timp în care poate asigura servicii de ghid. Voluntarul i poate fi ghid în intervalul [T1i, T2i) (intervalul este închis în T1i şi deschis în T2i).

Cerinţă

Dându-se intervalele de timp asociate celor N voluntari, determinaţi o variantă de angajare astfel încât în fiecare moment de timp să fie prezenţi exact K ghizi. Numărul total de voluntari angajaţi este irelevant.

Date de intrare

Prima linie a fişierului de intrare ghizi.in conţine două numere întregi N şi K, separate printr-un spaţiu, cu semnificaţiile de mai sus. Voluntarii sunt numerotaţi distinct, de la 1 la N. Fiecare dintre următoarele N linii conţine descrierea unui voluntar; mai exact linia i+1 conţine valorile întregi T1i şi T2i pentru voluntarul i.

Date de ieşire

În fişierul de ieşire ghizi.out veţi afişa pe prima linie numărul total de ghizi angajaţi - să-l notăm cu M. Pe a doua linie veţi scrie M numere distincte între 1 şi N, ordonate crescător, reprezentând numerele de ordine ale ghizilor angajati.

Restricţii

  • 1 ≤ N ≤ 5000
  • 0 ≤ T1 < T2 ≤ 100 pentru fiecare dintre cei N voluntari
  • 1 ≤ K ≤ N
  • Pot exista 2 voluntari cu acelaşi interval asociat.
  • Toate testele date vor avea soluţie.
  • Dacă există mai multe soluţii, afişaţi una oarecare.
  • La preselecţie participă numai fete.

Exemplu

ghizi.inghizi.out
6 2
0 100
0 15
15 99
0 10
10 20
20 100
4
1 4 5 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content