3239 - chain - Revision history

Aurelia Raluca at 09:35, 13 February 2024

2024-02-13T09:35:26Z

← Older revision		Revision as of 09:35, 13 February 2024
Line 1:		Line 1:
	== Enunt ==		== 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.		Se dă o secvență de <code>N</code> numere întregi <code>a1</code>, <code>a2</code>, …, <code>aN</code>. Pentru fiecare element <code>ak</code> (<code>k = 1, 2, ...,n</code>) vom determina primul element mai mare decât <code>ak</code>, dacă există. Îl notăm cu <code>ak1</code>. Apoi, pentru <code>ak1</code> facem același lucru și elementul găsit îl notăm cu <code>ak2</code>, și așa mai departe până ieșim în afara șirului. Se formează secvența <code>ak1</code>, <code>ak2</code>, …, pe care o numim chain începând cu poziția <code>k</code>.

	== ~~Cerinta ==~~		= Cerința =
			Scrieți un program care, pentru orice poziție <code>k</code> afișează lungimea secvenței chain corespunzătoare.

	~~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 <code>N</code>. Pe a doua linie se dau elementele șirului, separate prin spații.

	== ~~Date~~ de intrare ==		= 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".

	~~Pe prima linie a intrării standard se dă valoarea N. Pe a doua linie se dau elementele șirului, separate prin spații.~~		= Restricții și precizări =

	=~~= Date de iesire ==~~		* <code>0 < N < 500.000</code>
			* <code>0 < ai</code> <code>< 1.000.000</code>, pentru fiecare <code>i = 1..N</code>.

	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.		= 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

	~~== Restrictii si precizari ==~~		= Exemplul 2: =
			Intrare
	*0 < N < 500.000		0
	*0 < ai < 1.000.000, pentru fiecare i = 1..N.		123
			Ieșire
	== Exemplul ~~1 ==~~		Datele nu corespund restrictiilor impuse

	~~; intrare~~

	~~:11~~
	~~:3 2 4 2 11~~ 2 ~~7 5 8 10 6~~

	~~; iesire~~

	:~~Datele introduse corespund restrictiilor impuse.~~

	~~:2 2 1 1 0 3 2 2 1 0~~ 0

	~~== Exemplul 2 ==~~

	~~; intrare~~

	:2
	~~:5 6 8 1 3 9 5 7 9 3 5~~

	~~; iesire~~

	: Datele ~~de intrare~~ nu corespund restrictiilor impuse.

	== Rezolvare ==		== Rezolvare ==

	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
			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"

	~~#3239 - chain~~		def main():
			n = int(input())
			a = list(map(int, input().split()))

	~~def find_chain_length~~(~~sequence~~, k):		mesaj = verifica_restrictii(n, a)
	n = ~~len~~(~~sequence~~)		if mesaj != "Datele corespund restrictiilor impuse":
	~~chain_length = 0~~		print(mesaj)
	~~current_position = k - 1~~		return

	~~while current_position <~~ n:		p = [0]*n
	~~current_element~~ = ~~sequence~~[~~current_position~~]		d = [0]*n
	~~next_position = current_position + 1~~

	while ~~next_position < n and sequence~~[~~next_position~~] <= ~~current_element~~:		# O(n)
	~~next_position +~~= 1		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()

	~~if next_position <~~ n:		# chains
	~~chain_length +~~= 1		d[n-1] = 0
	~~current_position~~ = ~~next_position~~		for i in range(n-2, -1, -1):
			if p[i] == 0:
			d[i] = 0
	else:		else:
	~~break~~		d[i] = 1 + d[p[i]]

			print(' '.join(map(str, d)))

	~~return chain_length~~		if __name__ == "__main__":
			main()

	</syntaxhighlight>		</syntaxhighlight>

Aurelia Raluca: /* Rezolvare */

2023-12-17T12:06:38Z

Rezolvare

← Older revision		Revision as of 12:06, 17 December 2023
Line 45:		Line 45:

	== Rezolvare ==		== Rezolvare ==

			<syntaxhighlight lang="python3" line="1">

	#3239 - chain		#3239 - chain

	~~<syntaxhighlight lang="python3" line="1">~~

	def find_chain_length(sequence, k):		def find_chain_length(sequence, k):

Aurelia Raluca: Pagină nouă: == 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. == Cerinta == Scrieți un program care, pentru orice poziție...

2023-12-17T12:05:57Z

Pagină nouă: == 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. == Cerinta == Scrieți un program care, pentru orice poziție...

New page

== 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.

== Cerinta ==

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 iesire ==

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.

== Restrictii si precizari ==

*0 < N < 500.000
*0 < ai < 1.000.000, pentru fiecare i = 1..N.

== Exemplul 1 ==

; intrare

:11
:3 2 4 2 11 2 7 5 8 10 6

; iesire

:Datele introduse corespund restrictiilor impuse.

:2 2 1 1 0 3 2 2 1 0 0

== Exemplul 2 ==

; intrare

:2
:5 6 8 1 3 9 5 7 9 3 5

; iesire

: Datele de intrare nu corespund restrictiilor impuse.

== Rezolvare ==

#3239 - chain

<syntaxhighlight lang="python3" line="1">

def find_chain_length(sequence, k):
n = len(sequence)
chain_length = 0
current_position = k - 1

while current_position < n:
current_element = sequence[current_position]
next_position = current_position + 1

while next_position < n and sequence[next_position] <= current_element:
next_position += 1

if next_position < n:
chain_length += 1
current_position = next_position
else:
break

return chain_length

</syntaxhighlight>