2018 - Rogvaiv

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

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