Editing 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 &les; n &les; 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 ==
<syntaxhighlight lang="python" line>
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()
</syntaxhighlight>

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