Fișierul intrare/ieșire | munte.in, munte.out | Sursă | OJI 2014 clasa a 6-a |
---|---|---|---|
Autor | Roxana Tîmplaru | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Munte (clasa a 6-a)
Se consideră un șir x1, x2, ..., xn format din n numere naturale distincte. O secvență de număr maxim de elemente vecine în șir, de forma xi, xi+1, ..., xk-1, xk, xk+1, ..., xj (1 ≤ i < k < j ≤ n) cu proprietatea că xi < xi+1 < ... < xk-1 < xk > xk+1 > ... > xj, se numește munte cu vârful xk. Două secvențe munte au maxim un element comun în șir. O secvență munte are cel puțin 3 elemente. Un exemplu de șir format cu valorile 3 4 6 8 nu conține nicio secvență munte, iar unul format cu valorile 3 4 8 1 2 5 0 conține 2 secvențe munte: 3 4 8 1 și 1 2 5 0.
După determinarea tuturor secvențelor munte și a vârfurilor acestora, se elimină din șir vârfurile secvențelor munte și procedura continuă repetat cu determinarea noilor secvențe munte și a vârfurilor lor din șirul nou obținut. Procedura se oprește în momentul în care în șir nu mai există nicio secvență munte.
Cerință
Scrieți un program care citește numerele n, x1, x2, ..., xn și apoi determină:
a) numărul de secvențe munte din șirul inițial;
b) numărul total de secvențe munte obținute pornind de la șirul inițial până la cel care nu mai conține nicio secvență munte;
c) numărul de elemente din șirul final care nu mai conține secvențe munte.
Date de intrare
Fișierul de intrare munte.in conține pe prima linie numărul n, iar pe următoarea linie numerele naturale x1, x2, ..., xn separate două câte două prin câte un spațiu.
Date de ieșire
Fișierul de ieșire munte.out va conține pe prima linie un număr natural conform cerinței a), pe a doua linie un număr natural conform cerinței b), pe a treia linie un număr natural conform cerinței c).
Restricții
- 3 ≤ n ≤ 100
- 0 ≤ xi ≤ 100000, 1 ≤ i ≤ n
- Pentru rezolvarea corectă a cerinței a) se obține 20% din punctaj.
- Pentru rezolvarea corectă a cerinței b) se obține 40% din punctaj.
- Pentru rezolvarea corectă a cerinței c) se obține 40% din punctaj.
- Pentru testele date se asigură că șirul de numere dat inițial conține cel puțin o secvență munte.
Exemplu
munte.in | munte.out | Explicație |
---|---|---|
8 1 2 5 0 6 9 3 4 |
2 4 4 |
a) Sunt două secvențe munte: 1 2 5 0 și 0 6 9 3 b) După eliminarea vârfurilor secvențelor munte, șirul nou este 1 2 0 6 3 4. Acest șir conține 2 secvențe munte: 1 2 0 și 0 6 3. După eliminarea vârfurilor secvențelor munte, șirul nou este 1 0 3 4. Noul șir nu mai conține nicio secvență munte. În total sunt deci 4 secvențe. c) Șirul final care nu mai conține secvențe munte 1 0 3 4 are 4 elemente |