Hide

Problem L
Einvígi

Languages en is
/problems/einvigi/file/statement/is/img-0001.jpg
Einvígi milli tveggja hermanna

Tómas er mikill aðdáandi stríðsleikja. Uppáhaldsleikurinn hans núna er Einvígi margra. Í leiknum eru tveir spilarar að spila orrustu. Hver orrusta samanstendur af mörgum einvígum.

Tómas hefur n hermenn, hver táknaður með styrkleika ai. Andstæðingur Tómasar hefur einnig n hermenn, hver táknaður með styrkleika bi.

Einvígin fara þannig fram að i-ti hermaðurinn hjá Tómasi berst við i-ta hermanninn hjá andstæðingi sínum. Tómas vinnur einvígið ef ai>bi, það er jafntefli ef ai=bi og andstæðingurinn vinnur ef ai<bi. Einvígin fara fram í hækkandi röð; fyrst berjast a1 og b1, svo a2 og b2, og svo framvegis þar til an og bn eru búnir að berjast.

Tómas vinnur orrustuna ef hann vinnur fleiri einvígi heldur en óvinur sinn.

Tómas er nýbúinn að kaupa viðbótarpakka fyrir leikinn og í því var eitt Ofurseyði. Ofurseyðið virkar þannig að ef Tómas notar það þá mun styrkleikur hermanna hans verða sterkari um k í næstu m einvígum.

Tómas er ekki alveg viss um hvenær hann á að nota Ofurseyðið. Ef hann myndi velja besta tímann til að nota það, myndi Tómas geta unnið orrustuna?

Inntak

Fyrsta lína inniheldur þrjár heiltölur n,m,k, þar sem 1mn105, 1k107. Önnur lína inniheldur n heiltölur a1,a2,,an, þar sem 1ai107. Þriðja lína inniheldur n heiltölur b1,b2,,bn, þar sem 1bi107.

Úttak

Ef Tómas getur unnið orrustuna skrifið þá út fyrsta tíman sem hann gæti notað Ofurseyðið og unnið orrustuna. Ef Tómas getur ekki unnið orrustuna skrifið þá út Neibb.

Stigagjöf

Hópur

Stig

Takmarkanir

1

50

1mn1000, 1k,ai100

2

50

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
3 2 1
3 2 1
2 2 1
0
Sample Input 2 Sample Output 2
5 2 100
1 1 1 1 1
101 101 101 1 1
Neibb
Hide

Please log in to submit a solution to this problem

Log in