TAP2014B - Balanced base-3

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2014 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf ]

Throughout history many different numbering systems have been developed. Some, like Roman numerals, have now been almost completely abandoned due to their lack of convenience. Other even more exotic numbering systems are only ever used in certain applications, such as the factoradic numbers in the context of permutation numbering. In this problem we will consider a numbering system known as balanced base-3, which naturally appears in the analysis of diverse mathematical problems related to balance scales.

The balanced base-3 system is similar to the decimal or base-10 system we are familiar with in that it is positional. Positional numbering systems have digits whose relative order determines which power of the base accompanies them. For example, in base-10 we have

123 = 1×102 + 2×101 + 3×100.

In standard positional systems, the allowed digits are the numbers from 0 to B-1, where B is the base of the corresponding system. Therefore, the number 123 in base-10 is written in standard base-3 as "11120" because

1×34 + 1×33 + 1×32 + 2×31 + 0×30 = 123.

Balanced base-3 is different from standard base-3 only in the fact that the allowed digits are 0, 1 and -1, which we will respectively denote as '0', '+' and '-'. Then, the number 123 in base-10 is written as "+----0" in balanced base-3, for we have

1×35 + (-1)×34 + (-1)×33 + (-1)×32 + (-1)×31 + 0×30 = 123.

Conversion from numbers in base-10 to balanced base-3 is a mechanical and somewhat tedious process, so we require a program to do it for us. Can you help?

Throughout history many different numbering systems have been developed. Some, like Roman numerals, have now been almost completely abandoned due to their lack of convenience. Other even more exotic numbering systems are only ever used in certain applications, such as the factoradic numbers in the context of permutation numbering. In this problem we will consider a numbering system known as balanced base-3, which naturally appears in the analysis of diverse mathematical problems related to balance scales.
The balanced base-3 system is similar to the decimal or base-10 system we are familiar with in that it is positional. Positional numbering systems have digits whose relative order determines which power of the base accompanies them. For example, in base-10 we have
123 = 1*10^2 + 2*10^1 + 3*10^0.
In standard positional systems, the allowed digits are the numbers from 0 to B-1, where B is the base of the corresponding system. Therefore, the number 123 in base-10 is written in standard base-3 as "11120" because
1*3^4 + 1*3^3 + 1*3^2 + 2*3^1 + 0*3^0 = 123.
Balanced base-3 is different from standard base-3 only in the fact that the allowed digits are 0, 1 and -1, which we will respectively denote as '0', '+' and '-'. Then, number 123 in base-10 is written as "+----0" in balanced base-3, for we have
1*3^5 + (-1)*3^4 + (-1)*3^3 + (-1)*3^2 + (-1)*3^1 + 0*3^0 = 123.
Conversion from numbers in base-10 to balanced base-3 is a mechanical and somewhat tedious process, so we require a program to do it for us. Can you help?
Input
The first line contains an integer number T, the number of test cases (1 ≤ T ≤ 200). T test cases follow.
Each test case is described by a single line containing a positive integer number N, the number in base-10 that we want to write in balanced base-3 (1 <= N <= 1000).
Output
For each test case, print a single line containing a string composed solely of the characters '0', '+' and '-', and not beginning with '0', representing the digits of the number N in balanced base-3. Note that the restriction that the string does not start with a '0' ensures this representation is unique.

Input

The first line contains an integer number T, the number of test cases (1 ≤ T ≤ 200). T test cases follow.

Each test case is described by a single line containing a positive integer number N, the number in base-10 that we want to write in balanced base-3 ( N  1000).

Output

For each test case, print a single line containing a string composed solely of the characters '0', '+' and '-' and not beginning with '0', representing the digits of the number N in balanced base-3. Note that the restriction that the string does not start with a '0' ensures that this representation is unique.

Example

Input:
2
123
729

Output:
+----0
+000000

hide comments
iet17_rv: 2018-01-03 16:56:55

plz check ......this code ........20912648......its giving WA... :(

nadstratosfer: 2017-11-11 23:58:29

Spent 2 hours trying to get it done properly, almost broke the keyboard out of frustration. Finally gave up and AC'd with a stupid solution that wouldn't survive a large n. What a tricky little bitch of a problem.

Avinab saha: 2015-06-05 08:50:05

AC in 1 go:) very simple for 0.27 points :))

Insomniac: 2015-05-31 21:27:55

easy..... AC in one go :)

anshal dwivedi: 2015-03-07 06:56:30

easy one .. AC in one go..

Abhinandan Agarwal: 2015-02-28 19:17:35

larger n would have been more challenging ...

ivar.raknahs: 2014-10-02 01:08:28

easy one
AC.
i agree with nitish rao.

Last edit: 2014-10-01 08:50:04
Héctor Martín Peña Pollastri: 2014-10-02 01:08:28

@nitish rao: Don't think so, there is a O(log(N)) solution.


Added by:Fidel Schaposnik
Date:2014-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2014