https://wiki.universitas.ro/index.php?action=history&feed=atom&title=4124_-_Colibri 2026-05-02T01:48:30Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=4124_-_Colibri&diff=10045&oldid=prev 2024-06-03T17:31:11Z

<p>Pagină nouă: == Enunt == Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: (−1)aibici == Cerinţa == Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil. == Date de intrare == Fișierul de intrare colibri.in conține pe prima linie numărul N. Următoarele N linii descriu cele N triplete: pe linia i se află numerele naturale ai, bi, ci, sep...</p> <p><b>New page</b></p><div>== Enunt ==<br /> Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: (−1)aibici<br /> == Cerinţa ==<br /> Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil.<br /> == Date de intrare ==<br /> Fișierul de intrare colibri.in conține pe prima linie numărul N. Următoarele N linii descriu cele N triplete: pe linia i se află numerele naturale ai, bi, ci, separate prin spații.<br /> == Date de ieșire ==<br /> Pe prima linie a fișierului de ieșire colibri.out se află un șir de N cifre. Cifra i, unde 1 ≤ i ≤ N, este 1 dacă și numai dacă qi este selectat în subșirul soluție, altfel este 0. Cifrele șirului nu se vor separa prin spații.<br /> == Restricţii şi precizări ==<br /> * 1 ≤ N ≤ 50.000;<br /> * 0 ≤ ai, bi ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;<br /> * 1 ≤ ci ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;<br /> * Dacă există mai multe soluții, atunci se acceptă orice soluție corectă;<br /> * Spunem că un șir x este subșir al unui șir y dacă și numai dacă x se poate obține din y eliminând o parte din * elementele lui y (inclusiv nici unul) fără a schimba ordinea relativă a elementelor rămase.<br /> * Pentru 30 de puncte, N ≤ 19 și ai, ci, ci ≤ 9<br /> * Pentru 20 de puncte, N ≤ 19<br /> * Pentru 20 de puncte, ai, bi, ci ≤ 9<br /> * Pentru 30 de puncte, fără restricții suplimentare<br /> == Exemplul 1 ==<br /> ; colibri.in<br /> <br /> 5<br /> 0 0 1<br /> 2 4 2<br /> 4 7 7<br /> 1 2 3<br /> 0 3 2<br /> ; colibri.out<br /> <br /> 01001<br /> == Explicație ==<br /> În exemplu N=5, q1=01, q2=42, q3=77, q4=−23 și q5=32.<br /> <br /> Produsul maxim posibil este egal cu 3. Acesta se poate obține luând fie subșirul constând din numerele q2 și q5, fie luând subșirul format din numerele q2, q3 și q5. Cu alte cuvinte, și răspunsul 01101 este corect.<br /> &lt;br&gt;<br /> <br /> == Rezolvare ==<br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> def max_product_subarray(N, triples):<br /> max_product = float(&#039;-inf&#039;)<br /> max_index = -1<br /> <br /> for i in range(N):<br /> ai, bi, ci = triples[i]<br /> current_product = (-1) ** (ai * bi) * ci<br /> if current_product &gt; max_product:<br /> max_product = current_product<br /> max_index = i<br /> <br /> result = [&#039;0&#039;] * N<br /> result[max_index] = &#039;1&#039;<br /> return &#039;&#039;.join(result)<br /> <br /> def main():<br /> N = int(input())<br /> triples = [list(map(int, input().split())) for _ in range(N)]<br /> <br /> result = max_product_subarray(N, triples)<br /> print(result)<br /> <br /> if __name__ == &quot;__main__&quot;:<br /> main()<br /> <br /> &lt;/syntaxhighlight&gt;</div>

RebecaBud