2073 - PlatouK v2 - Revision history

Flaviu at 21:02, 14 May 2023

2023-05-14T21:02:15Z

← Older revision		Revision as of 21:02, 14 May 2023
Line 62:		Line 62:
	; Ieșire		; Ieșire
	: Datele nu corespund restrictiilor impuse		: Datele nu corespund restrictiilor impuse
	~~: 3~~

	== Rezolvare ==		== Rezolvare ==
Line 69:		Line 69:
	# 2073 - PlatouK v2		# 2073 - PlatouK v2

	def ~~lungime_maxima_platou~~(~~arr~~, k, ~~counter=0~~):		def validate_input(k, n, arr):
	if ~~counter~~ == k:		if not 1 <= k <= 100 or not 1 <= n <= 1000000:
	~~max_len, result~~ = ~~0, None~~		return False
	for i in ~~range~~(len(arr)):		if len(arr) != n:
	j = i + 1		return False
	while j < ~~len(arr)~~ and arr[j] == arr[i]:		for i in arr:
	j += 1		if not 0 <= i <= 10000:
	if j - i > ~~max_len~~:		return False
	~~max_len~~ = ~~j - i~~		return True
	~~result~~ = arr[i]
	return ~~max_len~~, ~~result~~
	~~max_len~~, ~~result = 0~~, ~~None~~		def find_longest_plateau(k, arr):
	for i in range(~~len~~(arr) ~~- 1):~~		n = len(arr)
	if ~~arr[i]~~ == ~~arr[i+1]~~:		longest_plateau = 0
	~~tmp_arr~~ = arr~~[:i] +~~ arr~~[i+2:]~~		plateau_element = -1
	~~tmp_arr~~.insert(i, arr~~[i:i~~+2])
	~~len_platou~~, ~~val_platou~~ = ~~lungime_maxima_platou~~(~~tmp_arr~~, ~~k, counter+1~~)		for i in range(n):
	~~if len_platou > max_len:~~		j = i + 1
	~~max_len = len_platou~~		while j < n and arr[i] == arr[j]:
	~~result = val_platou~~		j += 1
	~~return max_len, result~~		plateau_len = j - i
			if plateau_len > longest_plateau:
			longest_plateau = plateau_len
			plateau_element = arr[i]

			return longest_plateau, plateau_element


			def solve(k, n, arr):
			if not validate_input(k, n, arr):
			print("Datele nu corespund restrictiilor impuse.")
			return

			for i in range(k):
			plateau_len, plateau_element = find_longest_plateau(1, arr)
			if plateau_len == 0:
			break
			arr.remove(plateau_element)
			_, new_element = find_longest_plateau(1, arr)
			arr.insert(arr.index(new_element) + 1, plateau_element)

			plateau_len, plateau_element = find_longest_plateau(1, arr)
			print(plateau_len)


	if __name__ == "__main__":		if __name__ == "__main__":
Line 96:		Line 119:
	arr = list(map(int, input().split()))		arr = list(map(int, input().split()))
	p = int(input())		p = int(input())
	if p ~~not in (~~1~~, 2)~~:
	~~print~~(~~"Datele nu corespund restricțiilor impuse."~~)		if p == 1:
			solve(k, n, arr)
	else:		else:
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	~~max_len, result = lungime_maxima_platou(arr, k)~~



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Funcția max_platou~~ care primește ca ~~parametrii lista~~ de ~~numere și~~ numărul maxim de ~~mutări~~ și ~~returnează lungimea maximă a unui platou~~ care ~~poate să apară în șir în urma efectuării operațiilor~~ și ~~elementul din care este format platoul obținut după cele k operații~~.		validare(n, k, sir, cerinta) - Aceasta este o funcție de validare care primește ca parametri: n - numărul de elemente din șir, k - numărul maxim de operații permise, sir - lista cu elemente din șir și cerinta - un intreg care specifica cerinta (1 sau 2). Funcția validează inputul și returnează True dacă valorile de intrare sunt corecte, altfel returnează False.

	~~Funcția parcurge lista și găsește cel mai lung~~ platou ~~care se poate forma într~~-un ~~număr maxim de k mutări~~ și returnează lungimea ~~acestuia și valoarea elementului din~~ care ~~este format~~. ~~Pentru a găsi acest platou se realizează următoarele operații:~~		lungime_platou(platou) - Această funcție primește ca parametru un platou, adică o secvență formată din valori identice. Funcția calculează și returnează lungimea platoului, adică numărul de elemente care îl formează.

	~~Pentru fiecare platou~~ din ~~listă:~~		rezolva(sir, k) - Această funcție primește ca parametri: sir - lista cu elemente din șir și k - numărul maxim de operații permise. Funcția calculează lungimea maximă a unui platou care poate să apară în șir în urma efectuării operației de maxim k ori și elementul din care este format platoul obținut după cele k operații și returnează aceste valori.
	~~Se încearcă mutarea acestuia într~~-~~o poziție arbitrară~~
	Se calculează lungimea maximă a unui platou ~~din șirul obținut după mutare și numărul~~ de ~~mutări efectuate pentru a ajunge la acel șir~~
	~~Dacă lungimea maximă a platoului din șirul obținut este mai mare decât cea a platoului~~ maxim ~~găsit până acum, se actualizează lungimea maximă~~ și elementul din care este format platoul ~~maxim~~
	~~Funcția main care se execută doar dacă acest fișier este rulat direct, nu importat în altul. Funcția citește datele de intrare, validează~~ aceste ~~date și apelează funcția max_platou pentru a afișa rezultatul~~.

	În funcția ~~main~~, se ~~citesc datele de intrare și se validează, adică se verifică dacă acestea corespund condițiilor impuse în enunțul problemei~~. ~~Dacă datele~~ de ~~intrare sunt corecte~~, ~~se apelează funcția max_platou pentru a calcula lungimea maximă a unui platou care poate să apară în șir în urma efectuării operațiilor~~ și ~~elementul din care este format platoul obținut după cele k operații. Dacă datele nu sunt corecte, se~~ afișează ~~mesajul "Datele nu corespund restricțiilor impuse~~."		main() - Aceasta este funcția principală a programului, care se execută atunci când rulăm scriptul. Funcția citeste input-ul de la utilizator, validează inputul și apoi calculează și afișează rezultatul.

Flaviu at 22:40, 13 May 2023

2023-05-13T22:40:13Z

← Older revision		Revision as of 22:40, 13 May 2023
Line 43:		Line 43:
	* dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare		* dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare
	toate testele au soluție		toate testele au soluție

			== Exemplu 1 ==
	; Intrare		; Intrare
	: 2		: 2
Line 49:		Line 51:
	: 1		: 1
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~		: Datele sunt introduse corect.
	: Datele sunt introduse ~~correct~~.
	: 4		: 4

			== Exemplu 2 ==
			; Intrare
			: 2
			: 6
			: 2 2 2 3 3 3
			: 1
			; Ieșire
			: Datele nu corespund restrictiilor impuse
			: 3

	== Rezolvare ==		== Rezolvare ==
Line 58:		Line 69:
	# 2073 - PlatouK v2		# 2073 - PlatouK v2

	def ~~citire_lista~~():		def lungime_maxima_platou(arr, k, counter=0):
	~~try:~~		if counter == k:
	k = ~~int(input())~~		max_len, result = 0, None
	n = ~~int(input())~~		for i in range(len(arr)):
	~~lista~~ = ~~list(map(int~~, ~~input().split()))~~		j = i + 1
	~~p = int~~(~~input~~())		while j < len(arr) and arr[j] == arr[i]:
	~~return k, lista, p~~		j += 1
	~~except~~:		if j - i > max_len:
	~~print("Datele nu corespund restrictiilor impuse.")~~		max_len = j - i
			result = arr[i]
	~~def rezolva~~(~~k, lista~~):		return max_len, result
	~~try~~:		max_len, result = 0, None
	~~# calculam dictionarul frecventelor~~		for i in range(len(arr) - 1):
	~~frecvente~~ = {}		if arr[i] == arr[i+1]:
	~~for element in lista:~~		tmp_arr = arr[:i] + arr[i+2:]
	~~frecvente~~[~~element~~] ~~= frecvente.get(element, 0) + 1~~		tmp_arr.insert(i, arr[i:i+2])
			len_platou, val_platou = lungime_maxima_platou(tmp_arr, k, counter+1)
	~~# gasim elementul cu cea mai mare frecventa~~		if len_platou > max_len:
	~~max_frecventa~~ = ~~max(frecvente.values())~~		max_len = len_platou
	~~element_max_frecventa = max(k~~ for ~~k, v~~ in ~~frecvente.items~~(~~) if v == max_frecventa)~~		result = val_platou
			return max_len, result
	~~# calculam lungimea maxima a unui platou dupa k operatii~~
	~~lungime_maxima = min(max_frecventa + k,~~ len(~~lista~~))
	~~return lungime_maxima~~ if p == 1 ~~else element_max_frecventa~~
	~~except~~:
	~~print("Datele nu corespund restrictiilor impuse.")~~

	~~def valideaza(valoare)~~:
	~~try~~:
	~~if isinstance~~(~~valoare~~, ~~int~~):
	~~print~~(~~"Datele sunt introduse corect."~~)
	~~print(valoare)~~
	~~else~~:
	~~print("Datele sunt introduse corect.")~~
	~~print(*valoare)~~
	~~except:~~
	~~print("Datele nu corespund restrictiilor impuse.")~~

	if __name__ == "__main__":		if __name__ == "__main__":
	k, ~~lista,~~ p = ~~citire_lista~~()		k = int(input())
	~~rezultat = rezolva~~(k, ~~lista~~)		n = int(input())
	~~valideaza~~(~~rezultat~~)		arr = list(map(int, input().split()))
			p = int(input())
			if p not in (1, 2):
			print("Datele nu corespund restricțiilor impuse.")
			else:
			print("Datele sunt introduse corect.")
			max_len, result = lungime_maxima_platou(arr, k)


Line 105:		Line 106:
	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~citire_lista()~~ primește ~~datele~~ de ~~intrare~~ și ~~le citește folosind funcții predefinite~~ în ~~Python~~. ~~Aceasta~~ returnează ~~un tuplu~~ format din k, ~~lista~~ și p.		Funcția max_platou care primește ca parametrii lista de numere și numărul maxim de mutări și returnează lungimea maximă a unui platou care poate să apară în șir în urma efectuării operațiilor și elementul din care este format platoul obținut după cele k operații.

			Funcția parcurge lista și găsește cel mai lung platou care se poate forma într-un număr maxim de k mutări și returnează lungimea acestuia și valoarea elementului din care este format. Pentru a găsi acest platou se realizează următoarele operații:

			Pentru fiecare platou din listă:
			Se încearcă mutarea acestuia într-o poziție arbitrară
			Se calculează lungimea maximă a unui platou din șirul obținut după mutare și numărul de mutări efectuate pentru a ajunge la acel șir
			Dacă lungimea maximă a platoului din șirul obținut este mai mare decât cea a platoului maxim găsit până acum, se actualizează lungimea maximă și elementul din care este format platoul maxim
			Funcția main care se execută doar dacă acest fișier este rulat direct, nu importat în altul. Funcția citește datele de intrare, validează aceste date și apelează funcția max_platou pentru a afișa rezultatul.

	~~Funcția rezolva(k~~, ~~lista) primește k și lista citite~~ de la intrare și ~~implementează algoritmul descris~~ în ~~cerință~~ pentru a ~~determina~~ lungimea maximă a unui platou ~~sau~~ elementul din care este format platoul~~, în funcție de cerința specificată~~. ~~Pentru a face acest lucru~~, ~~funcția calculează mai întâi un dicționar al frecvențelor elementelor din lista și găsește elementul cu cea mai mare frecvență~~. ~~Pentru a găsi lungimea~~		În funcția main, se citesc datele de intrare și se validează, adică se verifică dacă acestea corespund condițiilor impuse în enunțul problemei. Dacă datele de intrare sunt corecte, se apelează funcția max_platou pentru a calcula lungimea maximă a unui platou care poate să apară în șir în urma efectuării operațiilor și elementul din care este format platoul obținut după cele k operații. Dacă datele nu sunt corecte, se afișează mesajul "Datele nu corespund restricțiilor impuse."

Flaviu at 19:00, 27 April 2023

2023-04-27T19:00:57Z

← Older revision		Revision as of 19:00, 27 April 2023
Line 32:		Line 32:

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va ~~afisa lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni de maxim k ori sau elementul din care este format platoul~~.		Dacă datele sunt introduse corect, pe ecran se va afișa:
			'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 47:		Line 49:
	: 1		: 1
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 4		: 4

Line 55:		Line 59:

	def citire_lista():		def citire_lista():
	k = int(input())		try:
	n = int(input())		k = int(input())
	lista = list(map(int, input().split()))		n = int(input())
	p = int(input())		lista = list(map(int, input().split()))
	return k, lista, p		p = int(input())
			return k, lista, p
			except:
			print("Datele nu corespund restrictiilor impuse.")

	def rezolva(k, lista):		def rezolva(k, lista):
	# calculam dictionarul frecventelor		try:
	frecvente = {}		# calculam dictionarul frecventelor
	for element in lista:		frecvente = {}
	frecvente[element] = frecvente.get(element, 0) + 1		for element in lista:
			frecvente[element] = frecvente.get(element, 0) + 1
	# gasim elementul cu cea mai mare frecventa
	max_frecventa = max(frecvente.values())		# gasim elementul cu cea mai mare frecventa
	element_max_frecventa = max(k for k, v in frecvente.items() if v == max_frecventa)		max_frecventa = max(frecvente.values())
			element_max_frecventa = max(k for k, v in frecvente.items() if v == max_frecventa)
	# calculam lungimea maxima a unui platou dupa k operatii
	lungime_maxima = min(max_frecventa + k, len(lista))		# calculam lungimea maxima a unui platou dupa k operatii
	return lungime_maxima if p == 1 else element_max_frecventa		lungime_maxima = min(max_frecventa + k, len(lista))
			return lungime_maxima if p == 1 else element_max_frecventa
			except:
			print("Datele nu corespund restrictiilor impuse.")

	def valideaza(valoare):		def valideaza(valoare):
	if isinstance(valoare, int):		try:
	print(valoare)		if isinstance(valoare, int):
	else:		print("Datele sunt introduse corect.")
	print(*valoare)		print(valoare)
			else:
			print("Datele sunt introduse corect.")
			print(*valoare)
			except:
			print("Datele nu corespund restrictiilor impuse.")

	if __name__ == "__main__":		if __name__ == "__main__":
Line 88:		Line 100:
	rezultat = rezolva(k, lista)		rezultat = rezolva(k, lista)
	valideaza(rezultat)		valideaza(rezultat)

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2073/platouk-v2 - PlatouK v2] ---- == Cerinţa == Fiind dat un șir de numere, numim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează. De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem: platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;...

2023-04-17T20:32:03Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2073/platouk-v2 - PlatouK v2] ---- == Cerinţa == Fiind dat un șir de numere, numim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează. De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem: platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;...

New page

Sursa: [https://www.pbinfo.ro/probleme/2073/platouk-v2 - PlatouK v2]
----
== Cerinţa ==
Fiind dat un șir de numere, numim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem:

platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;
platourile 7 7 (cel care începe în poziţia a patra) şi 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
platoul 3 care are lungimea 1.
În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziţii consecutive!

Asupra unui şir se poate efectua următoarea operaţiune:

se extrage un platou la alegere;
se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.
De exemplu, dacă avem următorul şir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În şirul rezultat inserăm platoul 2 2 (pe care l-am extras în pasul anterior) în poziţia a doua şi obţinem şirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8.
Să se scrie un program care citește un șir de n numere naturale din intervalul [0,10000] și un număr k și determină:

lungimea maximă a unui platou care poate să apară în şir în urma efectuării operaţiunii de mai sus de maxim k ori
elementul din care este format platoul obținut după cele k operațiuni

== Date de intrare ==
Programul va citi:

* pe prima linie un număr natural k;
* pe a doua linie un număr natural n;
* pe a treia linie un şir de n numere naturale separate prin câte un spaţiu.
* pe a patra linie p, care reprezinta cerința; p poate fi 1 sau 2

== Date de ieșire ==
Programul va afisa lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni de maxim k ori sau elementul din care este format platoul.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000000
* 1 ≤ k ≤ 100
* pentru cerința 1 – 50% din punctaj
* pentru cerința 2 – 50% din punctaj
* dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare
toate testele au soluție
; Intrare
: 2
: 16
: 2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
: 1
; Ieșire
: 4

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2073 - PlatouK v2

def citire_lista():
k = int(input())
n = int(input())
lista = list(map(int, input().split()))
p = int(input())
return k, lista, p

def rezolva(k, lista):
# calculam dictionarul frecventelor
frecvente = {}
for element in lista:
frecvente[element] = frecvente.get(element, 0) + 1

# gasim elementul cu cea mai mare frecventa
max_frecventa = max(frecvente.values())
element_max_frecventa = max(k for k, v in frecvente.items() if v == max_frecventa)

# calculam lungimea maxima a unui platou dupa k operatii
lungime_maxima = min(max_frecventa + k, len(lista))
return lungime_maxima if p == 1 else element_max_frecventa

def valideaza(valoare):
if isinstance(valoare, int):
print(valoare)
else:
print(*valoare)

if __name__ == "__main__":
k, lista, p = citire_lista()
rezultat = rezolva(k, lista)
valideaza(rezultat)

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citire_lista() primește datele de intrare și le citește folosind funcții predefinite în Python. Aceasta returnează un tuplu format din k, lista și p.

Funcția rezolva(k, lista) primește k și lista citite de la intrare și implementează algoritmul descris în cerință pentru a determina lungimea maximă a unui platou sau elementul din care este format platoul, în funcție de cerința specificată. Pentru a face acest lucru, funcția calculează mai întâi un dicționar al frecvențelor elementelor din lista și găsește elementul cu cea mai mare frecvență. Pentru a găsi lungimea