TAP2014B  Balanced base3
[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/tap2014problems.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 base3, which naturally appears in the analysis of diverse mathematical problems related to balance scales.
The balanced base3 system is similar to the decimal or base10 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 base10 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 B1, where B is the base of the corresponding system. Therefore, the number 123 in base10 is written in standard base3 as "11120" because
1×3^{4} + 1×3^{3} + 1×3^{2} + 2×3^{1} + 0×3^{0} = 123.
Balanced base3 is different from standard base3 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 base10 is written as "+0" in balanced base3, 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 base10 to balanced base3 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 base10 that we want to write in balanced base3 (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 base3. 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
Avinab saha:
20150605 08:50:05
AC in 1 go:) very simple for 0.27 points :)) 

Insomniac:
20150531 21:27:55
easy..... AC in one go :) 

anshal dwivedi:
20150307 06:56:30
easy one .. AC in one go..


Abhinandan Agarwal:
20150228 19:17:35
larger n would have been more challenging ... 

ivar.raknahs:
20141002 01:08:28
easy one


Héctor Martín Peña Pollastri:
20141002 01:08:28
@nitish rao: Don't think so, there is a O(log(N)) solution. 

nitish rao:
20141002 01:08:28
It would have been a good problem, if N is quite large. 

Fidel Schaposnik:
20141002 01:08:28
@Vignesh Manoharan: format seems correct, answers are not... 
Added by:  Fidel Schaposnik 
Date:  20140929 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2014 