1265 - giovanacci: Difference between revisions

From Bitnami MediaWiki
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ă.
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.

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>

  1. 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>