Sovago Rares-Andrei: /* Date de intrare */

2023-04-29T16:21:09Z

Date de intrare

← Older revision		Revision as of 16:21, 29 April 2023
Line 7:		Line 7:
	== Date de intrare ==		== Date de intrare ==

	Prima linie a fișierului de intrare tort.in conține numărul '''N'''. A doua linie conține valorile a1, …, aN, separate prin spații.		Prima linie a fișierului de intrare tort.in conține numărul '''N'''. A doua linie conține valorile '''a1, …, aN''', separate prin spații.

	== Date de intrare ==		== Date de intrare ==

Sovago Rares-Andrei: /* Date de intrare */

2023-04-29T16:20:51Z

Date de intrare

← Older revision		Revision as of 16:20, 29 April 2023
Line 7:		Line 7:
	== Date de intrare ==		== Date de intrare ==

	Prima linie a fișierului de intrare tort.in conține numărul N. A doua linie conține valorile a1, …, aN, separate prin spații.		Prima linie a fișierului de intrare tort.in conține numărul '''N'''. A doua linie conține valorile a1, …, aN, separate prin spații.

	== Date de intrare ==		== Date de intrare ==

Sovago Rares-Andrei: /* Rezolvare */

2023-04-08T08:08:09Z

Rezolvare

← Older revision		Revision as of 08:08, 8 April 2023
Line 63:		Line 63:
	def validare_input(n, secventa):		def validare_input(n, secventa):
	if n < 2 or n > 200000:		if n < 2 or n > 200000:
	~~print("Datele nu corespund restricțiilor impuse.")~~		return False
	~~sys.exit(0)~~
	for numar in secventa:		for numar in secventa:
	if numar < 1 or numar > 400000:		if numar < 1 or numar > 400000:
	~~print("Datele nu corespund restricțiilor impuse.")~~		return False
	~~sys.exit(0)~~		return True
	return ~~sum(secventa)~~


	~~print("Datele sunt introduse corect.")~~


Line 93:		Line 88:

	def rezolvare(n, secventa):		def rezolvare(n, secventa):
	suma_totala = ~~validare_input~~(n, secventa)		suma_totala = sum(secventa)

	for i in range(2, n + 2):		for i in range(2, n + 2):
Line 114:		Line 109:
	secventa = list(map(int, fin.readline().split()))		secventa = list(map(int, fin.readline().split()))

	~~suma_totala =~~ validare_input(dimensiune, secventa)		if not validare_input(dimensiune, secventa):
	~~if dimensiune < 2 or dimensiune > 200000~~:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	sys.exit(0)		sys.exit(0)

			print("Datele sunt introduse corect.")
	with open("tort.out", "w") as fout:		with open("tort.out", "w") as fout:
	ans = rezolvare(dimensiune, secventa)		ans = rezolvare(dimensiune, secventa)
	fout.write(str(ans))		fout.write(str(ans))

Nagy Lenard at 20:08, 7 April 2023

2023-04-07T20:08:19Z

← Older revision		Revision as of 20:08, 7 April 2023
Line 59:		Line 59:
	# 3718 - Tort2		# 3718 - Tort2
	import sys		import sys


	def validare_input(n, secventa):		def validare_input(n, secventa):
Line 69:		Line 70:
	sys.exit(0)		sys.exit(0)
	return sum(secventa)		return sum(secventa)


	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")

Line 87:		Line 90:

	return False		return False


	def rezolvare(n, secventa):		def rezolvare(n, secventa):
	suma_totala = validare_input(n, secventa)		suma_totala = validare_input(n, secventa)
Line 102:		Line 107:

	return 0		return 0


	if __name__ == "__main__":		if __name__ == "__main__":
Line 116:		Line 122:
	ans = rezolvare(dimensiune, secventa)		ans = rezolvare(dimensiune, secventa)
	fout.write(str(ans))		fout.write(str(ans))

Sovago Rares-Andrei: Pagină nouă: ==Cerința== Alexandra, prințesa Regatului Visurilor a primit un tort și vrea să-l împartă cu prietenii ei. Astfel ea va organiza o petrecere unde îi va invita. Tortul Alexandrei este format din N bucăți, iar a i-a bucată are ai cireșe. Alexandra va împărți tortul în mai multe secvențe continue de bucăți, astfel încât fiecare bucată este inclusă în exact o secvență, și fiecare secvență conține cel puțin o bucată de tort. Prima secvență – cea...

2023-04-07T17:46:38Z

Pagină nouă: ==Cerința== Alexandra, prințesa Regatului Visurilor a primit un tort și vrea să-l împartă cu prietenii ei. Astfel ea va organiza o petrecere unde îi va invita. Tortul Alexandrei este format din N bucăți, iar a i-a bucată are ai cireșe. Alexandra va împărți tortul în mai multe secvențe continue de bucăți, astfel încât fiecare bucată este inclusă în exact o secvență, și fiecare secvență conține cel puțin o bucată de tort. Prima secvență – cea...

New page

==Cerința==

Alexandra, prințesa Regatului Visurilor a primit un tort și vrea să-l împartă cu prietenii ei. Astfel ea va organiza o petrecere unde îi va invita. Tortul Alexandrei este format din N bucăți, iar a i-a bucată are ai cireșe. Alexandra va împărți tortul în mai multe secvențe continue de bucăți, astfel încât fiecare bucată este inclusă în exact o secvență, și fiecare secvență conține cel puțin o bucată de tort. Prima secvență – cea care conține prima bucată – o va mânca în noaptea de dinaintea petrecerii, iar restul bucăților le va da celorlalți prieteni invitați. Pentru a nu-i supăra, Alexandra vrea ca fiecare secvență dată unui prieten să conțină la fel de multe cireșe ca oricare altă secvență dată unui prieten (dar nu neapărat la fel de multe cireșe ca aceea mâncată de ea înaintea petrecerii). Alexandra trebuie să invite cel puțin un prieten la petrecere.
Dându-se N și șirul a, să se afle numărul de moduri în care Alexandra ar putea să împartă tortul în secvențe continue astfel încât să se respecte condițiile din enunț. Două moduri de a împărți tortul se consideră a fi distincte dacă și numai dacă există în unul o secvență care nu există în celălalt (dacă am reprezenta un mod de împărțire în secvențe prin intermediul șirului crescător al indicilor de început pentru fiecare secvență din acea împărțire, două moduri de împărțire sunt distincte dacă șirurile de indici asociate lor sunt diferite).

Formal, dându-se un șir de numere, se vrea să aflăm numărul de moduri de a împărți șirul în cel puțin două subsecvențe, astfel încât sumele elementelor tuturor subsecvențelor să fie egale, prima putând să aibă suma elementelor diferită de a celorlalte.
== Date de intrare ==

Prima linie a fișierului de intrare tort.in conține numărul N. A doua linie conține valorile a1, …, aN, separate prin spații.

== Date de intrare ==

Fișierul de intrare cosuri.in conține pe prima linie două numere naturale '''T''' și '''N''' separate printr-un spațiu. A doua linie a fișierului conține cele '''2•N''' numere naturale '''C1''', '''C2''',…, '''C2•N''', separate prin câte un spațiu.

== Date de ieșire ==

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Singura linie a fișierului de ieșire tort.out va conține numărul cerut. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

== Restricţii şi precizări ==
*1 ≤ N ≤ 200.000
*1 ≤ ai ≤ 400.000
*a1 + ... + aN ≤ 400.000
*Pentru 12 puncte, N ≤ 12
*Pentru alte 12 puncte, 1 ≤ N ≤ 100 și a1 = ... = aN = 1
*Pentru alte 20 puncte, 1 ≤ N ≤ 100
*Pentru alte 28 puncte, 1 ≤ N ≤ 1000 și a1 + ... + aN ≤ 2000
*Pentru alte 28 puncte, fără alte restricții
== Exemple ==
===Exemplul 1===
; ''tort.in''
:5
:1 1 2 1 1
; ''ecran''
:Datele sunt introduse corect.
; ''tort.out''
:1

===Exemplul 2===
; ''tort.in''
:7
:3 1 4 1 5 9 2
; ''ecran''
:Datele sunt introduse corect.
; ''tort.out''
:4
===Exemplul 3===
; ''tort.in''
:1
:1000000
; ''ecran''
:Datele nu corespund restricțiilor impuse.
; ''tort.out''
:
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 3718 - Tort2
import sys

def validare_input(n, secventa):
if n < 2 or n > 200000:
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
for numar in secventa:
if numar < 1 or numar > 400000:
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
return sum(secventa)
print("Datele sunt introduse corect.")

def poate_imparti_secventa(secventa, n, suma_dorita, index, bucata_curenta, prieteni):
if prieteni == 1:
return False

if bucata_curenta == suma_dorita:
if prieteni == 2:
return True
return poate_imparti_secventa(secventa, n, suma_dorita, 0, 0, prieteni - 1)

for i in range(index, n):
if secventa[i] + bucata_curenta <= suma_dorita:
if poate_imparti_secventa(secventa, n, suma_dorita, i + 1, secventa[i] + bucata_curenta, prieteni):
return True

return False
def rezolvare(n, secventa):
suma_totala = validare_input(n, secventa)

for i in range(2, n + 2):
if suma_totala % i != 0:
continue

suma_dorita = suma_totala // i
if secventa[0] > suma_dorita:
continue

if poate_imparti_secventa(secventa, n, suma_dorita, 1, secventa[0], i):
return i - 1

return 0

if __name__ == "__main__":
with open("tort.in", "r") as fin:
dimensiune = int(fin.readline().strip())
secventa = list(map(int, fin.readline().split()))

suma_totala = validare_input(dimensiune, secventa)
if dimensiune < 2 or dimensiune > 200000:
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)

with open("tort.out", "w") as fout:
ans = rezolvare(dimensiune, secventa)
fout.write(str(ans))

</syntaxhighlight>

==Explicatie==

Funcția validare_input(n, secventa) primește doi parametri: n, care reprezintă numărul de elemente din secvență și secventa, o listă de n numere întregi. Această funcție verifică dacă datele de intrare îndeplinesc condițiile impuse: n trebuie să fie cuprins între 2 și 200000, iar fiecare element din secventa trebuie să fie cuprins între 1 și 400000. Dacă datele de intrare nu îndeplinesc aceste condiții, se afișează un mesaj corespunzător și se iese din program cu ajutorul funcției sys.exit(0). Dacă datele de intrare sunt valide, se calculează și se returnează suma elementelor din secvență.

Funcția poate_imparti_secventa(secventa, n, suma_dorita, index, bucata_curenta, prieteni) primește șase parametri:

secventa: lista de numere întregi care reprezintă secvența de împărțit
n: numărul de elemente din secvență
suma_dorita: suma dorită a bucăților, adică suma totală împărțită la numărul de prieteni
index: indexul elementului curent din secvență
bucata_curenta: suma curentă a bucății de împărțit
prieteni: numărul de prieteni rămași
Această funcție verifică dacă secvența secventa poate fi împărțită în prieteni bucăți astfel încât fiecare bucată să aibă suma suma_dorita. Funcția utilizează o abordare recursivă și verifică toate posibilitățile de împărțire, începând de la indexul index. Dacă secvența poate fi împărțită cu succes, se returnează True, altfel se returnează False.

Funcția rezolvare(n, secventa) primește aceiași doi parametri ca și funcția validare_input(n, secventa). Această funcție calculează suma totală a elementelor din secvență prin apelarea funcției validare_input(n, secventa) și apoi parcurge toate posibilitățile de împărțire a secvenței în bucăți egale. Dacă găsește o împărțire validă, returnează numărul de prieteni implicați în împărțire. Dacă nu există o împărțire validă, se returne

3718 - Tort2 - Revision history

Sovago Rares-Andrei: /* Date de intrare */

Sovago Rares-Andrei: /* Date de intrare */

Sovago Rares-Andrei: /* Rezolvare */

Nagy Lenard at 20:08, 7 April 2023