Fişierul intrare/ieşire:zmeu2.in, zmeu2.outSursăOJI 2003, clasele 11-12
AutorDana LicaAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test0.2 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zmeu2

Un zmeu cu N capete călătoreşte din poveste în poveste, iar în poveştile tradiţionale întâlneşte câte un Făt Frumos care-l mai scurtează de câteva capete, în timp ce în poveştile moderne salvează omenirea mâncând în timp record, cu toate capetele lui, insecte ucigaşe apărute prin mutaţii genetice. Într-o seară, el îşi planifică o succesiune de poveşti cărora să le dea viaţă. El ştie P poveşti numerotate de la 1 la P, durata fiecăreia şi numărul de capete pe care le pierde în fiecare poveste. Mai ştie o mulţime de K perechi de poveşti care nu pot fi spuse una după alta.

Cerinţă

Ştiind că trebuie să înceapă cu povestea 1 şi să încheie succesiunea cu povestea P, ajutaţi bietul zmeu să aleagă una sau mai multe poveşti intermediare astfel încât durata totală să fie minimă şi să rămână cu cel puţin un cap la sfârşitul tuturor poveştilor.

Date de intrare

Fişierul de intrare zmeu2.in conţine pe prima linie numerele N, P şi K despărţite prin câte un spaţiu. Pe următoarele P linii se află câte o pereche de numere di şi ci (separate prin câte un spaţiu) ce reprezintă durata şi capetele tăiate pentru fiecare poveste. Iar pe ultimele K linii se află câte o pereche de numere pi şi pj (separate prin câte un spaţiu) ce semnifică faptul că povestea pj nu poate fi spusă după povestea pi.

Date de ieşire

În fişierul de ieşire zmeu2.out veţi afişa un singur număr natural reprezentând durata (minimă) a succesiunii de poveşti, sau valoarea -1 dacă nu există o astfel de succesiune.

Restricţii

  • 2 ≤ N ≤ 500
  • 1 ≤ P ≤ 200
  • 0 ≤ K ≤ 30.000
  • Valorile reprezentând duratele şi numărul de capete sunt numere naturale (duratele fiind strict pozitive), nedepăşind valoarea 10.

Exemplu

zmeu2.inzmeu2.out
10 4 2
2 6
4 0
1 3
3 3
3 2
4 3
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content