2148 - ADN - Revision history

Ardelean Alexandru at 15:26, 6 May 2023

2023-05-06T15:26:37Z

← Older revision		Revision as of 15:26, 6 May 2023
Line 77:		Line 77:
	nr_perechi = 0		nr_perechi = 0

			# Inițializăm un dicționar cu cheile de la 1 la n și valorile 1
	for i in range(1, n + 1):		for i in range(1, n + 1):
	martieni_adn[i] = 1		martieni_adn[i] = 1

			# Folosim Ciurul lui Eratostene pentru a calcula factorizarea în numere prime a fiecărui număr de la 2 la n
	for i in range(2, n + 1):		for i in range(2, n + 1):
			# Dacă martieni_adn[i] == 1, atunci i este un număr prim
	if martieni_adn[i] == 1:		if martieni_adn[i] == 1:
			# Setăm factorizarea în numere prime a lui martieni_adn[i] să fie pasul i
	martieni_adn[i] = i		martieni_adn[i] = i
			# Folosind algoritmul Ciurului lui Eratostene, marcam toți multiplii lui i cu factorul prim i
	j = 2		j = 2
	while j * i <= n:		while j * i <= n:
	martieni_adn[i * j] = martieni_adn[i * j] * i		martieni_adn[i * j] = martieni_adn[i * j] * i
			# Incrementăm j pentru a considera următorul multiplu al lui i
	j += 1		j += 1

			# Calculăm numărul de perechi de marțieni cu ADN-e distincte
	for i in range(1, n + 1):		for i in range(1, n + 1):
	nr_perechi += int(n / martieni_adn[i])		nr_perechi += int(n / martieni_adn[i])

Ardelean Alexandru at 14:04, 29 April 2023

2023-04-29T14:04:59Z

← Older revision		Revision as of 14:04, 29 April 2023
Line 31:		Line 31:
	:6		:6
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:16		:16

Line 42:		Line 43:
	:19		:19
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:88		:88

Line 48:		Line 50:
	:38		:38
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:251		:251

Line 54:		Line 57:
	:99		:99
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:961		:961

Ardelean Alexandru: /* Rezolvare */

2023-04-29T13:43:23Z

Rezolvare

← Older revision		Revision as of 13:43, 29 April 2023
Line 69:		Line 69:


	def ~~nr_perechi_adn~~(n):		def ADN(n):
	martieni_adn = {}		martieni_adn = {}
	nr_perechi = 0		nr_perechi = 0
Line 85:		Line 85:
	nr_perechi += int(n / martieni_adn[i])		nr_perechi += int(n / martieni_adn[i])

	~~return~~ nr_perechi		print(nr_perechi)


	~~def main()~~:		if __name__ == "__main__":
	n = int(input())		n = int(input())

	if not conditii(n):		if not conditii(n):
	~~return~~ print("Datele de intrare nu corespund restricțiilor impuse.")		print("Datele de intrare nu corespund restricțiilor impuse.")
	print("Datele de intrare corespund restricțiilor impuse.")		else:
			print("Datele de intrare corespund restricțiilor impuse.")
	~~print(nr_perechi_adn~~(n))		ADN(n)


	~~if __name__ == "__main__":~~
	~~main(~~)

	</syntaxhighlight>		</syntaxhighlight>

Ardelean Alexandru at 11:05, 26 March 2023

2023-03-26T11:05:10Z

← Older revision		Revision as of 11:05, 26 March 2023
Line 60:		Line 60:
	:0		:0
	;Ieșire		;Ieșire
	:~~Date~~ de intrare ~~gresite!~~		:Datele de intrare nu corespund restricțiilor impuse.

	==Rezolvare==		==Rezolvare==

Ardelean Alexandru at 10:35, 26 March 2023

2023-03-26T10:35:27Z

← Older revision		Revision as of 10:35, 26 March 2023
Line 14:		Line 14:
	Fișierul de intrare <code>adn.in</code> conține pe prima linie numărul <code>N</code>, reprezentând numărul de marțieni.		Fișierul de intrare <code>adn.in</code> conține pe prima linie numărul <code>N</code>, reprezentând numărul de marțieni.
	==Date de ieșire==		==Date de ieșire==
	~~Fișierul~~ de ~~ieșire <code>adn~~.~~out</code>~~ va ~~conține pe prima linie~~ numărul de perechi determinat.		Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

			Pe următorul rând se va afișa numărul de perechi determinat.

			În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

	==Restricții și precizări==		==Restricții și precizări==
Line 88:		Line 92:

	if not conditii(n):		if not conditii(n):
	return print("~~Date~~ de intrare ~~gresite!~~")		return print("Datele de intrare nu corespund restricțiilor impuse.")
			print("Datele de intrare corespund restricțiilor impuse.")

	print(nr_perechi_adn(n))		print(nr_perechi_adn(n))

Ardelean Alexandru: /* Restricții și precizări */

2023-03-21T12:55:43Z

Restricții și precizări

← Older revision		Revision as of 12:55, 21 March 2023
Line 19:		Line 19:

	* <code>1 ≤ N ≤ 5 000 000</code>		* <code>1 ≤ N ≤ 5 000 000</code>
	* ~~<code>~~Pe planeta Marte orice marțian X îl moștenește pe X.</code>		* Pe planeta Marte orice marțian <code>X</code> îl moștenește pe <code>X.</code>
	* ~~<code>~~Orice marțian îl moștenește pe marțianul 1 deoarece ADN(1)={}, adică mulțimea vidă, care se consideră inclusă în orice mulțime nevidă.~~</code>~~		* Orice marțian îl moștenește pe marțianul <code>1</code> deoarece <code>ADN(1)={}</code>, adică mulțimea vidă, care se consideră inclusă în orice mulțime nevidă.
	* ~~<code>~~Se garantează că numărul de perechi determinat are cel mult nouă cifre.~~</code>~~		* Se garantează că numărul de perechi determinat are cel mult nouă cifre.

	==Exemplu 1==		==Exemplu 1==

Ardelean Alexandru: Pagină nouă: ==Cerința== Pe Marte s-au descoperit `N` marțieni, identificați de către oamenii de știință de pe Pământ prin numerele de la `1` la `N`. Cercetările au dovedit că ADN-ul oricărui marțian `X` este format din mulțimea factorilor primi din descompunerea lui `X`. De exemplu `ADN(6)={2,3}`. Se știe că marțianul cu numărul de ordine `Y` îl moștenește pe marțianul cu numărul de ordi...

2023-03-21T12:03:41Z

Pagină nouă: ==Cerința== Pe Marte s-au descoperit <code>N</code> marțieni, identificați de către oamenii de știință de pe Pământ prin numerele de la <code>1</code> la <code>N</code>. Cercetările au dovedit că ADN-ul oricărui marțian <code>X</code> este format din mulțimea factorilor primi din descompunerea lui <code>X</code>. De exemplu <code>ADN(6)={2,3}</code>. Se știe că marțianul cu numărul de ordine <code>Y</code> îl moștenește pe marțianul cu numărul de ordi...

New page

==Cerința==
Pe Marte s-au descoperit <code>N</code> marțieni, identificați de către oamenii de știință de pe Pământ prin numerele de la <code>1</code> la <code>N</code>. Cercetările au dovedit că ADN-ul oricărui marțian <code>X</code> este format din mulțimea factorilor primi din descompunerea lui <code>X</code>. De exemplu <code>ADN(6)={2,3}</code>.

Se știe că marțianul cu numărul de ordine <code>Y</code> îl moștenește pe marțianul cu numărul de ordine <code>X</code> dacă <code>ADN(X)</code> este inclus în <code>ADN(Y)</code>, adică mulțimea factorilor primi ai lui <code>X</code> este inclusă în mulțimea factorilor primi ai lui <code>Y</code>.

De exemplu, marțianul <code>6</code> îl moștenește pe marțianul <code>3</code> deoarece <code>ADN(3)={3}</code> este inclus în <code>ADN(6)={2,3}</code>.

Trebuie să specificăm că se pot întâlni situații extreme în care <code>X</code> îl moștenește pe <code>Y</code> dar și <code>Y</code> îl moștenește pe <code>X</code>, atunci când cei doi marțieni au ADN-urile egale. Este situația marțianului <code>12</code> care îl moștenește pe <code>6</code> dar și <code>6</code> îl moștenește pe <code>12</code>.

Realizați un program care, considerând mulțimea celor <code>N</code> marțieni, determină numărul de perechi de marțieni <code>(Y, X)</code> pentru care <code>Y</code> îl moștenește pe <code>X</code>, unde <code>1 ≤ X ≤ N</code> și <code>1 ≤ Y ≤ N</code>.

==Date de intrare==
Fișierul de intrare <code>adn.in</code> conține pe prima linie numărul <code>N</code>, reprezentând numărul de marțieni.
==Date de ieșire==
Fișierul de ieșire <code>adn.out</code> va conține pe prima linie numărul de perechi determinat.

==Restricții și precizări==

* <code>1 ≤ N ≤ 5 000 000</code>
* <code>Pe planeta Marte orice marțian X îl moștenește pe X.</code>
* <code>Orice marțian îl moștenește pe marțianul 1 deoarece ADN(1)={}, adică mulțimea vidă, care se consideră inclusă în orice mulțime nevidă.</code>
* <code>Se garantează că numărul de perechi determinat are cel mult nouă cifre.</code>

==Exemplu 1==
;Intrare
:6
;Ieșire
:16

===Explicație===
<code>ADN(1)={}</code>, <code>ADN(2)={2}</code>, <code>ADN(3)={3}</code>, <code>ADN(4)={2}</code>, <code>ADN(5)={5}</code>, <code>ADN(6)={2,3}</code>.

Perechile de marțieni determinate sunt <code>(1,1)</code>; <code>(2,2)</code>; <code>(3,3)</code>; <code>(4,4)</code>; <code>(5,5)</code>; <code>(6,6)</code>; <code>(4,2)</code>; <code>(2,4)</code>; <code>(6,2)</code>; <code>(6,3)</code>; <code>(6,4)</code>; <code>(2,1)</code> ; <code>(3,1)</code>; <code>(4,1)</code>; <code>(5,1)</code>; <code>(6,1)</code>.

==Exemplu 2==
;Intrare
:19
;Ieșire
:88

==Exemplu 3==
;Intrare
:38
;Ieșire
:251

== Exemplu 4 ==
;Intrare
:99
;Ieșire
:961

== Exemplu 5 ==
;Intrare
:0
;Ieșire
:Date de intrare gresite!

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2148 ADN
def conditii(n):
return 1 <= n <= 5_000_000

def nr_perechi_adn(n):
martieni_adn = {}
nr_perechi = 0

for i in range(1, n + 1):
martieni_adn[i] = 1
for i in range(2, n + 1):
if martieni_adn[i] == 1:
martieni_adn[i] = i
j = 2
while j * i <= n:
martieni_adn[i * j] = martieni_adn[i * j] * i
j += 1
for i in range(1, n + 1):
nr_perechi += int(n / martieni_adn[i])

return nr_perechi

def main():
n = int(input())

if not conditii(n):
return print("Date de intrare gresite!")

print(nr_perechi_adn(n))

if __name__ == "__main__":
main()

</syntaxhighlight>