Editing 4124 - Colibri

== 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, separate prin spații.
== Date de ieșire ==
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.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 50.000;
* 0 ≤ ai, bi ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;
* 1 ≤ ci ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;
* Dacă există mai multe soluții, atunci se acceptă orice soluție corectă;
* 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.
* Pentru 30 de puncte, N ≤ 19 și ai, ci, ci ≤ 9
* Pentru 20 de puncte, N ≤ 19
* Pentru 20 de puncte, ai, bi, ci ≤ 9
* Pentru 30 de puncte, fără restricții suplimentare
== Exemplul 1 ==
; colibri.in

  5
  0 0 1
  2 4 2
  4 7 7
  1 2 3
  0 3 2
; colibri.out

  01001
== Explicație ==
În exemplu N=5, q1=01, q2=42, q3=77, q4=−23 și q5=32.

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>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_product_subarray(N, triples):
    max_product = float('-inf')
    max_index = -1

    for i in range(N):
        ai, bi, ci = triples[i]
        current_product = (-1) ** (ai * bi) * ci
        if current_product > max_product:
            max_product = current_product
            max_index = i

    result = ['0'] * N
    result[max_index] = '1'
    return ''.join(result)

def main():
    N = int(input())
    triples = [list(map(int, input().split())) for _ in range(N)]

    result = max_product_subarray(N, triples)
    print(result)

if __name__ == "__main__":
    main()

</syntaxhighlight>