3623 - insule01

Cerinţa

Se dă n un număr natural. Într-un şir de lungime n, format cu cifrele 0 şi 1, numim insulă o secvenţă maximă de cifre egale. Să se afle câte insule se află în toate şirurile de lungime n, formate cu cifrele 0 şi 1.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul insulelor care se află în toate şirurile de lungime n, formate cu cifrele 0 şi 1. Deoarece acest număr este prea mare, se va afişa modulo 1.000.000.007.

Restricţii şi precizări

• 1 ⩽ n ⩽ 1.000.000.000

Exemplul 1

Intrare

2 

Iesire

Datele de intrare corespund restrictiilor impuse
6

Exemplu 2

Intrare

1000000001

Iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

def compute_islands(n):
    mod = 1000000007
    dp = [0] * (n+1)
    dp[1] = 2
    dp[2] = 6
    for i in range(3, n+1):
        dp[i] = (dp[i-1] * 2 + dp[i-2] * 2) % mod
    return dp[n]


def main():
    n = int(input())

    if n > pow(10, 9):
        print("Datele de intrare nu corespund restrictiilor impuse")
        return

    islands = compute_islands(n)
    print("Datele de intrare corespund restrictiilor impuse")
    print(islands)


if __name__ == "__main__":
    main()

Explicatie

Şirurile de lungime 2 formate cu cifrele 0 şi 1 sunt 00, 01, 10, 11, acestea conţinând 1, 2, 2, respectiv 1 insule. În total sunt 6 insule.