2018 - Rogvaiv: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: == Cerința == Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele n uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate? == Date de intrare == Fișierul de intrare rogvaivin.txt conține pe prima linie numărul n. =...) |
Fără descriere a modificării |
||
Linia 1: | Linia 1: | ||
= Cerința = | |||
Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele n uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate? | Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele <code>n</code> uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate? | ||
Fișierul de intrare | = Date de intrare = | ||
Fișierul de intrare <code>rogvaivIN.txt</code> conține pe prima linie numărul <code>n</code>. | |||
Fișierul de ieșire | |||
= Date de ieșire = | |||
*numărul n are cel mult 1.000.000 de cifre. | Fișierul de ieșire <code>rogvaivOUT.txt</code> va conține pe prima linie numărul de moduri în care Dorel poate vopsi gardul, modulo <code>1.000.000.007</code>. | ||
= Restricții și precizări = | |||
* numărul <code>n</code> are cel mult <code>1.000.000</code> de cifre. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse". | |||
= Exemplu: = | |||
== | <code>rogvaivIN.txt</code> | ||
3 | |||
<code>rogvaivOUT.txt</code> | |||
343 | |||
=== Explicație === | |||
Fiecare ulucă poate fi vopsită cu una din cele <code>7</code> culori, deci avem <code>7•7•7=343</code> moduri. | |||
<br> | <br> | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line="1"> | ||
def verifica_restrictii(a): | |||
if len(a) > 1000001: | |||
try: | return False | ||
if not a.isdigit(): | |||
return False | |||
except | return True | ||
def main(): | |||
try: | |||
with open("rogvaivIN.txt", "r") as f: | |||
a = f.read().strip() | |||
except FileNotFoundError: | |||
with open("rogvaivOUT.txt", "w") as g: | |||
g.write("Datele nu corespund restrictiilor impuse") | |||
return | |||
if not verifica_restrictii(a): | |||
with open("rogvaivOUT.txt", "w") as g: | |||
g.write("Datele nu corespund restrictiilor impuse") | |||
return | |||
n = len(a) | |||
s = 0 | |||
for i in range(n): | |||
s = (s * 10 + int(a[i])) % 1000000006 | |||
c = [0] * 50 | |||
i = 0 | |||
while s != 0: | |||
i += 1 | |||
c[i] = s % 2 | |||
s = s // 2 | |||
p = 1 | |||
for j in range(i, 0, -1): | |||
if c[j] == 1: | |||
p = ((p * p) * 7) % 1000000007 | |||
else: | |||
p = (p * p) % 1000000007 | |||
with open("rogvaivOUT.txt", "w") as g: | |||
with open(" | g.write(str(p)) | ||
if __name__ == "__main__": | |||
main() | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Versiunea curentă din 18 mai 2024 13:04
Cerința
Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele n
uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate?
Date de intrare
Fișierul de intrare rogvaivIN.txt
conține pe prima linie numărul n
.
Date de ieșire
Fișierul de ieșire rogvaivOUT.txt
va conține pe prima linie numărul de moduri în care Dorel poate vopsi gardul, modulo 1.000.000.007
.
Restricții și precizări
- numărul
n
are cel mult1.000.000
de cifre. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Exemplu:
rogvaivIN.txt
3
rogvaivOUT.txt
343
Explicație
Fiecare ulucă poate fi vopsită cu una din cele 7
culori, deci avem 7•7•7=343
moduri.
Rezolvare
def verifica_restrictii(a):
if len(a) > 1000001:
return False
if not a.isdigit():
return False
return True
def main():
try:
with open("rogvaivIN.txt", "r") as f:
a = f.read().strip()
except FileNotFoundError:
with open("rogvaivOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return
if not verifica_restrictii(a):
with open("rogvaivOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return
n = len(a)
s = 0
for i in range(n):
s = (s * 10 + int(a[i])) % 1000000006
c = [0] * 50
i = 0
while s != 0:
i += 1
c[i] = s % 2
s = s // 2
p = 1
for j in range(i, 0, -1):
if c[j] == 1:
p = ((p * p) * 7) % 1000000007
else:
p = (p * p) % 1000000007
with open("rogvaivOUT.txt", "w") as g:
g.write(str(p))
if __name__ == "__main__":
main()