Počet bodov: 30, časový limit: 2000ms
Gregor mal dnes celkom zlý deň. Nielenže nepostúpil na krajské kolo Zenitu, ale ešte k tomu dnes na matematike zastupoval jeho najneobľúbenejší učiteľ. A veru aj dnes sa Gregorovi ušlo. Učiteľ napísal na tabuľu \(N\) čísel, a po dlhom dumavom pohľade na nich napokon s úškrnom zahlásil:
“Tak teda, deťúrence. Na domácu úlohu si dáme takéto neškodné cvičenie. Tu, hľa, som na tabuľu napísal veľa čísel a vy za úlohu musíte zistiť, ktoré čísla máme vynásobiť aby sme získali najväčší súčin. To by vás malo na dnes dobre zaneprázdniť.”
Ach. Kto by už len dokázal vymyslieť takú nudnú, zdĺhavú a nepraktickú domácu úlohu. Keby len bol niekto, kto by Gregorovi pomohol a vyriešil ju namiesto neho.
V prvom riadku je číslo \(N\): počet čísel. V druhom riadku je \(N\) čísel. Platí \(1 \leq N \leq 10^5\), žiadne z nich v absolútnej hodnote neprekročí \(10^9\).
Vyberte niektoré spomedzi týchto čísel tak, aby ich súčin bol čo najväčší. Odpoveď budeme reprezentovať pomocou reťazca dĺžky \(N\) pozostávajúceho z jednotiek a núl, kde nula bude označovať, že toľké číslo do súčinu neberieme a jednotka bude označovať, že ho berieme. Nakoniec si ešte popíšeme exaktné pravidlá, ako má tento reťazec vyzerať:
1
.1
, použijeme i-te číslo v našom súčine. Tento súčin musí byť maximálny možný.Navyše, v polovici vstupov je \(N \leq 20\) a maximálny súčin sa zmestí do 64-bitovej premennej so znamienkom.
Input:
6
-2 -2 -3 4 5 1
Output:
101110
Najviac sa nám oplatí zobrať čísla \(-2, -3, 4, 5\). Jednotku neberieme, aby sme neporušili tretí bod a spomedzi dvoch \(-2\) si vyberieme tú ľavšiu, aby sme splnili aj štvrtý bod.
Voľne prerozprávané to znamená, že chcete mať jednotky čo najviac vľavo vo vašom reťazci.↩