2018 - Rogvaiv

From Bitnami MediaWiki

Cerința[edit | edit source]

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[edit | edit source]

Fișierul de intrare rogvaivIN.txt conține pe prima linie numărul n.

Date de ieșire[edit | edit source]

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[edit | edit source]

  • numărul n are cel mult 1.000.000 de cifre. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Exemplu:[edit | edit source]

rogvaivIN.txt

3

rogvaivOUT.txt

343

Explicație[edit | edit source]

Fiecare ulucă poate fi vopsită cu una din cele 7 culori, deci avem 7•7•7=343 moduri.


Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line="1"> 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()

</syntaxhighlight>