Vizualizare sursă pentru „1265 - giovanacci”

== 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:
        with open("giovanacciout.txt", "w") as output_file:
            output_file.write("Nu au fost respectate cerintele impuse\n")
if __name__ == "__main__":
    main()

</syntaxhighlight>