2405 - politic - Revision history

Monica Dragos at 22:42, 14 May 2023

2023-05-14T22:42:24Z

← Older revision		Revision as of 22:42, 14 May 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/304/secvente 2405 - politic]		Sursa: [https://www.pbinfo.ro/probleme/304/secvente 2405 - politic]
	----		----


			== Cerinţa ==
	În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1, 2, 3, 5 şi 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1, 2 și 3 și altul din 5 și 6.)		În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1, 2, 3, 5 şi 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1, 2 și 3 și altul din 5 și 6.)
	Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați.		Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați.
	Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeași coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1, 2, 4, 5, 7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5.		Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeași coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1, 2, 4, 5, 7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5.

	~~== Cerinţa ==~~
	Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară.		Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară.

Line 14:		Line 15:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire politic.out va conține:~~
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', ~~apoi pe un rând nou '''~~prima linie numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', fișierul de ieșire politic.out conține prima linie numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat''', 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 ==

Flaviu at 22:06, 14 May 2023

2023-05-14T22:06:16Z

← Older revision		Revision as of 22:06, 14 May 2023
Line 27:		Line 27:
	: 1 2 3 5 6 8 10 11 14 15		: 1 2 3 5 6 8 10 11 14 15
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: politic.out		: politic.out
	~~: Datele sunt introduse correct.~~
	: 5		: 5
	: 4		: 4
Line 38:		Line 38:
	: 0 7 8 9 1 2 3 4 5		: 0 7 8 9 1 2 3 4 5
	; Ieșire		; Ieșire
	~~: politic.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 46:		Line 45:
	# 2405 - politic		# 2405 - politic

	def ~~read_input~~():		def validate_input(n, arr):
	n = ~~int(input())~~		if n <= 0 or n > 20000:
	~~parties~~ = ~~list(map(int, input().split())~~)		return False
	return ~~n, parties~~		if any(x <= 0 or x > 30000 for x in arr):
			return False
			return True

	def ~~solve~~(~~n, parties~~):		def count_sequences(arr):
	~~# numărul de partide~~		cnt = 1
	~~num_parties~~ = 0		max_cnt = 1
	for i in range(n):		for i in range(1, len(arr)):
	if ~~i == 0 or parties~~[i] ~~- parties~~[i-1] ~~> 1~~:		if arr[i] > arr[i-1]:
	~~num_parties~~ += 1		cnt += 1
	~~# numărul de coaliții majoritare~~		if cnt > max_cnt:
	~~num_majority_coalitions = 0~~		max_cnt = cnt
	~~for i in range(num_parties):~~		else:
	~~for j in range(i+1, num_parties):~~		cnt = 1
	if ~~parties[j] - parties[i] == j - i~~:		return max_cnt
	~~# partidele i și j pot forma o coaliție~~
	~~left~~ = ~~i-1 if i > 0 else None~~
	~~right = j+1 if j < num_parties-1~~ else ~~None~~
	~~# verificăm dacă toate partidele între i și j sunt în coaliție~~
	~~if (left is None or parties[i] - parties[left] > 1) and (right is None or parties[right] - parties[j] > 1)~~:
	~~# am găsit o coaliție majoritară~~
	~~num_majority_coalitions +~~= 1
	return ~~num_parties, num_majority_coalitions~~

	def ~~validate_output~~(~~expected~~, ~~actual~~):		def count_coalitions(arr):
	return ~~expected == actual~~		cnt = 0
			for i in range(len(arr)):
			for j in range(i+1, len(arr)):
			diff = abs(arr[i] - arr[j])
			if diff == 1:
			break
			else:
			for k in range(i+1, j):
			if abs(arr[k] - arr[i]) > diff and abs(arr[k] - arr[j]) > diff:
			continue
			else:
			break
			else:
			cnt += 1
			return cnt

	if __name__ == '__main__':		if __name__ == "__main__":
	n~~, parties~~ = ~~read_input~~()		n = int(input())
	~~num_parties, num_majority_coalitions~~ = ~~solve~~(n, ~~parties~~)		arr = list(map(int, input().split()))
	~~is_valid = validate_output~~(4, ~~num_parties~~)		if validate_input(n, arr):
	~~if is_valid~~:
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
			print(count_sequences(arr))
			print(count_coalitions(arr))
	else:		else:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	~~print(num_parties)~~
	~~print(num_majority_coalitions)~~


Line 89:		Line 95:
	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~read_input citește datele de intrare și le returnează sub forma unei perechi~~ (n, ~~parties~~)~~, unde~~ n este ~~numărul de deputați~~, ~~iar parties este lista cu orientările politice ale acestora~~.		Funcția validate_input(n, arr) verifică dacă numărul n este între 1 și 20000 și dacă fiecare element din array-ul arr este între 1 și 30000. Dacă datele nu corespund acestor restricții, funcția returnează False, altfel returnează True.
	Funcția ~~solve primește datele~~ de ~~intrare~~ și ~~calculează~~ numărul de ~~partide~~ și numărul de ~~coaliții majoritare~~. ~~Pentru a calcula numărul~~ de ~~partide~~, ~~parcurgem lista parties~~ și ~~numărăm câte ori întâlnim un număr care nu~~ este ~~consecutiv~~ cu ~~ultimul număr întâlnit~~. ~~Pentru a calcula numărul de coaliții majoritare~~, ~~parcurgem toate perechile de partide~~ care ~~pot forma~~ o ~~coaliție (adică două partide a căror~~ diferență ~~este~~ egală cu ~~diferența~~ dintre ~~pozițiile lor în listă)~~ și ~~verificăm dacă toate partidele între ele sunt în coaliție~~.
	~~Funcția validate_output validează rezultatul returnat~~ de funcția ~~solve, comparându~~-~~l cu rezultatul așteptat~~.		Funcția count_sequences(arr) numără cel mai lung șir crescător de elemente consecutive din array-ul arr. Inițial, variabila cnt este setată la 1, pentru că fiecare element din array poate fi considerat un șir crescător de lungime 1. Apoi, se parcurge array-ul și se verifică dacă elementul curent este mai mare decât cel anterior. Dacă da, se crește numărul de elemente din șirul crescător curent, și se actualizează max_cnt dacă valoarea lui cnt este mai mare. Dacă elementul curent este mai mic sau egal decât cel anterior, se resetează cnt la 1. La final, funcția returnează max_cnt, lungimea maximă a unui șir crescător de elemente consecutive.
	~~În funcția main, citim~~ datele de intrare~~, rezolvăm problema apelând~~ funcția ~~solve și afișăm rezultatul~~.
	~~Această soluție are complexitatea O(N^2)~~, ~~unde N este numărul~~ de ~~deputați din parlament. Pentru~~ valorile ~~maxime ale lui N (20~~.~~000)~~, ~~această soluție ar~~		Funcția count_coalitions(arr) numără numărul de sub-șiruri neadiacente din array-ul arr care au diferența maximă între cel mai mare și cel mai mic element mai mică sau egală cu 1. Funcția parcurge fiecare pereche de elemente din array, calculează diferența dintre ele și verifică dacă aceasta este mai mare sau egală cu 2. Dacă da, atunci verifică dacă există vreun alt element între cele două care să aibă o diferență mai mică sau egală cu cea dintre cele două. Dacă există un astfel de element, atunci sub-șirul nu este valid și se trece la următoarea pereche de elemente. Dacă nu există un astfel de element, atunci sub-șirul este valid și se crește numărul de sub-șiruri găsite. La final, funcția returnează numărul de sub-șiruri valide găsite.

			Funcția __main__ primește datele de intrare și le validează folosind funcția validate_input. Dacă datele sunt valide, afișează un mesaj de confirmare și calculează valorile cerute folosind funcțiile count_sequences și count_coalitions. Dacă datele nu sunt valide, afișează un mesaj de eroare.

Flaviu at 08:15, 3 May 2023

2023-05-03T08:15:09Z

← Older revision		Revision as of 08:15, 3 May 2023
Line 16:		Line 16:
	Fișierul de ieșire politic.out va conține:		Fișierul de ieșire politic.out va conține:
	Dacă datele sunt introduse corect, pe ecran se va afișa:		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."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''prima linie numărul C, reprezentând numărul de secvenţe cu elementele ordonate crescător din şirul dat''', 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 ==
	* 0 < N ≤ 20.000		* 0 < N ≤ 20.000
	* numerele din șir sunt mai mici sau egale cu 30.000		* numerele din șir sunt mai mici sau egale cu 30.000
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: politic.in
	: 10		: 10
	: 1 2 3 5 6 8 10 11 14 15		: 1 2 3 5 6 8 10 11 14 15
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: politic.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 5		: 5
	: 4		: 4

			== Exemplu 2 ==
			; Intrare
			: politic.in
			: 20
			: 0 7 8 9 1 2 3 4 5
			; Ieșire
			: politic.out
			: Datele nu corespund restricțiilor impuse.

	== Rezolvare ==		== Rezolvare ==

Flaviu at 15:01, 28 April 2023

2023-04-28T15:01:14Z

← Older revision		Revision as of 15:01, 28 April 2023
Line 14:		Line 14:

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire politic.out va conține pe ~~prima linie~~ un ~~număr natural nenul X~~, reprezentând ~~numărul de partide din parlament~~, ~~iar a doua linie~~ va ~~conține un alt număr natural nenul Y care reprezintă numărul de coaliții majoritare care se pot forma~~.		Fișierul de ieșire politic.out va conține:
			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 24:		Line 26:
	: 1 2 3 5 6 8 10 11 14 15		: 1 2 3 5 6 8 10 11 14 15
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 5		: 5
	: 4		: 4
Line 58:		Line 62:

	def validate_output(expected, actual):		def validate_output(expected, actual):
	~~assert~~ expected == actual~~, f"Expected {expected}, but got {actual}"~~		return expected == actual

	if __name__ == '__main__':		if __name__ == '__main__':
	n, parties = read_input()		n, parties = read_input()
	num_parties, num_majority_coalitions = solve(n, parties)		num_parties, num_majority_coalitions = solve(n, parties)
			is_valid = validate_output(4, num_parties)
			if is_valid:
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")
	print(num_parties)		print(num_parties)
	print(num_majority_coalitions)		print(num_majority_coalitions)

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 2405 - politic] ---- În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina f...

2023-04-18T07:28:30Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 2405 - politic] ---- În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina f...

New page

Sursa: [https://www.pbinfo.ro/probleme/304/secvente 2405 - politic]
----
În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1, 2, 3, 5 şi 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1, 2 și 3 și altul din 5 și 6.)
Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați.
Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeași coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1, 2, 4, 5, 7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5.

== Cerinţa ==
Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară.

== Date de intrare ==
Fișierul de intrare politic.in conține pe prima linie un număr natural nenul N, reprezentând numărul de deputați din parlament. Pe a doua linie se află N numere naturale nenule separate prin câte un spațiu, ordonate strict crescător, reprezentând doctrinele parlamentarilor.

== Date de ieșire ==
Fișierul de ieșire politic.out va conține pe prima linie un număr natural nenul X, reprezentând numărul de partide din parlament, iar a doua linie va conține un alt număr natural nenul Y care reprezintă numărul de coaliții majoritare care se pot forma.

== Restricţii şi precizări ==
* 0 < N ≤ 20.000
* numerele din șir sunt mai mici sau egale cu 30.000
== Exemplu ==
; Intrare
: 10
: 1 2 3 5 6 8 10 11 14 15
; Ieșire
: 5
: 4

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2405 - politic

def read_input():
n = int(input())
parties = list(map(int, input().split()))
return n, parties

def solve(n, parties):
# numărul de partide
num_parties = 0
for i in range(n):
if i == 0 or parties[i] - parties[i-1] > 1:
num_parties += 1
# numărul de coaliții majoritare
num_majority_coalitions = 0
for i in range(num_parties):
for j in range(i+1, num_parties):
if parties[j] - parties[i] == j - i:
# partidele i și j pot forma o coaliție
left = i-1 if i > 0 else None
right = j+1 if j < num_parties-1 else None
# verificăm dacă toate partidele între i și j sunt în coaliție
if (left is None or parties[i] - parties[left] > 1) and (right is None or parties[right] - parties[j] > 1):
# am găsit o coaliție majoritară
num_majority_coalitions += 1
return num_parties, num_majority_coalitions

def validate_output(expected, actual):
assert expected == actual, f"Expected {expected}, but got {actual}"

if __name__ == '__main__':
n, parties = read_input()
num_parties, num_majority_coalitions = solve(n, parties)
print(num_parties)
print(num_majority_coalitions)

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare și le returnează sub forma unei perechi (n, parties), unde n este numărul de deputați, iar parties este lista cu orientările politice ale acestora.
Funcția solve primește datele de intrare și calculează numărul de partide și numărul de coaliții majoritare. Pentru a calcula numărul de partide, parcurgem lista parties și numărăm câte ori întâlnim un număr care nu este consecutiv cu ultimul număr întâlnit. Pentru a calcula numărul de coaliții majoritare, parcurgem toate perechile de partide care pot forma o coaliție (adică două partide a căror diferență este egală cu diferența dintre pozițiile lor în listă) și verificăm dacă toate partidele între ele sunt în coaliție.
Funcția validate_output validează rezultatul returnat de funcția solve, comparându-l cu rezultatul așteptat.
În funcția main, citim datele de intrare, rezolvăm problema apelând funcția solve și afișăm rezultatul.
Această soluție are complexitatea O(N^2), unde N este numărul de deputați din parlament. Pentru valorile maxime ale lui N (20.000), această soluție ar