Finále

B: Samé jedničky

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

První diplomatická mise na sousední exoplanetu S2 skončila úspěchem! Se zdejší mimozemskou civilizací došlo k rychlému navázání kontaktu. Problém ovšem nastal, když se začalo hovořit o počtech. Mimozemšťané totiž mají jen jednu číslovku - jedničku a všechna další čísla vytváří jen pomocí sčítání a násobení jedničkových výrazů. Generál Kája by se s nimi chtěl domluvit i početně, ale také by byl rád, kdyby při čtení vámi vytvořených čísel neusínali nudou - proto na zapsání čísla N můžete použít maximálně 300 znaků. Vaším úkolem je pro zadané číslo N vypsat způsob, jak zapsat číslo N pomocí jedničkového výrazu. V jedničkovém výrazu se může vyskytovat pouze číslo 1, a povolené operace jsou pouze sčítání a násobení. Můžeme také používat závorky. Priorita operátorů funguje jako obvykle – násobení má přednost před sčítáním.

Formálněji definujme jedničkový výraz takto:

  • 1 je jedničkový výraz
  • Pokud V je jedničkový výraz, pak (V) je také jedničkový výraz
  • Pokud V1 a V2 jsou jedničkové výrazy, pak V1+V2 a V1*V2 jsou oboje jedničkové výrazy

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testovacích vstupů.
Každý test se skládá z jediného řádku, na kterém je kladné číslo N – číslo, které chceme zapsat pomocí jedničkového výrazu.

Tvar výstupu

Pro každý testovací výstup vypište na samostatný řádek řetězec reprezentující jedničkový výraz, který se vyhodnotí na N daného testu. Jednotlivé jedničkové výrazy smí mít maximálně 300 znaků a musí se skládat pouze ze znaků 1+*(). Existuje-li více správných řešení, vypište libovolné z nich.

Lehká verze

  • T ≤ 20
  • 1 ≤ N ≤ 2 500

Těžká verze

  • T ≤ 20
  • 1 ≤ N ≤ 109

Ukázkový vstup

2
4
6

Ukázkový výstup

1+1+1+1
(1+1)*(1+1+1)



						

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)