3785 - AI: Diferență între versiuni
De la Universitas MediaWiki
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 1: | Linia 1: | ||
Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei E(n)=∑nk=1(2⋅(a2+b2)k2⋅cos(k⋅α)), | Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei E(n)=∑nk=1(2⋅(a2+b2)k2⋅cos(k⋅α)), | ||
unde α=arctg(ab) , iar n, a, b sunt numere naturale nenule. | unde α=arctg(ab) , iar n, a, b sunt numere naturale nenule. | ||
= Cerința = | |||
Să se afle valoarea expresiei , modulo <code>1.000.000.007</code>. | |||
= Date de intrare = | |||
Fișierul de intrare <code>alIN.txt</code> conține pe prima linie numerele <code>n, a, b</code>, separate prin spațiu. | |||
= Date de ieșire = | |||
Fișierul de ieșire <code>alOUT.txt</code> va conține pe prima linie valoarea expresiei , modulo <code>1.000.000.007</code>. | |||
= Restricții și precizări = | |||
* <code>1 ≤ n ≤ 1012</code> | |||
* <code>1 ≤ a , b ≤ 20</code> | |||
</ | = Exemplul 1: = | ||
<code>alIN.txt</code> | |||
3 5 12 | |||
<code>alOUT.txt</code> | |||
1918 | |||
== Explicatie == | == Explicatie == | ||
Dacă α=arctg(5/12), atunci sin(α)=5/13 şi cos(α)=12/13. | Dacă α=arctg(5/12), atunci sin(α)=5/13 şi cos(α)=12/13. | ||
Avem E(3)=2⋅13⋅cos(α)+2⋅13*2⋅cos(2α)+2⋅13*3⋅cos(3α)=2⋅13⋅12/13+2⋅13*2⋅(2⋅cos2(α)−1)+2⋅13*3⋅(4⋅cos*3(α)−3⋅cos(α))=24+238+1656=1918. | Avem E(3)=2⋅13⋅cos(α)+2⋅13*2⋅cos(2α)+2⋅13*3⋅cos(3α)=2⋅13⋅12/13+2⋅13*2⋅(2⋅cos2(α)−1)+2⋅13*3⋅(4⋅cos*3(α)−3⋅cos(α))=24+238+1656=1918. | ||
== Exemplul 2: == | |||
<code>alIN.txt</code> | |||
3 21 12 | |||
<code>alOUT.txt</code> | |||
Datele nu corespund restrictiilor impuse | |||
== Rezolvare == | |||
<syntaxhighlight lang="python" line="1"> | |||
MOD = 1000000007 | |||
def gcd(a, b): | |||
if b == 0: | |||
return (1, 0) | |||
else: | |||
x, y = gcd(b, a % b) | |||
return (y, x - y * (a // b)) | |||
def prod(x, y): | |||
ret = [[0, 0], [0, 0]] | |||
ret[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD | |||
ret[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD | |||
ret[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD | |||
ret[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD | |||
return ret | |||
def pwr(mat, n): | |||
nullMat = [[1, 0], [0, 1]] | |||
if n == 0: | |||
return nullMat | |||
if n % 2: | |||
return prod(mat, pwr(prod(mat, mat), n // 2)) | |||
return pwr(prod(mat, mat), n // 2) | |||
def verify_restrictions(n, a, b): | |||
if 1 <= n <= 1012 and 1 <= a <= 20 and 1 <= b <= 20: | |||
return True | |||
return False | |||
def main(): | |||
try: | |||
with open("alIN.txt", "r") as fin: | |||
line = fin.readline().strip() | |||
if not line: | |||
raise ValueError("File is empty or invalid format.") | |||
n, a, b = map(int, line.split()) | |||
if not verify_restrictions(n, a, b): | |||
with open("alOUT.txt", "w") as fout: | |||
fout.write("Datele nu corespund restrictiilor impuse") | |||
return | |||
if n == 1: | |||
E = ((a * a + b * b) * (2 * b - 2) - 2 * (b * b - a * a) + 2 * b) // (a * a + b * b - 2 * b + 1) | |||
with open("alOUT.txt", "w") as fout: | |||
fout.write(str(E)) | |||
return | |||
numi = (b - 1) ** 2 + a * a | |||
pat = a * a + b * b | |||
invm, ins = gcd(numi, MOD) | |||
initMat = [[2 * b, -pat], [1, 0]] | |||
Alt = [[2 * (b * b - a * a), 0], [2 * b, 0]] | |||
C = pwr(initMat, n - 1) | |||
sol = prod(C, Alt) | |||
En = -2 * pat + 2 * b | |||
E = (pat * sol[1][0] - sol[0][0] + En) % MOD | |||
E = (E * invm) % MOD | |||
if E < 0: | |||
E = (MOD + E) % MOD | |||
with open("alOUT.txt", "w") as fout: | |||
fout.write(str(E)) | |||
except Exception as e: | |||
with open("alOUT.txt", "w") as fout: | |||
fout.write(str(e)) | |||
if __name__ == "__main__": | |||
main() | |||
</syntaxhighlight> |
Versiunea de la data 18 mai 2024 17:01
Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei E(n)=∑nk=1(2⋅(a2+b2)k2⋅cos(k⋅α)), unde α=arctg(ab) , iar n, a, b sunt numere naturale nenule.
Cerința
Să se afle valoarea expresiei , modulo 1.000.000.007
.
Date de intrare
Fișierul de intrare alIN.txt
conține pe prima linie numerele n, a, b
, separate prin spațiu.
Date de ieșire
Fișierul de ieșire alOUT.txt
va conține pe prima linie valoarea expresiei , modulo 1.000.000.007
.
Restricții și precizări
1 ≤ n ≤ 1012
1 ≤ a , b ≤ 20
Exemplul 1:
alIN.txt
3 5 12
alOUT.txt
1918
Explicatie
Dacă α=arctg(5/12), atunci sin(α)=5/13 şi cos(α)=12/13. Avem E(3)=2⋅13⋅cos(α)+2⋅13*2⋅cos(2α)+2⋅13*3⋅cos(3α)=2⋅13⋅12/13+2⋅13*2⋅(2⋅cos2(α)−1)+2⋅13*3⋅(4⋅cos*3(α)−3⋅cos(α))=24+238+1656=1918.
Exemplul 2:
alIN.txt
3 21 12
alOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
MOD = 1000000007
def gcd(a, b):
if b == 0:
return (1, 0)
else:
x, y = gcd(b, a % b)
return (y, x - y * (a // b))
def prod(x, y):
ret = [[0, 0], [0, 0]]
ret[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD
ret[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD
ret[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD
ret[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD
return ret
def pwr(mat, n):
nullMat = [[1, 0], [0, 1]]
if n == 0:
return nullMat
if n % 2:
return prod(mat, pwr(prod(mat, mat), n // 2))
return pwr(prod(mat, mat), n // 2)
def verify_restrictions(n, a, b):
if 1 <= n <= 1012 and 1 <= a <= 20 and 1 <= b <= 20:
return True
return False
def main():
try:
with open("alIN.txt", "r") as fin:
line = fin.readline().strip()
if not line:
raise ValueError("File is empty or invalid format.")
n, a, b = map(int, line.split())
if not verify_restrictions(n, a, b):
with open("alOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return
if n == 1:
E = ((a * a + b * b) * (2 * b - 2) - 2 * (b * b - a * a) + 2 * b) // (a * a + b * b - 2 * b + 1)
with open("alOUT.txt", "w") as fout:
fout.write(str(E))
return
numi = (b - 1) ** 2 + a * a
pat = a * a + b * b
invm, ins = gcd(numi, MOD)
initMat = [[2 * b, -pat], [1, 0]]
Alt = [[2 * (b * b - a * a), 0], [2 * b, 0]]
C = pwr(initMat, n - 1)
sol = prod(C, Alt)
En = -2 * pat + 2 * b
E = (pat * sol[1][0] - sol[0][0] + En) % MOD
E = (E * invm) % MOD
if E < 0:
E = (MOD + E) % MOD
with open("alOUT.txt", "w") as fout:
fout.write(str(E))
except Exception as e:
with open("alOUT.txt", "w") as fout:
fout.write(str(e))
if __name__ == "__main__":
main()