Fişierul intrare/ieşire:intfm.in, intfm.outSursăAlgoritmiada 2012, Runda 1
AutorCosmin GheorgheAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Intfm

Noaptea alba a pieselor de teatru de apropie, iar prietenul nostru Nocam vrea sa se culturalizeze. Evenimentul prezinta N spectacole. Citind programul complet, Nocam a observat ca fiecare piesa este alcatuita din 4 acte de durata egala. Intre actele 2 si 3 exista o pauza care dureaza la fel de mult ca si un act, adica o cincime din durata totala a piesei.

Dandu-se numarul N si cele N intervale de timp corespunzatoare perioadelor in care ruleaza fiecare piesa (exprimate in secunde), sa se determine numarul maxim de spectacole la care Nocam poate asista complet (prezenta este obligatorie la toate cele 4 acte).

Date de intrare

Fişierul de intrare intfm.in va contine pe prima linie numarul N, iar pe urmatoarele N linii cate 2 numere naturale, starti si finishi reprezentand momentul de inceput si momentul de final pentru piesa i.

Date de ieşire

În fişierul de ieşire intfm.out se va afisa o singura valoare, numarul maxim de piese de teatru la care poate sa mearga Nocam.

Restricţii si precizari

  • 1 ≤ N ≤ 2000
  • 0 ≤ starti ≤ finishi ≤ 109
  • Durata oricarui spectacol este divizibila cu 5
  • In pauza unei piese de teatru Nocam poate merge si la alte piese, cu conditia de a se intoarce la timp pentru actul 3 al piesei initiale
  • Deplasarea intre spectacole se face instantaneu (daca o piesa are loc in intervalul (a, b) si alta piesa are loc in intervalul (b, c), Nocam va putea merge la ambele).
  • Toate spectacolele vor avea durata pozitiva (mai mare ca 0)

Exemplu

intfm.inintfm.out
5
0 625
625 700
343 668
301 326
311 316
4

Explicaţie

Se iau intervalele (0, 625), (625, 700), (301, 326), (311, 316).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content