Latest revision as of 13:04, 18 May 2024

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

rogvaivOUT.txt

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>

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