https://wiki.universitas.ro/index.php?action=history&feed=atom&title=2683_-_Easy_ssc 2026-05-01T04:39:27Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=2683_-_Easy_ssc&diff=8957&oldid=prev 2024-01-04T10:07:09Z

<p>Pagină nouă: Se dă un șir de &#039;&#039;&#039;n&#039;&#039;&#039; numere naturale. Șirul poate fi partiționat în mai multe moduri într-un număr de subșiruri strict crescătoare. De exemplu, șirul &#039;&#039;&#039;4 6 2 5 8 1 3 7&#039;&#039;&#039; poate fi partiționat astfel: &#039;&#039;&#039;4 6 8&#039;&#039;&#039; (primul subșir), &#039;&#039;&#039;2 5 7&#039;&#039;&#039; (al doilea) și &#039;&#039;&#039;1 3&#039;&#039;&#039; (al treilea). O altă modalitate este formând patru subșiruri: &#039;&#039;&#039;4 5 7&#039;&#039;&#039;, &#039;&#039;&#039;6 8&#039;&#039;&#039;, &#039;&#039;&#039;2 3&#039;&#039;&#039; și &#039;&#039;&#039;1&#039;&#039;&#039;. == Cerinţa == Să se determine numărul minim de subșiruri strict crescătoare în...</p> <p><b>New page</b></p><div>Se dă un șir de &#039;&#039;&#039;n&#039;&#039;&#039; numere naturale. Șirul poate fi partiționat în mai multe moduri într-un număr de subșiruri strict crescătoare. De exemplu, șirul &#039;&#039;&#039;4 6 2 5 8 1 3 7&#039;&#039;&#039; poate fi partiționat astfel: &#039;&#039;&#039;4 6 8&#039;&#039;&#039; (primul subșir), &#039;&#039;&#039;2 5 7&#039;&#039;&#039; (al doilea) și &#039;&#039;&#039;1 3&#039;&#039;&#039; (al treilea). O altă modalitate este formând patru subșiruri: &#039;&#039;&#039;4 5 7&#039;&#039;&#039;, &#039;&#039;&#039;6 8&#039;&#039;&#039;, &#039;&#039;&#039;2 3&#039;&#039;&#039; și &#039;&#039;&#039;1&#039;&#039;&#039;.<br /> == Cerinţa ==<br /> Să se determine numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.<br /> == Date de intrare ==<br /> Programul citește de la tastatură numărul &#039;&#039;&#039;n&#039;&#039;&#039;, iar apoi șirul de &#039;&#039;&#039;n&#039;&#039;&#039; numere naturale, separate prin spații.<br /> == Date de ieșire ==<br /> Programul va afișa pe ecran numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.<br /> == Restricţii şi precizări ==<br /> * &#039;&#039;&#039;1 &amp;les; n &amp;les; 1000&#039;&#039;&#039;<br /> * cele &#039;&#039;&#039;n&#039;&#039;&#039; numere citite vor fi mai mici decât &#039;&#039;&#039;50.000&#039;&#039;&#039;<br /> * Un subșir se obține dintr-un șir prin eliminarea a zero, unul, sau mai multe elemente.<br /> == Exemplu 1 ==<br /> ; Intrare<br /> 8<br /> 4 6 2 5 8 1 3 7<br /> ; Iesire<br /> Datele de intrare corespund restrictiilor impuse<br /> 3<br /> &lt;br&gt;<br /> == Exemplu 2 ==<br /> ; Intrare<br /> 10001<br /> 4 6 2 5 8 1 3 7<br /> ; Iesire<br /> Datele de intrare nu corespund restrictiilor impuse<br /> &lt;br&gt;<br /> == Rezolvare ==<br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> from bisect import bisect_left<br /> <br /> <br /> def numar_minim_subsecvente(n, sir):<br /> # Calculează numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.<br /> <br /> subsecvente = [0] * n<br /> lungime = 1<br /> <br /> # Primul element al sirului este întotdeauna o subsecvență în sine<br /> subsecvente[0] = sir[0]<br /> <br /> for i in range(1, n):<br /> # Dacă elementul curent este mai mare decât ultimul element al subsecvenței curente,<br /> # îl adăugăm la sfârșitul subsecvenței și creștem lungimea acesteia<br /> if sir[i] &gt; subsecvente[lungime - 1]:<br /> subsecvente[lungime] = sir[i]<br /> lungime += 1<br /> else:<br /> # Dacă elementul curent este mai mic sau egal cu ultimul element al subsecvenței curente,<br /> # înlocuim cel mai mare element care este mai mic sau egal cu elementul curent<br /> j = bisect_left(subsecvente, sir[i], 0, lungime)<br /> subsecvente[j] = sir[i]<br /> <br /> return lungime<br /> <br /> <br /> def main():<br /> n = int(input().strip())<br /> sir = list(map(int, input().split()))<br /> <br /> # Verifică dacă datele de intrare respectă restricțiile<br /> if not (1 &lt;= n &lt;= 1000 and all(0 &lt;= x &lt; 50000 for x in sir)):<br /> print(&quot;Datele de intrare nu corespund restrictiilor impuse\n&quot;)<br /> return<br /> <br /> print(&quot;Datele de intrare corespund restrictiilor impuse\n&quot;)<br /> <br /> numar = numar_minim_subsecvente(n, sir)<br /> print(f&quot;{numar}\n&quot;)<br /> <br /> <br /> if __name__ == &quot;__main__&quot;:<br /> main()<br /> <br /> <br /> &lt;/syntaxhighlight&gt;</div>

Codrut Borcutean