1265 - giovanacci - Revision history

Ramona Dragoș at 14:09, 6 January 2024

2024-01-06T14:09:29Z

← Older revision		Revision as of 14:09, 6 January 2024
Line 1:		Line 1:
	== Cerința ==		== Cerința ==
	Șirul Fibonacci este definit după regula:		Șirul Fibonacci este definit după regula:
	*F1=1		*'''F1=1'''
	*F2=1		*'''F2=1'''
	*Fn=Fn–1+Fn–2		*'''Fn=Fn–1+Fn–2'''
	Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale pos1,pos2,…,posn reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide Fpos1,Fpos2,…,Fposn. Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la numărul p. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură.		Comisia mafioților îl supune pe Giovanni la '''T''' teste. Pentru fiecare test se dau '''n''' și apoi '''n''' numere naturale '''pos1,pos2,…,posn''' reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr '''g''' care divide '''Fpos1,Fpos2,…,Fposn'''. Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui '''g''' la numărul '''p'''. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură.

	== Date de intrare ==		== Date de intrare ==
	Fișierul de intrare giovanacciin.txt conține pe prima linie numerele T și p, iar pe următoarele T linii n, urmat de n numere naturale.		Fișierul de intrare '''giovanacciin.txt''' conține pe prima linie numerele '''T''' și '''p''', iar pe următoarele '''T''' linii '''n''', urmat de '''n''' numere naturale.
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire giovanacciout.txt va conține cele T răspunsuri, câte unul pe linie.		Fișierul de ieșire '''giovanacciout.txt''' va conține cele '''T''' răspunsuri, câte unul pe linie.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 &les; T &les; 1000		*'''1 &les; T &les; 1000'''
	*2 &les; p &les; 100000		*'''2 &les; p &les; 100000'''
	*1 &les; n &les; 1000		*'''1 &les; n &les; 1000'''
	*1 &les; posi &les; 100000000000000000		*'''1 &les; posi &les; 100000000000000000'''

	== Exemplu 1 ==		== Exemplu 1 ==
	;giovanacciin.txt		;'''giovanacciin.txt'''
	:2 2		:2 2
	:3 6 9 12		:3 6 9 12
	:2 5 10		:2 5 10
	;giovanacciout.txt		;'''giovanacciout.txt'''
	:0		:0
	:1		:1
Line 27:		Line 27:
	<br>		<br>
	== Exemplu 2 ==		== Exemplu 2 ==
	;giovanacciin.txt		;'''giovanacciin.txt'''
	:0 0		:0 0
	:0 0		:0 0
	;giovanacciout.txt		;'''giovanacciout.txt'''
	: Nu au fost respectate cerintele impuse		: Nu au fost respectate cerintele impuse
	<br>		<br>
Line 74:		Line 74:
	output_file.write("Datele corespund\n")		output_file.write("Datele corespund\n")
	else:		else:
	~~print~~("Nu au fost respectate ~~cerințele~~ impuse.")		with open("giovanacciout.txt", "w") as output_file:
			output_file.write("Nu au fost respectate cerintele impuse\n")
	if __name__ == "__main__":		if __name__ == "__main__":
	main()		main()

	</syntaxhighlight>		</syntaxhighlight>

Ramona Dragoș: /* Cerința */

2023-12-22T08:02:16Z

Cerința

← Older revision		Revision as of 08:02, 22 December 2023
Line 4:		Line 4:
	*F2=1		*F2=1
	*Fn=Fn–1+Fn–2		*Fn=Fn–1+Fn–2
	Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale pos1,pos2,…,posn		Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale pos1,pos2,…,posn reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide Fpos1,Fpos2,…,Fposn. Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la numărul p. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură.
	reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide Fpos1,Fpos2,…,Fposn
	. Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la numărul p. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură.
	== Date de intrare ==		== Date de intrare ==
	Fișierul de intrare giovanacciin.txt conține pe prima linie numerele T și p, iar pe următoarele T linii n, urmat de n numere naturale.		Fișierul de intrare giovanacciin.txt conține pe prima linie numerele T și p, iar pe următoarele T linii n, urmat de n numere naturale.

Ramona Dragoș: Pagină nouă: == Cerința == Șirul Fibonacci este definit după regula: F1=1 F2=1 *Fn=Fn–1+Fn–2 Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale pos1,pos2,…,posn reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide Fpos1,Fpos2,…,Fposn . Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la număru...

2023-12-22T08:01:36Z

Pagină nouă: == Cerința == Șirul Fibonacci este definit după regula: *F1=1 *F2=1 *Fn=Fn–1+Fn–2 Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale pos1,pos2,…,posn reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide Fpos1,Fpos2,…,Fposn . Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la număru...

New page

== Cerința ==
Șirul Fibonacci este definit după regula:
*F1=1
*F2=1
*Fn=Fn–1+Fn–2
Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale pos1,pos2,…,posn
reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide Fpos1,Fpos2,…,Fposn
. Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la numărul p. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură.
== Date de intrare ==
Fișierul de intrare giovanacciin.txt conține pe prima linie numerele T și p, iar pe următoarele T linii n, urmat de n numere naturale.
== Date de ieșire ==
Fișierul de ieșire giovanacciout.txt va conține cele T răspunsuri, câte unul pe linie.
== Restricții și precizări ==
*1 &les; T &les; 1000
*2 &les; p &les; 100000
*1 &les; n &les; 1000
*1 &les; posi &les; 100000000000000000

== Exemplu 1 ==
;giovanacciin.txt
:2 2
:3 6 9 12
:2 5 10
;giovanacciout.txt
:0
:1
:Datele corespund
<br>
== Exemplu 2 ==
;giovanacciin.txt
:0 0
:0 0
;giovanacciout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1265 - Giovanacci
def fibonacci(n):
fib = [0, 1]
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
return fib

def find_largest_divisor_modulo_p(n, positions, p):
fib_sequence = fibonacci(max(positions))
largest_divisor = 0

for pos in positions:
if fib_sequence[pos] > largest_divisor:
largest_divisor = fib_sequence[pos]

return largest_divisor % p

def main():
try:
# Citirea datelor de intrare din fișier
with open("giovanacciin.txt", "r") as input_file:
T, p = map(int, input_file.readline().strip().split())
tests = [list(map(int, input_file.readline().strip().split()[1:])) for _ in range(T)]
except FileNotFoundError:
print("Fișierul giovanacciin.txt nu există.")
return
except ValueError:
print("Datele de intrare nu sunt valide.")
return

# Verificare dacă datele de intrare corespund cerințelor impuse
if 1 <= T <= 1000 and 2 <= p <= 100000 and all(1 <= len(test) <= 1000 and all(1 <= posi <= 100000000000000000 for posi in test) for test in tests):
# Calcularea rezultatelor și scrierea în fișierul de ieșire
with open("giovanacciout.txt", "w") as output_file:
for test in tests:
result = find_largest_divisor_modulo_p(test[0], test[1:], p)
output_file.write(str(result) + "\n")
output_file.write("Datele corespund\n")
else:
print("Nu au fost respectate cerințele impuse.")

if __name__ == "__main__":
main()

</syntaxhighlight>