| Fişierul intrare/ieşire: | munte7.in, munte7.out | Sursă | InfoOltenia 2018 - Clasa a 9-a |
| Autor | Ionut Gingu | Adăugată de |  Info-Oltenia 2018 •infooltenia |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Munte7
Se dă un şir de N numere naturale care trebuie adus la forma de “munte”. Un şir are formă de munte dacă există 1 <= i <= n astfel încât:
- oricare ar fi j, 1 <= j < i, v[j] <= v[j + 1]
- oricare ar fi k, i <= k < n, v[k] >= v[k + 1]
Cu alte cuvinte, un şir are formă de munte dacă este crescător până la o pozitie i şi apoi descrescător până la sfârşit.
Cerinţă
Să se calculeze numărul minim de numere care trebuiesc modificate pentru ca şirul rezultat să aibă formă de munte.
Date de intrare
Fişierul de intrare munte7.in contine pe prima linie numărul N = numărul de numere din şir. Pe a doua linie se for găsi cele N numere ale şirului.
Date de ieşire
Fişierul de ieşire munte7.out va contine pe prima linie numărul de modificări necesare pentru a-i da şirului forma de “munte”.
Restricţii
- 2 <= N <= 200000
- Elementele şirului sunt numere intregi care au valoarea absolută <= 109
- Pentru 40% din teste N <= 2000
- Pentru restul de 60%, N <= 200000
Exemplu
| munte7.in | munte7.out | Explicatii |
|---|---|---|
| 7 -1 2 3 -1 3 2 1 | 1 | Dacă îi dăm elementului de pe poziţia 4 valoarea 3, atunci şirul devine -1 2 3 3 3 2 1 şi are o formă de munte. |
| 9 1 5 4 7 6 8 3 5 2 | 3 | Schimbăm elementul de pe poziţia 3 în 6, elementul de pe poziţia 5 în 7 şi elementul de pe poziţia 7 în 6. şirul devine 1 5 6 7 7 8 6 5 2, deci este un „munte” cu vârf în poziţia 6. |
