1265 - giovanacci: Difference between revisions
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... |
|||
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ă. | ||
. 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. |
Revision as of 08:02, 22 December 2023
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 ⩽ T ⩽ 1000
- 2 ⩽ p ⩽ 100000
- 1 ⩽ n ⩽ 1000
- 1 ⩽ posi ⩽ 100000000000000000
Exemplu 1
- giovanacciin.txt
- 2 2
- 3 6 9 12
- 2 5 10
- giovanacciout.txt
- 0
- 1
- Datele corespund
Exemplu 2
- giovanacciin.txt
- 0 0
- 0 0
- giovanacciout.txt
- Nu au fost respectate cerintele impuse
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>