Fișierul intrare/ieșire munte.in, munte.out Sursă OJI 2014 clasa a 6-a
Autor Roxana Tîmplaru Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii