4245 - Suma ONI - Revision history

Dragos1234: /* Exemplul 2 */

2023-05-11T22:51:30Z

Exemplul 2

← Older revision		Revision as of 22:51, 11 May 2023
Line 30:		Line 30:
	: 15		: 15
	; Ieșire		; Ieșire
	: Datele ~~de intrare~~ corespund cerintelor.		: Datele introduse corespund cerintelor.
	: ''sumaoni.out''		: ''sumaoni.out''
	: 5		: 5

Dragos1234: /* Restricţii şi precizări */

2023-05-11T22:50:44Z

Restricţii şi precizări

← Older revision		Revision as of 22:50, 11 May 2023
Line 10:		Line 10:

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 &les; '''N''' &les; ~~50000~~		* 1 &les; '''S''' &les; 100.000
	* ~~0 &les; '''M''' &les; 10~~		* Dacă există mai multe soluţii se cere doar una.
	* 1 &les; '''numărul inițial de benzi al fiecărei piramide''' &les; 50

	== Exemplul 1 ==		== Exemplul 1 ==

Dragos1234: /* Rezolvare */

2023-04-14T17:09:50Z

Rezolvare

← Older revision		Revision as of 17:09, 14 April 2023
Line 39:		Line 39:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	#4245		#4245
	def ~~validate_input~~(s):		def verifica_date_intrare(s):
	if s < 1 or s > 100000:		if s < 1 or s > 100000:
	print("Datele introduse nu corespund cerintelor.")		print("Datele introduse nu corespund cerintelor.")
Line 45:		Line 45:


	def ~~binary_search_sum~~(s):		def cauta_suma_minimala(s):
	st = 1		start_interval = 1
	dr = 1000		final_interval = 1000
	n = 0		suma_minima_gasita = 0

	while st <= dr:		while start_interval <= final_interval:
	~~mid~~ = st + (dr - st) // 2		mijloc_interval = start_interval + (final_interval - start_interval) // 2
	sg = ~~mid~~ * (~~mid~~ + 1) // 2		suma = mijloc_interval * (mijloc_interval + 1) // 2
	if sg >= s:		if suma >= s:
	n = ~~mid~~		suma_minima_gasita = mijloc_interval
	dr = ~~mid~~ - 1		final_interval = mijloc_interval - 1
	else:		else:
	st = ~~mid~~ + 1		start_interval = mijloc_interval + 1

	~~diff~~ = n * (n + 1) // 2 - s		diferenta = suma_minima_gasita * (suma_minima_gasita + 1) // 2 - s
	while ~~diff~~ & 1:		while diferenta & 1:
	n += 1		suma_minima_gasita += 1
	~~diff~~ = n * (n + 1) // 2 - s		diferenta = suma_minima_gasita * (suma_minima_gasita + 1) // 2 - s

	return n, ~~diff~~		return suma_minima_gasita, diferenta


	def ~~print_result~~(n, ~~diff~~):		def afiseaza_rezultat(suma_minima_gasita, diferenta):
	~~fout~~ = open("sumaoni.out", "w")		fisier_iesire = open("sumaoni.out", "w")
	~~fout~~.write(str(n) + '\n')		fisier_iesire.write(str(suma_minima_gasita) + '\n')
	if ~~diff~~ == 0:		if diferenta == 0:
	~~fout~~.close()		fisier_iesire.close()
	return		return

	if ~~diff~~ // 2 <= n:		if diferenta // 2 <= suma_minima_gasita:
	~~fout~~.write(str(~~diff~~ // 2))		fisier_iesire.write(str(diferenta // 2))
	~~fout~~.close()		fisier_iesire.close()
	return		return

	~~diff~~ //= 2		diferenta //= 2
	for i in range(1, ~~diff~~ // 2 + 1):		for i in range(1, diferenta // 2 + 1):
	if ~~diff~~ - i <= n and ~~diff~~ - i != i:		if diferenta - i <= suma_minima_gasita and diferenta - i != i:
	~~fout~~.write(str(i) + '\n' + str(~~diff~~ - i))		fisier_iesire.write(str(i) + '\n' + str(diferenta - i))
	~~fout~~.close()		fisier_iesire.close()
	return		return

	~~fout~~.close()		fisier_iesire.close()


	if __name__ == '__main__':		if __name__ == '__main__':
	~~fin~~ = open("sumaoni.in", "r")		fisier_intrare = open("sumaoni.in", "r")
	s = int(~~fin~~.readline())		s = int(fisier_intrare.readline())
	~~fin~~.close()		fisier_intrare.close()

	~~validate_input~~(s)		verifica_date_intrare(s)

	n, ~~diff~~ = ~~binary_search_sum~~(s)		suma_minima_gasita, diferenta = cauta_suma_minimala(s)

	if n is not None and ~~diff~~ is not None:		if suma_minima_gasita is not None and diferenta is not None:
	print("Datele introduse corespund cerintelor.")		print("Datele introduse corespund cerintelor.")
	~~print_result~~(n, ~~diff~~)		afiseaza_rezultat(suma_minima_gasita, diferenta)

	</syntaxhighlight>		</syntaxhighlight>

Dragos1234: /* Rezolvare */

2023-04-14T11:28:08Z

Rezolvare

← Older revision		Revision as of 11:28, 14 April 2023
Line 38:		Line 38:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
			#4245
	def validate_input(s):		def validate_input(s):
	if s < 1 or s > 100000:		if s < 1 or s > 100000:
	print("Datele introduse nu corespund cerintelor.")		print("Datele introduse nu corespund cerintelor.")
	exit()		exit()


	def binary_search_sum(s):		def binary_search_sum(s):
Line 63:		Line 65:

	return n, diff		return n, diff


	def print_result(n, diff):		def print_result(n, diff):

Dragos1234: /* Exemplul 2 */

2023-04-14T11:27:08Z

Exemplul 2

← Older revision		Revision as of 11:27, 14 April 2023
Line 28:		Line 28:
	== Exemplul 2 ==		== Exemplul 2 ==
	; Intrare		; Intrare
	: ''~~tripar~~.in''		: ''sumaoni.in''
	: 2		: 15
	~~: 3 0~~
	~~: 1~~
	~~: 2~~
	~~: 3~~
	; Ieșire		; Ieșire
	: Datele de intrare corespund cerintelor.		: Datele de intrare corespund cerintelor.
	: ''~~tripar~~.out''		: ''sumaoni.out''
	: 0		: 5
	~~: 3~~
	~~: 9~~
	<br>		<br>

Dragos1234: /* Exemplul 1 */

2023-04-14T11:26:28Z

Exemplul 1

← Older revision		Revision as of 11:26, 14 April 2023
Line 19:		Line 19:
	: 12		: 12
	; Ieșire		; Ieșire
	: Datele ~~de intrare~~ corespund cerintelor..		: Datele introduse corespund cerintelor.
	: ''sumaoni.out''		: ''sumaoni.out''
	: 7		: 7

Dragos1234: /* Exemplul 1 */

2023-04-14T11:26:03Z

Exemplul 1

← Older revision		Revision as of 11:26, 14 April 2023
Line 16:		Line 16:
	== Exemplul 1 ==		== Exemplul 1 ==
	; Intrare		; Intrare
	: ''~~tripar~~.in''		: ''sumaoni.in''
	: 1		: 12
	~~: 3 0~~
	~~: 1~~
	~~: 2~~
	~~: 3~~
	; Ieșire		; Ieșire
	: Datele de intrare corespund cerintelor..		: Datele de intrare corespund cerintelor..
	: ''~~tripar~~.out''		: ''sumaoni.out''
			: 7
	: 1		: 1
	: 4		: 7
	~~: 9~~
	<br>		<br>

Dragos1234: /* Explicatie rezolvare */

2023-04-14T11:25:11Z

Explicatie rezolvare

← Older revision		Revision as of 11:25, 14 April 2023
Line 112:		Line 112:

	== Explicatie rezolvare ==		== Explicatie rezolvare ==
	Acest program ~~este o soluție pentru o problemă care primește intrare prin intermediul fișierelor~~ '''~~tripar~~.in~~''' și '''tripar.out~~'''.		Acest program are rolul de a găsi numărul minim de perechi de numere consecutive în șirul de numere naturale, astfel încât suma lor să fie egală cu numărul dat s din fișierul '''sumaoni.in'''.

	În fișierul '''~~tripar~~.in''', ~~prima linie conține un singur număr întreg p~~ (1 ~~sau 2~~), ~~care indică tipul~~ de ~~operație care trebuie efectuată. A doua linie conține două numere întregi separate prin spațiu,~~ n ~~și m, reprezentând numărul de benzi ale fiecărei piramide și numărul de niveluri de perechi drepte-paralele de cuburi~~ care ~~trebuie construite. Ultimele~~ n ~~linii conțin un singur număr întreg pe fiecare linie, reprezentând numărul de benzi al fiecărei piramide~~.		Programul primește numărul s din fișierul '''sumaoni.in''', validează dacă acesta respectă cerințele problemei (1 ≤ S ≤ 100.000) prin intermediul funcției '''validate_input(s)''', apoi utilizează o funcție de căutare binară pentru a găsi cel mai mic număr natural n pentru care suma primelor n numere naturale este mai mare sau egală cu s.

	~~Programul citește datele de intrare, apoi validează aceste date utilizând funcția '''validate_input'''.~~ Dacă ~~datele de intrare sunt valide~~, se ~~afișează un mesaj corespunzător, iar programul trece la calcularea și scrierea rezultatelor în fișierul '''tripar.out'''. Dacă datele~~ de ~~intrare nu sunt valide, se afișează~~ un ~~mesaj de eroare corespunzător și programul se oprește~~.		Dacă diferența dintre suma primelor n numere naturale și s este un număr impar, se adaugă o pereche suplimentară de numere consecutive astfel încât diferența să fie un număr par.

	~~Funcțiile '''nr_triunghiuri'''~~ și '''~~nr_perechi_dr_paralele~~''' ~~calculează numărul de triunghiuri sau perechi drepte-paralele de cuburi~~, în ~~funcție de cerința problemei și de~~ datele de intrare ~~primite. Rezultatele~~ sunt ~~scrise în fișierul tripar.out în ordinea datelor de intrare.~~		În final, programul afișează numărul minim de perechi de numere consecutive și perechile de numere (dacă există) în fișierul '''sumaoni.out'''. De asemenea, se afișează un mesaj în cazul în care datele de intrare sunt valide sau nu.

	~~La final, programul verifică dacă codul a fost rulat direct~~ sau ~~a fost importat într-un alt program prin intermediul liniei '''if __name__ == '__main__':'''~~.

Dragos1234: /* Date de ieșire */

2023-04-14T11:24:20Z

Date de ieșire

← Older revision		Revision as of 11:24, 14 April 2023
Line 7:		Line 7:

	== Date de ieșire ==		== Date de ieșire ==
	~~Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, fişierul~~ de ~~ieşire~~ '''~~tripar~~.out''' va conține ~~N linii;~~ pe ~~linia i se va scrie un număr natural reprezentând,~~ numărul ~~de triunghiuri de cea mai mică dimensiune pe~~ care ~~piramida i le conține după executarea procedeului de M ori~~, iar ~~în consolă se va afișa mesajul "Datele de intrare corespund cerintelor."~~		Fișierul de ieșire '''sumaoni.out''' va conține pe prima linie numărul minim N pentru care se poate obţine suma S, iar pe următoarele linii, până la sfârşitul fişierului, numerele care au semn negativ, câte unul pe linie, iar în consolă se va afișa mesajul "Datele introduse corespund cerințelor." În caz contrar programul va afișa in consolă mesajul "Datele introduse nu corespund cerințelor." Ordinea de afişare a numerelor nu are importanţă. Celelalte numere care nu apar în fişier se consideră pozitive.

	~~Dacă valoarea lui p este 2~~, ~~se va rezolva numai punctul b) din cerință. În acest caz~~, ~~fişierul de ieşire '''tripar.out''' va conține N linii; pe linia i se va scrie un număr natural reprezentând~~, ~~numărul de perechi de drepte paralele~~ pe ~~care piramida i le conține după executarea procedeului de M ori~~, ar în consolă se va afișa mesajul "Datele ~~de intrare~~ corespund ~~cerintelor~~."

	În ~~cazul in care cerintele de mai sus nu sunt indeplinite~~ programul va afișa în consolă mesajul "Datele introduse nu corespund cerințelor."

	== Restricţii şi precizări ==		== Restricţii şi precizări ==

Dragos1234: /* Date de intrare */

2023-04-14T11:22:30Z

Date de intrare

← Older revision		Revision as of 11:22, 14 April 2023
Line 4:		Line 4:

	== Date de intrare ==		== Date de intrare ==
	~~Fişierul~~ de intrare ~~'''tripar~~.in~~''' conţine~~ pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Următoarea linie va conține numerele N și M separate printr-un un spațiu. Pe următoarea linie se vor afla N numere naturale, al i-lea număr reprezintă numărul de benzi pe care, inițial, piramida i le are.		Fișierul de intrare sumaoni.in conține pe prima linie un întreg pozitiv S reprezentând suma ce trebuie obţinută.

	== Date de ieșire ==		== Date de ieșire ==