Latest revision as of 13:04, 18 May 2024

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 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:

rogvaivIN.txt

rogvaivOUT.txt

Explicație

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

Rezolvare

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

@@ Line 1: / Line 1: @@
-== Cerința ==
+= 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?
-== Date de intrare ==
-Fișierul de intrare rogvaivin.txt conține pe prima linie numărul n.
+= Date de intrare =
-== Date de ieșire ==
+Fișierul de intrare <code>rogvaivIN.txt</code> conține pe prima linie numărul <code>n</code>.
-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 ==
+= 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>.
-== Exemplu 1 ==
-; rogvaivin.txt
+= Restricții și precizări =
-: 3
-; rogvaivout.txt
+* 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".
-: 343
-<br>
+= Exemplu: =
-== Exemplu 2 ==
+<code>rogvaivIN.txt</code>
-; rogvaivin.txt
-: 5
+<code>rogvaivOUT.txt</code>
-; rogvaivout.txt
-: 16807
+=== 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>
 == Rezolvare ==
-<syntaxhighlight lang="python" line>
+<syntaxhighlight lang="python" line="1">
-#2018 - Rogvaiv
+def verifica_restrictii(a):
-# Citirea datelor de intrare
+    if len(a) > 1000001:
-try:
+        return False
-    with open("rogvaivin.txt", "r") as f:
+    if not a.isdigit():
-        n = int(f.readline())
+        return False
-except Exception as e:
+    return True
-     print("Fals")
-     exit()
+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
-# Verificarea restricțiilor
+    c = [0] * 50
-if n <= 0 or n > 1000000:
+    i = 0
-    print("Fals")
+    while s != 0:
-    exit()
+        i += 1
+        c[i] = s % 2
+        s = s // 2
-# Calculul numărului de moduri
+    p = 1
-mod = 1000000007
+    for j in range(i, 0, -1):
-ways_to_paint = pow(7, n, mod)
+        if c[j] == 1:
+            p = ((p * p) * 7) % 1000000007
+        else:
+            p = (p * p) % 1000000007
-# Scrierea rezultatului în fișierul de ieșire
+    with open("rogvaivOUT.txt", "w") as g:
-with open("rogvaivout.txt", "w") as f_out:
+        g.write(str(p))
-    f_out.write(str(ways_to_paint))
+if __name__ == "__main__":
+    main()
 </syntaxhighlight>
-== Explicatie ==
-Fiecare ulucă poate fi vopsită cu una din cele 7 culori, deci avem 7•7•7=343 moduri.