3239 - chain
Enunt
Se dă o secvență de N
numere întregi a1
, a2
, …, aN
. Pentru fiecare element ak
(k = 1, 2, ...,n
) vom determina primul element mai mare decât ak
, dacă există. Îl notăm cu ak1
. Apoi, pentru ak1
facem același lucru și elementul găsit îl notăm cu ak2
, și așa mai departe până ieșim în afara șirului. Se formează secvența ak1
, ak2
, …, pe care o numim chain începând cu poziția k
.
Cerința
Scrieți un program care, pentru orice poziție k
afișează lungimea secvenței chain corespunzătoare.
Date de intrare
Pe prima linie a intrării standard se dă valoarea N
. Pe a doua linie se dau elementele șirului, separate prin spații.
Date de ieșire
Pe o linie a ieșirii standard, programul va scrie șirul valorilor ce reprezintă lungimile secvențelor chain corespunzătoare elementelor șirului de intrare. Fiecare două numere consecutive trebuie separate printr-un singur spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări
0 < N < 500.000
0 < ai
< 1.000.000
, pentru fiecarei = 1..N
.
Exemplul 1:
Intrare
11 3 2 4 2 11 2 7 5 8 10 6
Ieșire
2 2 1 1 0 3 2 2 1 0 0
Exemplul 2:
Intrare
0 123
Ieșire
Datele nu corespund restrictiilor impuse
Rezolvare
def verifica_restrictii(n, a):
if not (0 < n < 500000):
return "Datele nu corespund restrictiilor impuse"
for i in range(n):
if not (0 < a[i] < 1000000):
return "Datele nu corespund restrictiilor impuse"
return "Datele corespund restrictiilor impuse"
def main():
n = int(input())
a = list(map(int, input().split()))
mesaj = verifica_restrictii(n, a)
if mesaj != "Datele corespund restrictiilor impuse":
print(mesaj)
return
p = [0]*n
d = [0]*n
# O(n)
s = []
for i in range(1, n):
s.append(i-1)
while s:
j = s[-1]
if a[j] >= a[i]:
break
if a[j] < a[i]:
p[j] = i
s.pop()
# chains
d[n-1] = 0
for i in range(n-2, -1, -1):
if p[i] == 0:
d[i] = 0
else:
d[i] = 1 + d[p[i]]
print(' '.join(map(str, d)))
if __name__ == "__main__":
main()