30069번 - Grąža 다국어

Bitlandijos prekybos tinklas „Baxima“ nori modernizuoti savo parduotuves ir įrengti išmanius kasos aparatus. Vienas iš išmaniosios kasos komponentų yra robotas, gebantis automatiškai grąžinti grąžą bitais (Bitlandijos valiuta).

Bitų banknotai turi šiuos nominalus: $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$.

Dienos pradžioje kasa yra tuščia. Toliau yra registruojamos visos transakcijos: į kasą įdedamų banknotų nominalai. Trūksta tik programinės įrangos, kuri suskaičiuotų, kaip geriausia parinkti grąžą kiekvienam klientui.

Parašykite progamą, kuri rastų, kokiais nominalais robotas turi duoti grąžą, kad kiekvienam klientui būtų atiduodama kuo mažiau banknotų.

Pirmoje eilutėje įrašytas transakcijų skaičius $T$. Sekančiose $T$ eilučių įrašyta po vieną skaičių $t_i$:

• Jei $t_i > 0$, tai jis bus lygus vienam iš galimų Bito valiutos nominalų, ir reiškia, kad į kasą įdedamas šio nominalo banknotas.
• Jei $t_i < 0$, tai reiškia, jog klientui reikalinga grąža, ir iš kasos reikia išimti atitinkamus banknotus.

Kiekvienai grąžos transakcijai ($t_i < 0$), jūs turite išvesti po eilutę, kurioje būtų įrašyti grąžai panaudoti banknotai, nuo didžiausio iki mažiausio. Nepamirškite, jog robotas turi grąžinti pinigus taip, kad banknotų skaičius būtų kuo mažesnis.

Laikykite, kad kasoje visuomet bus pakankamai banknotų, kad pavyktų duoti grąžą klientui.

• $1 ≤ T ≤ 1\,000$
• $-10^6 ≤ t_i < 0$ arba $t_i ∈ \{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024\}$.