Fişierul intrare/ieşire:paznici.in, paznici.outSursăOlimpiada pe scoala 2015
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.3 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Paznici (clasele 11-12)

Pentru a proteja cea mai bună şcoală din ţară de atacurile teroriste, guvernul a hotărât să încheie un contract cu o firmă de protecţie şi pază. Fiecare firmă are asociat un cod numeric şi poate asigura paza numai în anumite intervale de timp (fiecare dintre angajaţii săi poate lucra în anumite intervale de timp). Guvernul doreşte asigurarea pazei între momentele de timp A şi B. În acest scop va alege acea firmă pentru care perioada de timp din intervalul [A,B] neacoperită cu agenţi de pază este cea mai scurtă. Dacă vor exista mai multe firme aflate la egalitate conform acestui criteriu, atunci va fi aleasă cea având codul numeric mai mic.

Date de intrare

Fişierul de intrare paznici.in conţine pe prima linie numerele A şi B reprezentând perioada în care trebuie asigurată paza. Pe cea de-a doa linie se va afla numărul total de paznici, N. Pe următoarele N linii se vor afla câte trei numere X, Y şi C reprezentând intervalul de timp şi codul firmei la care este angajat fiecare paznic în parte.

Date de ieşire

În fişierul de ieşire paznici.out se va scrie un singur număr reprezentând codul firmei alese.

Restricţii

  • 0 ≤ A < B ≤ 1 000 000 000
  • 1 ≤ N ≤ 100 000
  • A ≤ X < Y ≤ B pentru fiecare paznic în parte
  • 1 ≤ C ≤ 1000 pentru fiecare paznic în parte

Exemplu

paznici.inpaznici.out
1 10
3
1 4 1
3 10 2
8 10 1
2

Explicaţie

Firma 2 va lăsa şcoala nepăzită între 1 şi 3 ( 2 unităţi de timp ) în timp ce firma 1 nu va păzi şcoala între 4 şi 8 ( 4 unităţi de timp)

Trebuie sa te autentifici pentru a trimite solutii. Click aici