Diferențe pentru problema/ecluze între reviziile #3 si #10

ecluze

Ecluze (Lot Juniori)

De exemplu, dacă pentru un sector navigabil există $9$ ecluze pentru care nivelul apei este următorul:
table(demo).

|=. 1 |=. 2 |=. 3 |=. 4 |=. 5 |=. 6 |=. 7 |=. 8 |=. 9 |
|=. 2 |=. 2 |=. 4 |=. 1 |=. 2 |=. 2 |=. 1 |=. 2 |=. 2 |

|_. ecluză  |=. 1 |=. 2 |=. 3 |=. 4 |=. 5 |=. 6 |=. 7 |=. 8 |=. 9 |
|_. nivel apă |=. 2 |=. 2 |=. 4 |=. 1 |=. 2 |=. 2 |=. 1 |=. 2 |=. 2 |
 
h2. 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.

h2. Date de intrare

Fișierul de intrare $ecluze.in$ ...

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ă $h[~1~], h[~2~],…, h[~N~]$ valori naturale separate prin câte un spațiu ce reprezintă nivelul apei corespunzător fiecărei ecluze.

h2. Date de ieșire

În fișierul de ieșire $ecluze.out$ ...

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.

h2. Restricții

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100 000$
* $1 ≤ h[~i~] ≤ 1 000 (h[~i~] – nivelul apei ecluzei i)$
* $pentru 20% din teste N ≤ 30$

h2. Exemplu
table(example).

|_. ecluze.in |_. ecluze.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

|_. ecluze.in |_. ecluze.out |_. Explicaț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
|

== include(page="template/taskfooter" task_id="ecluze") ==