Županijsko natjecanje 2013. / Osnovna škola (8. razred) - 3. zadatak

Nakon napornog tjedna na poslu, Krešo je odlučio uzeti odmor i posjetiti rodbinu.

Na putu do tamo, vozeći se autocestom, naišao je na kolonu kamiona.

Zaobići tu kolonu i ne bi bio toliki problem da nije radova na cesti koji otežavaju pretjecanje.

Kako je već rekao kada će stići, zanima ga koliko će mu vremena biti potrebno da zaobiñe kolonu kako bi mogao javiti koliko će kasniti.

Autocesta se sastoji od dvije trake, u jednoj od njih se voze kamioni, a druga služi za pretjecanje.

Svi kamioni kreću se jednakom brzinom od jednog kilometra po minuti, dok Krešin auto može postići i duplo veću brzinu što koristi kako bi ih pretekao.

Naravno, Kreši je cilj što prije zaobići kolonu, ali kada vozi neposredno iza kamiona mora prilagoditi brzinu brzini kamiona dok u suprotnom vozi maksimalnom brzinom.

Zbog radova na cesti traka za pretjecanje je na nekim mjestima prekinuta pa Krešo mora paziti kada pretječe.

Kreši je unaprijed poznato na kojim kilometrima autoceste se nalaze kamioni i na kojim je kilometrima traka za pretjecanje prekinuta.

Budući da je savjestan vozač nikada se neće prestrojiti u traku za pretjecanje dok u potpunosti nije prošao kilometar u kome se nalazi prekid trake za pretjecanje niti će se vratiti u traku s kamionima dok u potpunosti nije prošao kilometar u kome se nalaze kamioni.

Krešin auto na početku se nalazi na nultom kilometru autoceste, a možemo pretpostaviti da mu je za prestrojavanje, ubrzavanje i usporavanje potrebno zanemarivo malo vremena.

Vaš zadatak je odrediti koliko bi Kreši bilo potrebno vremena da zaobiđe kolonu kada ne bi bilo radova na cesti i koliko će mu vremena biti potrebno da zaobiđe kolonu kada su radovi prisutni tj. kada prekidi na traci za pretjecanje postoje.

Ilustracija prvog test primjera (gornji red slike predstavlja traku s kamionima, a donji traku za pretjecanje; legenda: 'o' – Krešin auto, 'X' – kilometar u kome se nalaze kamioni, '|' – kilometar u kojem se nalazi prekid u traci za pretjecanje, '-' – prazan kilometar ceste):

ULAZNI PODATCI

U prvom retku nalaze se dva prirodna broja N i M (1 ≤ N, M ≤ 100), redom broj kilometara u kojima se nalaze kamioni i broj kilometara na kojima je prekinuta traka za pretjecanje.

U drugom retku nalazi se N prirodnih brojeva Ki (1 ≤ Ki ≤ 109), kilometri na kojima se nalaze kamioni u nultoj minuti.

U trećem retku nalazi se M prirodnih brojeva Pi (1 ≤ Pi ≤ 109), kilometri na kojima je prekinuta traka za pretjecanje.

Možete pretpostaviti da su brojevi u drugom i trećem retku sortirani uzlazno.

IZLAZNI PODATCI

U prva i jedina dva retka potrebno je ispisati tražena vremena iz zadatka (izražena u minutama), u prvom retku kada zanemarimo prekide, a u drugom kada prekidi postoje.

PRIMJERI TEST PODATAKA

Ulaz

1 1
1
4

Izlaz

2
7

Ulaz

3 2
1 5 6
3 9

Izlaz

7
11

Ulaz

3 3
1 3 5
2 9 10

Izlaz

6
13

Objašnjenje

Pojašnjenje drugog test primjera:

Da nije bilo radova na cesti Krešo bi kolonu pretekao za 7 minuta.

Kada radovi postoje Krešo 4 minute čeka da proñe prekid trake za pretjecanje, a zatim za 2 minute pretekne prvi kilometar kamiona.

Do druga dva kilometra kamiona stigne za 2 minute i pretekne ih za 3 minute. To je ukupno 11 minuta.