4299 - Gravitatie - Revision history

AntalKrisztian at 13:54, 26 November 2023

2023-11-26T13:54:01Z

← Older revision		Revision as of 13:54, 26 November 2023
Line 4:		Line 4:
	Pentru a minimiza gradul de durere, Gigel poate interschimba (de câte ori vrea el) oricare două turnuleţe între ele. (ex: schimbă turnuleţul '''1''' cu turnuleţul '''3''', apoi turnuleţul '''4''' cu turnuleţul '''2''', etc…).		Pentru a minimiza gradul de durere, Gigel poate interschimba (de câte ori vrea el) oricare două turnuleţe între ele. (ex: schimbă turnuleţul '''1''' cu turnuleţul '''3''', apoi turnuleţul '''4''' cu turnuleţul '''2''', etc…).
	== Date de intrare ==		== Date de intrare ==
	În fișierul de intrare '''gravitatiein.txt''' se află pe prima linie, '''N''' numărul de turnuleţe. Pe a doua linie se găsesc '''N''' numere naturale, reprezentând înalţimea ~~<math>~~ Hi ~~</math>~~ a fiecărui turnuleţ, în ordinea în care acestea sunt aranjate inițial.		În fișierul de intrare '''gravitatiein.txt''' se află pe prima linie, '''N''' numărul de turnuleţe. Pe a doua linie se găsesc '''N''' numere naturale, reprezentând înalţimea Hi a fiecărui turnuleţ, în ordinea în care acestea sunt aranjate inițial.
	== Date de ieşire ==		== Date de ieşire ==
	În fisierul de iesire '''gravitatieout.txt''' se va scrie un singur numar, '''Nr''', reprezentând gradul minim de durere ce se poate obține prin rearanjarea turnulețelor folosind miscări valide.		În fisierul de iesire '''gravitatieout.txt''' se va scrie un singur numar, '''Nr''', reprezentând gradul minim de durere ce se poate obține prin rearanjarea turnulețelor folosind miscări valide.

AntalKrisztian at 13:52, 26 November 2023

2023-11-26T13:52:33Z

← Older revision		Revision as of 13:52, 26 November 2023
Line 4:		Line 4:
	Pentru a minimiza gradul de durere, Gigel poate interschimba (de câte ori vrea el) oricare două turnuleţe între ele. (ex: schimbă turnuleţul '''1''' cu turnuleţul '''3''', apoi turnuleţul '''4''' cu turnuleţul '''2''', etc…).		Pentru a minimiza gradul de durere, Gigel poate interschimba (de câte ori vrea el) oricare două turnuleţe între ele. (ex: schimbă turnuleţul '''1''' cu turnuleţul '''3''', apoi turnuleţul '''4''' cu turnuleţul '''2''', etc…).
	== Date de intrare ==		== Date de intrare ==
	În fișierul de intrare '''~~gravitatie~~.in''' se află pe prima linie, '''N''' numărul de turnuleţe. Pe a doua linie se găsesc '''N''' numere naturale, reprezentând înalţimea <math> Hi </math> a fiecărui turnuleţ, în ordinea în care acestea sunt aranjate inițial.		În fișierul de intrare '''gravitatiein.txt''' se află pe prima linie, '''N''' numărul de turnuleţe. Pe a doua linie se găsesc '''N''' numere naturale, reprezentând înalţimea <math> Hi </math> a fiecărui turnuleţ, în ordinea în care acestea sunt aranjate inițial.
	== Date de ieşire ==		== Date de ieşire ==
	În fisierul de iesire '''~~gravitatie~~.~~out~~''' se va scrie un singur numar, '''Nr''', reprezentând gradul minim de durere ce se poate obține prin rearanjarea turnulețelor folosind miscări valide.		În fisierul de iesire '''gravitatieout.txt''' se va scrie un singur numar, '''Nr''', reprezentând gradul minim de durere ce se poate obține prin rearanjarea turnulețelor folosind miscări valide.
	== Restricții și precizări ==		== Restricții și precizări ==
	* 1 &les; n &les; 100.000		* 1 &les; n &les; 100.000
Line 13:		Line 13:
	* Pentru '''40%''' din punctaj 0 &les; Hi &les; 100.000		* Pentru '''40%''' din punctaj 0 &les; Hi &les; 100.000
	== Exemplul 1 ==		== Exemplul 1 ==
	; ~~gravitatie~~.in		; gravitatiein.txt
	: 3		3
	: 7 3 3		7 3 3
	; ~~gravitatie~~.~~out~~		; gravitatieout.txt
	: 2		Datele de intrare corespund restrictiilor impuse
			2
			<br>
	== Explicație ==		== Explicație ==
	Gradul minim de durere se poate obține folosind configuratia inițială. Daca de exemplu am schimba primul turnuleț cu al doilea, atunci gradul de durere ar fi 3, placa rupându-se în 3 bucăți diferite.		Gradul minim de durere se poate obține folosind configuratia inițială. Daca de exemplu am schimba primul turnuleț cu al doilea, atunci gradul de durere ar fi 3, placa rupându-se în 3 bucăți diferite.
	== Exemplul 2 ==		== Exemplul 2 ==
	; ~~gravitatie~~.in		; gravitatiein.txt
	: 4		4
	: 4 7 2 7		4 7 2 7
	; ~~gravitatie~~.~~out~~		; gravitatieout.txt
	: 3		Datele de intrare corespund restrictiilor impuse
			3
			<br>
	== Explicație ==		== Explicație ==
	Se observă că dacă inversăm ultimul turn cu penultimul se obține configurația: '''4 7 7 2''', configurație ce are gradul de durere '''3''', care este și gradul minim.		Se observă că dacă inversăm ultimul turn cu penultimul se obține configurația: '''4 7 7 2''', configurație ce are gradul de durere '''3''', care este și gradul minim.
			== Exemplul 3 ==
			; gravitatiein.txt
			jfhhdinjd
			; gravitatieout.txt
			Datele de intrare nu corespund restrictiilor impuse
			<br>
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	def durere_minima(N, H):		# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
			def validare(n_validare, h_validare):
			# Verificăm dacă n este în intervalul 1-10000
			if n_validare < 1 or n_validare > 10000:
			raise ValueError # Ridicăm o eroare dacă n nu este în intervalul 1-10000
			for h in h_validare: # Parcurgem lista de înălțimi
			# Verificăm dacă înălțimea este în intervalul 0-2^64-1
			if h < 0 or h > 2**64-1:
			raise ValueError
			file_out.write("Datele de intrare corespund restrictiilor impuse\n")


			# Funcția durere_minima calculează gradul minim de durere ce se poate obține prin rearanjarea turnulețelor
			def durere_minima(n_minim, h_minim):
	# Creăm o listă de perechi (înălțime, poziție inițială)		# Creăm o listă de perechi (înălțime, poziție inițială)
	turnuri = [(H[i], i) for i in range(N)]		turnuri = [(h_minim[i], i) for i in range(n_minim)]
	# Sortăm lista în funcție de înălțime		# Sortăm lista în funcție de înălțime
	turnuri.sort()		turnuri.sort()
	# Calculăm numărul de bucăți în care se rupe placa de plastic		# Calculăm numărul de bucăți în care se rupe placa de plastic
	~~durere~~ = 1		calculare = 1
	for i in range(1, N):		for i in range(1, n_minim):
	if turnuri[i-1][1] > turnuri[i][1] or turnuri[i-1][0] != turnuri[i][0]:		if turnuri[i-1][1] > turnuri[i][1] or turnuri[i-1][0] != turnuri[i][0]:
	~~durere~~ += 1		calculare += 1
	return ~~durere~~		return calculare


			if __name__ == '__main__':
			file_in = open("gravitatiein.txt", "r")
			file_out = open("gravitatieout.txt", "w")

	# Citim ~~datele~~ de ~~intrare din fișier~~		try:
	~~with open('gravitatie.in', 'r') as f:~~		# Citim numărul de turnulețe
	N = int(f.readline())		n_main = int(file_in.readline())
	H = list(map(int, f.readline().split()))		# Citim înălțimile turnulețelor
			H_main = list(map(int, file_in.readline().split()))
			# Validăm datele de intrare
			validare(n_main, H_main)
			# Calculăm durerea minimă
			durere = durere_minima(n_main, H_main)
			# Scriem durerea minimă în fișierul de ieșire
			file_out.write(str(durere) + '\n')

	# ~~Calculăm durerea minimă~~		# Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
	~~durere = durere_minima~~(N, H)		except ValueError:
			file_out.write("Datele de intrare nu corespund restrictiilor impuse")
			# Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
			except IndexError:
			file_out.write("Datele de intrare nu corespund restrictiilor impuse")

	~~# Scriem rezultatul în fișierul de ieșire~~
	~~with open('gravitatie.out', 'w') as f:~~
	~~f.write(str(durere))~~

	</syntaxhighlight>		</syntaxhighlight>

AntalKrisztian: Pagină nouă: == Cerinţa == Gigel era foarte plictisit așa că a început să se joace cu piese de lego. El a construit turnuleţe de diverse înalţimi pe care le-a aranjat unul lângă celalalt, în linie. Prietenul său, Gogu, intrând în cameră să vadă ce face, a călcat accidental pe turnuleţe, urlând de durere. Când şi-a dat seama Gigel că şi-a supărat prietenul acesta s-a hotărât să îşi rearanjeze turnurile în aşa fel încât gradul de durere, atunci când cineva...

2023-11-07T16:24:23Z

Pagină nouă: == Cerinţa == Gigel era foarte plictisit așa că a început să se joace cu piese de lego. El a construit turnuleţe de diverse înalţimi pe care le-a aranjat unul lângă celalalt, în linie. Prietenul său, Gogu, intrând în cameră să vadă ce face, a călcat accidental pe turnuleţe, urlând de durere. Când şi-a dat seama Gigel că şi-a supărat prietenul acesta s-a hotărât să îşi rearanjeze turnurile în aşa fel încât gradul de durere, atunci când cineva...

New page

== Cerinţa ==
Gigel era foarte plictisit așa că a început să se joace cu piese de lego. El a construit turnuleţe de diverse înalţimi pe care le-a aranjat unul lângă celalalt, în linie. Prietenul său, Gogu, intrând în cameră să vadă ce face, a călcat accidental pe turnuleţe, urlând de durere. Când şi-a dat seama Gigel că şi-a supărat prietenul acesta s-a hotărât să îşi rearanjeze turnurile în aşa fel încât gradul de durere, atunci când cineva va călca pe ele sa fie cat mai mic.
Ca să calculeze acest grad de durere, Gigel, băiat deştept, a aruncat o placă de plastic peste toate turnuleţele, placă ce s-a rupt în locurile în care două turnuri adiacente au inaltimi diferite. Acesta a stabilit ca gradul de durere să fie egal cu numărul părților în care s-a rupt placa iniţială.
Pentru a minimiza gradul de durere, Gigel poate interschimba (de câte ori vrea el) oricare două turnuleţe între ele. (ex: schimbă turnuleţul '''1''' cu turnuleţul '''3''', apoi turnuleţul '''4''' cu turnuleţul '''2''', etc…).
== Date de intrare ==
În fișierul de intrare '''gravitatie.in''' se află pe prima linie, '''N''' numărul de turnuleţe. Pe a doua linie se găsesc '''N''' numere naturale, reprezentând înalţimea <math> Hi </math> a fiecărui turnuleţ, în ordinea în care acestea sunt aranjate inițial.
== Date de ieşire ==
În fisierul de iesire '''gravitatie.out''' se va scrie un singur numar, '''Nr''', reprezentând gradul minim de durere ce se poate obține prin rearanjarea turnulețelor folosind miscări valide.
== Restricții și precizări ==
* 1 &les; n &les; 100.000
* 0 &les; Hi &les; 4.000.000.000 (patru miliarde)
* Bucata de plastic aruncată are lungimea egală cu lungimea șirului de turnulețe.
* Pentru '''40%''' din punctaj 0 &les; Hi &les; 100.000
== Exemplul 1 ==
; gravitatie.in
: 3
: 7 3 3
; gravitatie.out
: 2
== Explicație ==
Gradul minim de durere se poate obține folosind configuratia inițială. Daca de exemplu am schimba primul turnuleț cu al doilea, atunci gradul de durere ar fi 3, placa rupându-se în 3 bucăți diferite.
== Exemplul 2 ==
; gravitatie.in
: 4
: 4 7 2 7
; gravitatie.out
: 3
== Explicație ==
Se observă că dacă inversăm ultimul turn cu penultimul se obține configurația: '''4 7 7 2''', configurație ce are gradul de durere '''3''', care este și gradul minim.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def durere_minima(N, H):
# Creăm o listă de perechi (înălțime, poziție inițială)
turnuri = [(H[i], i) for i in range(N)]
# Sortăm lista în funcție de înălțime
turnuri.sort()
# Calculăm numărul de bucăți în care se rupe placa de plastic
durere = 1
for i in range(1, N):
if turnuri[i-1][1] > turnuri[i][1] or turnuri[i-1][0] != turnuri[i][0]:
durere += 1
return durere

# Citim datele de intrare din fișier
with open('gravitatie.in', 'r') as f:
N = int(f.readline())
H = list(map(int, f.readline().split()))

# Calculăm durerea minimă
durere = durere_minima(N, H)

# Scriem rezultatul în fișierul de ieșire
with open('gravitatie.out', 'w') as f:
f.write(str(durere))

</syntaxhighlight>