Code Submission Evaluation System Login

Datatähti 2018 loppu

Start:2018-01-18 12:15:00
End:2018-01-18 17:15:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2018 loppu - MetsämetroCSES - Metsämetro

Metsämetro

Time limit:1.00 s
Memory limit:512 MB

Metsälän ja Syrjälän välinen uusi metroyhteys on viimein avattu. Linjalla on $n$ asemaa, joista ensimmäinen on Metsälä ja viimeinen on Syrjälä.

Metro ajoi ensimmäisen vuoron Metsälästä Syrjälään. Tiedät jokaisesta asemasta, montako matkustajaa yhteensä nousi junaan tai poistui junasta. Mikä on näiden tietojen perusteella pienin ja suurin mahdollinen määrä, montako matkustajaa oli enimmillään junassa jonkin kahden aseman välillä?

Juna oli tyhjä matkan alussa ja lopussa sekä kukaan matkustaja ei poistunut junasta heti nousemisen jälkeen samalla asemalla.

Syöte

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

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: mittaustulos kullakin asemalla.

Tuloste

Tulosta kaksi kokonaislukua: ala- ja yläraja junan suurimmalle matkustajamäärälle.

Voit olettaa, että on ainakin yksi tapa, miten matkustajat ovat voineet liikkua.

Esimerkki

Syöte:
4
5 3 4 6


Tuloste:
6 8

Selitys: Alarajassa junassa on asemien välillä 5, 2 ja 6 matkustajaa. Ylärajassa junassa on asemien välillä 5, 8 ja 6 matkustajaa.

Osatehtävä 1 (14 pistettä)
Osatehtävä 2 (28 pistettä)
Osatehtävä 3 (58 pistettä)