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

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