https://wiki.universitas.ro/index.php?action=history&feed=atom&title=3623_-_insule01 2026-05-01T14:05:04Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=3623_-_insule01&diff=8810&oldid=prev 2024-01-02T21:51:16Z

<p>Pagină nouă: == Cerinţa == Se dă &#039;&#039;&#039;n&#039;&#039;&#039; un număr natural. Într-un şir de lungime &#039;&#039;&#039;n&#039;&#039;&#039;, format cu cifrele &#039;&#039;&#039;0&#039;&#039;&#039; şi &#039;&#039;&#039;1&#039;&#039;&#039;, numim &#039;&#039;&#039;insulă&#039;&#039;&#039; o secvenţă maximă de cifre egale. Să se afle câte &#039;&#039;&#039;insule&#039;&#039;&#039; se află în toate şirurile de lungime &#039;&#039;&#039;n&#039;&#039;&#039;, formate cu cifrele &#039;&#039;&#039;0&#039;&#039;&#039; şi &#039;&#039;&#039;1&#039;&#039;&#039;. == Date de intrare == Programul citește de la tastatură numărul &#039;&#039;&#039;n&#039;&#039;&#039;. == Date de ieșire == Programul va afișa pe ecran numărul &#039;&#039;&#039;insulelor&#039;&#039;&#039; care se află în toate şiru...</p> <p><b>New page</b></p><div>== Cerinţa ==<br /> Se dă &#039;&#039;&#039;n&#039;&#039;&#039; un număr natural. Într-un şir de lungime &#039;&#039;&#039;n&#039;&#039;&#039;, format cu cifrele &#039;&#039;&#039;0&#039;&#039;&#039; şi &#039;&#039;&#039;1&#039;&#039;&#039;, numim &#039;&#039;&#039;insulă&#039;&#039;&#039; o secvenţă maximă de cifre egale. Să se afle câte &#039;&#039;&#039;insule&#039;&#039;&#039; se află în toate şirurile de lungime &#039;&#039;&#039;n&#039;&#039;&#039;, formate cu cifrele &#039;&#039;&#039;0&#039;&#039;&#039; şi &#039;&#039;&#039;1&#039;&#039;&#039;.<br /> == Date de intrare ==<br /> Programul citește de la tastatură numărul &#039;&#039;&#039;n&#039;&#039;&#039;.<br /> == Date de ieșire ==<br /> Programul va afișa pe ecran numărul &#039;&#039;&#039;insulelor&#039;&#039;&#039; care se află în toate şirurile de lungime &#039;&#039;&#039;n&#039;&#039;&#039;, formate cu cifrele &#039;&#039;&#039;0&#039;&#039;&#039; şi &#039;&#039;&#039;1&#039;&#039;&#039;. Deoarece acest număr este prea mare, se va afişa modulo &#039;&#039;&#039;1.000.000.007&#039;&#039;&#039;.<br /> == Restricţii şi precizări ==<br /> * &#039;&#039;&#039;1 &amp;les; n &amp;les; 1.000.000.000&#039;&#039;&#039;<br /> <br /> == Exemplul 1 ==<br /> ; Intrare<br /> 2 <br /> ; Iesire<br /> Datele de intrare corespund restrictiilor impuse<br /> 6<br /> <br /> == Exemplu 2 ==<br /> ; Intrare<br /> 1000000001<br /> ; Iesire<br /> Datele de intrare nu corespund restrictiilor impuse<br /> <br /> <br /> <br /> == Rezolvare ==<br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> def compute_islands(n):<br /> mod = 1000000007<br /> dp = [0] * (n+1)<br /> dp[1] = 2<br /> dp[2] = 6<br /> for i in range(3, n+1):<br /> dp[i] = (dp[i-1] * 2 + dp[i-2] * 2) % mod<br /> return dp[n]<br /> <br /> <br /> def main():<br /> n = int(input())<br /> <br /> if n &gt; pow(10, 9):<br /> print(&quot;Datele de intrare nu corespund restrictiilor impuse&quot;)<br /> return<br /> <br /> islands = compute_islands(n)<br /> print(&quot;Datele de intrare corespund restrictiilor impuse&quot;)<br /> print(islands)<br /> <br /> <br /> if __name__ == &quot;__main__&quot;:<br /> main()<br /> &lt;/syntaxhighlight&gt;<br /> <br /> == Explicatie ==<br /> Şirurile de lungime &#039;&#039;&#039;2&#039;&#039;&#039; formate cu cifrele &#039;&#039;&#039;0&#039;&#039;&#039; şi &#039;&#039;&#039;1&#039;&#039;&#039; sunt &#039;&#039;&#039;00&#039;&#039;&#039;, &#039;&#039;&#039;01&#039;&#039;&#039;, &#039;&#039;&#039;10&#039;&#039;&#039;, &#039;&#039;&#039;11&#039;&#039;&#039;, acestea conţinând &#039;&#039;&#039;1&#039;&#039;&#039;, &#039;&#039;&#039;2&#039;&#039;&#039;, &#039;&#039;&#039;2&#039;&#039;&#039;, respectiv &#039;&#039;&#039;1&#039;&#039;&#039; insule. În total sunt &#039;&#039;&#039;6&#039;&#039;&#039; insule.</div>

Brianna Waltner