VanceaGabriel at 22:28, 12 January 2024

2024-01-12T22:28:09Z

← Older revision		Revision as of 22:28, 12 January 2024
Line 11:		Line 11:
	= Cerința =		= Cerința =
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3">
	~~MOD~~ = 666013 #~~definim constanta~~ pentru operatia modulo		Constanta_mod = 666013
			# Constanta pentru operatia modulo

	~~fin~~ = ~~open("veverita4.in", "r") #deschidem fisierele input si output~~		numar_n = 0
	~~fout = open("veverita4.out", "w")~~

	~~n = int(fin.readline()) #citim valoarea lui "n" din fisierul input~~

	#~~definim~~ functie pentru inmultirea matricei		# Definim functie pentru inmultirea matricei
	def ~~mat_multiply~~(a, b)		def inmultire_matrice(numar_a, numar_b):
	~~ans~~ = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]		raspuns = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
	for i in range(4):		for i in range(4):
	for j in range(4):		for j in range(4):
	for k in range(4):		for k in range(4):
	~~ans~~[i][j] += a[i][k] * b[k][j]		raspuns[i][j] += numar_a[i][k] * numar_b[k][j]
	if n > 1000:#~~aplicam~~ operatia modulo daca n>1000		if numar_n > 1000:
	~~ans~~[i][j] %= ~~MOD~~		# Aplicam operatia modulo daca n > 1000
	return ~~ans # ridicam matricea la puterea n-1~~		raspuns[i][j] %= Constanta_mod
			return raspuns

	#~~definim~~ matricea initiala "~~mat~~"
	~~mat~~ = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]		def main():
	#~~initializam~~ rezultatul ~~matricel~~ "~~ansmat~~" ca matrice de identitate		# Deschidem fisierele input si output
	~~ansmat~~ = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]		fin = open("veverita4.in", "r")
	#~~efectuam~~ exponentierea matricei folosind metoda exponentierei binare		fout = open("veverita4.out", "w")
	~~exp~~ = n - 1
	while ~~exp~~:		# Citim valoarea numarului "n" din fisierul input
	if ~~exp~~ % 2 == 1:		numar_n = int(fin.readline())
	~~ansmat~~ = ~~mat_multiply~~(~~ansmat~~, ~~mat~~)
	~~mat~~ = ~~mat_multiply~~(~~mat~~, ~~mat~~)		# Definim matricea initiala "matrice"
	~~exp~~ = int(~~exp~~ / 2)		matrice = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]
	#~~calculam~~ rezultatul final apeland elementele din "~~ansmat~~"
	~~ans~~ = 0		# Initializam rezultatul matricei "matrice_rezultata" ca matrice de identitate
	for i in range(4):		matrice_rezultata = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
	for j in range(4):
	~~ans~~ += ~~ansmat~~[i][j]		# Efectuam exponentierea matricei folosind metoda exponentierei binare
	#~~aplicam~~ operatia modulo daca n>1000		exponent = numar_n - 1
	if n > 1000:		while exponent:
	~~ans~~ %= ~~MOD~~		if exponent % 2 == 1:
	#~~scriem~~ rezultatul final in fisierul output si inchidem ~~fisierul~~		# Inmultim matricea_rezultata cu matricea
	fout.write(str(~~ans~~))		matrice_rezultata = inmultire_matrice(matrice_rezultata, matrice)
	fin.close()		# Ridicam matricea la puterea 2
	fout.close()		matrice = inmultire_matrice(matrice, matrice)
			exponent = int(exponent / 2)

			# Calculam rezultatul final apeland elementele din "matrice_rezultata"
			raspuns = 0
			for i in range(4):
			for j in range(4):
			raspuns += matrice_rezultata[i][j]

			# Aplicam operatia modulo daca n > 1000
			if numar_n > 1000:
			raspuns %= Constanta_mod

			# Scriem rezultatul final in fisierul output si inchidem fisierele
			fout.write(str(raspuns))

			fin.close()
			fout.close()

			# Verificam daca scriptul este rulat direct


			if __name__ == "__main__":
			# Apelam functia main()
			main()
	</syntaxhighlight>Aflați numărul <code>M</code> de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă <code>n</code> este mai mic sau egal cu <code>1000</code>, atunci veți afișa chiar numărul <code>M</code>, iar dacă <code>n</code> este mai mare decât <code>1000</code>, veți afișa restul împărțirii lui <code>M</code> la <code>666013</code>.		</syntaxhighlight>Aflați numărul <code>M</code> de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă <code>n</code> este mai mic sau egal cu <code>1000</code>, atunci veți afișa chiar numărul <code>M</code>, iar dacă <code>n</code> este mai mare decât <code>1000</code>, veți afișa restul împărțirii lui <code>M</code> la <code>666013</code>.

VanceaGabriel: Pagină nouă: În parcul orașului există `4` rânduri de câte `n` copaci perfect aliniați. Rândurile sunt notate A, B, C și D, iar copacii de pe fiecare rând sunt numerotați de la `1` la `n`, ca în imaginea de mai jos: O veveriță jucăușă sare prin copaci astfel: * pornește dintr-un copac numerotat cu `1`; * la fiecare pas sare dintr-un copac numerotat cu `i` într-un copac numerotat cu `i+1`. Da...

2024-01-11T22:59:41Z

Pagină nouă: În parcul orașului există <code>4</code> rânduri de câte <code>n</code> copaci perfect aliniați. Rândurile sunt notate A, B, C și D, iar copacii de pe fiecare rând sunt numerotați de la <code>1</code> la <code>n</code>, ca în imaginea de mai jos: O veveriță jucăușă sare prin copaci astfel: * pornește dintr-un copac numerotat cu <code>1</code>; * la fiecare pas sare dintr-un copac numerotat cu <code>i</code> într-un copac numerotat cu <code>i+1</code>. Da...

New page

În parcul orașului există <code>4</code> rânduri de câte <code>n</code> copaci perfect aliniați. Rândurile sunt notate A, B, C și D, iar copacii de pe fiecare rând sunt numerotați de la <code>1</code> la <code>n</code>, ca în imaginea de mai jos:

O veveriță jucăușă sare prin copaci astfel:

* pornește dintr-un copac numerotat cu <code>1</code>;
* la fiecare pas sare dintr-un copac numerotat cu <code>i</code> într-un copac numerotat cu <code>i+1</code>. Dacă se află într-un copac de pe rândul A, va sări în copacul de pe rândul B, dacă se află într-un copac de pe rândul D, va sări în copacul de pe rândul C, dacă se află în copacul de pe rândul B, va sări în copacul de pe rândul A sau în copacul de pe rândul C, iar dacă se află în copacul de pe rândul C, va sări în copacul de pe rândul B sau în copacul de pe rândul D;
* se oprește într-unul dintre copacii numerotați cu <code>n</code>.

= Cerința =
<syntaxhighlight lang="python3">
MOD = 666013 #definim constanta pentru operatia modulo

fin = open("veverita4.in", "r") #deschidem fisierele input si output
fout = open("veverita4.out", "w")

n = int(fin.readline()) #citim valoarea lui "n" din fisierul input

#definim functie pentru inmultirea matricei
def mat_multiply(a, b)
ans = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
for i in range(4):
for j in range(4):
for k in range(4):
ans[i][j] += a[i][k] * b[k][j]
if n > 1000:#aplicam operatia modulo daca n>1000
ans[i][j] %= MOD
return ans # ridicam matricea la puterea n-1

#definim matricea initiala "mat"
mat = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]
#initializam rezultatul matricel "ansmat" ca matrice de identitate
ansmat = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
#efectuam exponentierea matricei folosind metoda exponentierei binare
exp = n - 1
while exp:
if exp % 2 == 1:
ansmat = mat_multiply(ansmat, mat)
mat = mat_multiply(mat, mat)
exp = int(exp / 2)
#calculam rezultatul final apeland elementele din "ansmat"
ans = 0
for i in range(4):
for j in range(4):
ans += ansmat[i][j]
#aplicam operatia modulo daca n>1000
if n > 1000:
ans %= MOD
#scriem rezultatul final in fisierul output si inchidem fisierul
fout.write(str(ans))
fin.close()
fout.close()
</syntaxhighlight>Aflați numărul <code>M</code> de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă <code>n</code> este mai mic sau egal cu <code>1000</code>, atunci veți afișa chiar numărul <code>M</code>, iar dacă <code>n</code> este mai mare decât <code>1000</code>, veți afișa restul împărțirii lui <code>M</code> la <code>666013</code>.

= Date de intrare =
Fișierul de intrare <code>veverita4.in</code> conține pe prima linie numărul <code>n</code>.

= Date de ieșire =
Fișierul de ieșire <code>veverita4.out</code> va conține pe prima linie valoarea cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 109</code>
* pentru 60% din teste, <code>n ≤ 1000</code>;
* pentru alte 40% din teste, <code>n ≤ 109</code>;

= Exemplu =
<code>veverita4.in</code>
3
<code>veverita4.out</code>
10

4287 - Veverita 4 - Revision history

VanceaGabriel at 22:28, 12 January 2024