Fişierul intrare/ieşire:dunarea.in, dunarea.outSursăONI 2009, clasa a 8-a
AutorVictor ManzAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dunarea

Programul de reabilitare turistica a Dunării şi atragere a turiştilor a determinat autorităţile să decidă vânzarea de abonamente pe fiecare linie de croazieră existentă între porturile dunărene, la acelaşi preţ. Vasele unei linii de croazieră navighează între două porturi Xi, Yi (1≤ iN ) şi opresc în toate porturile dintre acestea, Xi+1, Xi+2,..., Yi-1, Yi. Un pescar gălăţean se deplasează zilnic din portul A în portul B folosind liniile de croazieră şi ar vrea să reducă cheltuielile cât mai mult. El a ajuns la concluzia că un număr de abonamente pe câte o linie de croazieră, alese eficient, este mai avantajos decât cumpărarea câte unui bilet pentru fiecare călătorie. Din păcate există mai multe combinaţii de linii de croazieră care parcurg traseul de la A la B. Pescar fiind, matematica nu este punctul său forte, deci vă cere ajutorul pentru a stabili care este numărul minim de abonamente necesare pentru a ajunge din portul A la B

Cerinţă

Scrieţi un program care, pe baza traseelor liniilor de croazieră, să calculeze şi să afişeze numărul minim de abonamente necesare pentru a ajunge de la A la B.

Date de intrare

Fişierul de intrare dunarea.in conţine pe prima linie trei numere naturale nenule A, B şi N separate prin câte un spaţiu. A şi B reprezintă porturile între care se deplasează zilnic pescarul. N este numărul de linii de croazieră.
Pe următoarele N linii se află câte 2 numere naturale nenule Xi, Yi (1 ≤ i ≤ N)separate prin câte un spaţiu, reprezentând porturile între care navighează linia de croazieră i.

Date de ieşire

Fişierul de ieşire dunarea.out va conţine un singur număr natural nenul, reprezentând numărul minim de abonamente necesare.

Restricţii

  • 1 ≤ A < B ≤ 5.000
  • 1 ≤ N ≤ 5.000
  • 1 ≤ Xi ≤ Yi ≤ 5.000
  • Se garantează pentru fiecare set de date de intrare existenţa a cel puţin unei linii de croazieră care acoperă întreg traseul de la A la B.
  • Pot să existe două sau mai multe linii de croazieră între aceleaşi porturi (cum se întâmplă în exemplul de mai jos cu liniile 1 şi 7).

Exemplu

dunarea.indunarea.out
1 10 8
5 8
1 2
5 10
3 7
3 6
3 4
5 8
2 4
4

Explicaţie

Sunt suficiente 4 abonamente pentru liniile: 2, 8, 4 şi 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content