Rezolvare PBinfo #4124

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: \( \frac{(-1)^{a_i}b_i}{c_i} \)

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

Exemplu:

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, \( {q}_{1} = \frac{0}{1} \), \( {q}_{2} = \frac{4}{2} \), \( {q}_{3} = \frac{7}{7} \), \( {q}_{4} = -\frac{2}{3} \) și \( {q}_{5} = \frac{3}{2} \).

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.