Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Ritarit


Task | Statistics


CSES - RitaritCSES - Ritarit

Time limit:1.00 s Memory limit:512 MB

Pyöreän pöydän ritarit ovat asettuneet syömään, mutta jokin on pahasti pielessä!

Jokainen ritari on toimittanut etukäteen tiedon, montako kiloa ruokaa tarvitsee. Mutta tarjoilijat ovat olleet huolimattomia eivätkä ruokamäärät täsmää. Vain ruoan kokonaismäärä on oikea.

Joka vuorolla yksi ritari voi siirtää kilon ruokaa hänen vieressään istuvalle ritarille. Mikä on pienin määrä vuoroja, joiden jälkeen jokaisella ritarilla on oikea määrä ruokaa?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: ritarien määrä.

Sitten syötteessä on $n$ kokonaislukua $a_1,a_2,\ldots,a_n$: montako kiloa ruokaa kukin ritari tarvitsee.

Lopuksi syötteessä on $n$ kokonaislukua $b_1,b_2,\ldots,b_n$: montako kiloa ruokaa kukin ritari on saanut eteensä.

Tuloste

Tulosta yksi kokonaisluku: pienin vuorojen määrä.

Rajat
Esimerkki

Syöte:
5
1 1 1 1 1
2 3 0 0 0


Tuloste:
4

Selitys: Jokainen ritari tarvitsee kilon ruokaa. Aluksi ritari 1:n edessä on kaksi kiloa ruokaa ja ritari 2:n edessä on kolme kiloa ruokaa. Ratkaisu: Ritari 1 siirtää ensin kilon ruokaa ritari 5:lle. Sitten ritari 2 siirtää kahdesti kilon ruokaa ritari 3:lle. Lopuksi ritari 3 siirtää kilon ruokaa ritari 4:lle.