1046 - Munte
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ța
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 și precizări
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
8 1 2 5 0 6 9 3 4
munte.out
2 4 4
Explicație
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
Încărcare soluție
Lipește codul aici
MAX = 1000000
fin = open("munte.in", "r")
fout = open("munte.out", "w")
n = 0
i = 0
j = 0
parcurgere = 0
munti = 0
cati = 0
x = [0] * 110
gasit_munte = False
n = int(fin.readline())
x = list(map(int, fin.readline().split()))
parcurgere = 1
gasit_munte = True
while gasit_munte:
gasit_munte = False
cati = 0
i = 0
while i < n and x[i] > x[i + 1]:
i += 1
while i <= n:
while i < n and x[i] < x[i + 1]:
i += 1
if i < n:
munti += 1
cati += 1
x[i] = MAX
gasit_munte = True
while i < n and x[i] > x[i + 1]:
i += 1
if i < n and x[i] > x[i - 1]:
i -= 1
else:
if i == n:
break
if parcurgere == 1:
fout.write(str(munti) + '\n')
parcurgere += 1
i = 0
while i < n:
while x[i] != MAX and i < n:
i += 1
for j in range(i, n):
x[j] = x[j + 1]
if gasit_munte:
n -= cati
fout.write(str(munti) + '\n')
fout.write(str(n) + '\n')
fin.close()
fout.close()