Fişierul intrare/ieşire:ecluze.in, ecluze.outSursăLot III Juniori 2015
AutorEugen NodeaAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Ecluze (Lot Juniori)

Ecluza este o construcţie hidrotehnică amenajată pe traseul unei căi navigabile, care asigură trecerea navelor între două suprafeţe de apă cu niveluri diferite. O ecluză se compune dintr-un bazin numit „sas" sau „camera ecluzei", prevăzut la ambele capete cu porţi etanşe şi dintr-o instalaţie puternică de pompare pentru umplerea sau golirea sasului până la nivelul dorit.
Specialiştii români au construit pe cursul navigabil al Dunării o succesiune de N ecluze numerotate de la 1 la N, care asigură condiţii optime de navigare în sezoanele secetoase. Astfel, dacă o navă se află la un moment dat în ecluza i şi nivelul apei din ecluză diferă de nivelul apei din ecluza i+1, pentru a-şi continua navigarea în condiţii optime se face modificarea nivelului apei fie din ecluza i la nivelul ecluzei i+1, fie se face modificarea nivelului apei din ecluza i+1 la nivelul ecluzei i.
De exemplu, dacă pentru un sector navigabil există 9 ecluze pentru care nivelul apei este următorul:

ecluză123456789
nivel apă224122122

Cerinţă

Cunoscând nivelul apei din cele N ecluze, să se determine numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Date de intrare

Fişierul de intrare ecluze.in conţine pe prima linie numărul natural N ce reprezintă numărul de ecluze. Pe următoarea linie se află h1, h2,…, hN valori naturale separate prin câte un spaţiu ce reprezintă nivelul apei corespunzător fiecărei ecluze.

Date de ieşire

Fişierul de ieşire ecluze.out va conţine pe o singură linie un număr natural M ce reprezintă numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Restricţii

  • 2 ≤ N ≤ 100 000
  • 1 ≤ hi ≤ 1 000 (hi – nivelul apei ecluzei i)
  • pentru 20% din teste N ≤ 30

Exemplu

ecluze.inecluze.outExplicaţii
9
1 2 3 3 2 1 1 2 3
6
  • ecluza 1 este umplută până la nivelul 2
  • ecluza 2 este umplută până la nivelul 3
  • nivelul din ecluza 4 este coborât până la nivelul 2
  • nivelul din ecluza 5 este coborât până la nivelul 1
  • ecluza 7 este umplută până la nivelul 2
  • ecluza 8 este umplută până la nivelul 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici