Лимит времени 3090/9045/8000/4000 мс. Лимит памяти 15720/79180/65000/65000 Кб. Question by Osman Ay, It has been first asked in IS 2012 March.
Te Parkojme Autobuse
Perktheu: Devid Duma
English
Qyteti i Tiranës ka N autobusë, të shënuar në mënyrë të
përshtatshme nga 1 tek N, për transportin publik. Autobusët
parkohen në një zonë parkimi në fund të çdo dite. Autobusët
parkohen krah për krah. Ata mund të renditen në çdo mënyrë, por
ka disa kufizime që duhet të merren parasysh. Kufizimet kanë të
bëjnë me prioritetin midis dy autobusëve të caktuar. Disa
autobusë duhen parkuar përpara disa autobusëve të tjerë për
shkak të orarit të ditës së ardhshme.
Kërkesë
Bëni një program që jep numrin e kufizimeve që nuk janë
plotësuar me radhitjen e dhënë të autobusëve.
Specifikimet e Input
Input ka disa rreshta. Rreshti i parë përmban dy numra të plotë:
N dhe M, ku N tregon numrin e autobusëve (1 < N ≤ 10000) dhe
M (0 ≤ M ≤ 501000) tregon numrin e kufizimeve. Secili prej M
rreshtave të mëposhtëm përfaqëson një kufizim me një cift
numrash të plotë X dhe Y (1 ≤ X, Y ≤ N). Një cift tregon se
autobusi X duhet të parkohet para autobusit Y.
Pjesa e fundit e input përmban N numra që tregojnë rradhitjen
e disponueshme të autobusëve. Autobusët janë të shënuar me numra
nga 1 deri te N dhe ka më së shumti 40 autobusë në një rresht,
që do të thotë se rreshtat përmbajnë më pak se 255 karaktere.
Specifikimet e Output
Nxirr vetëm një numër Res (ku 0 ≤ Res ≤ M). Kjo do të
thotë se ka Res kufizime të cilat nuk janë plotësuar me rradhitjen e
dhënë të autobusëve. Nëse të gjitha kufizimet janë plotësuar në
rradhitjen e autobusëve, nxirr 0 (zero).
Give just one integer Res (where 0 ≤ Res ≤ M). That means there are Res restrictions which are not satisfied with
the given bus order. If all the restrictions are satisfied with the current bus order, show 0 (zero).
Shembull Input
6 7
1 3
2 4
1 6
5 4
4 6
3 6
2 1
2 3 1 5 6 4
Shembull Output
2
Shpjegimi për shembullin output.
Janë dy kufizime(i pari(1 3) dhe i pesti(4 6) ) që nuk janë
plotësuar me kushtet e dhëna.
Для отправки решений необходимо выполнить вход.
|