SORTMUCH - How many can you sort?

You have invented a new sorting algorithm which can sort n integers in exactly n log3 n time. (which is faster than almost every sorting algorithm till date). You have proved the correctness of your algorithm to your professor.

The professor now asks you what is the maximum number of integers that you can sort in a given time T.

Note: log3 = (log to the base 3)

Proper usage of type casting is required to solve this problem. For testing purposes you can use this high precision calculator.

Input:

The first line consists of an integer t. For each test case, you are given an integer T, the time to sort the integers.

Output:

For each test case, print the maximum number of integers that you can sort in T time.

Constraints:

1 <= t <= 10^5

3 <= T <= 10^10

Time limit: 1 second

Example:

Input:
4
3
10
10000000000
4374

Output:
3
6
546076908
729

Added by:cegprakash
Date:2016-11-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: MAWK BC BF NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-11-27 17:49:15 cegprakash
If you are using log(3), try using log((long double)3). This may improve precision.

Also note that long double precision is only till 10^-12. (i.e. you cannot compare two long double values using == operator) . Make use of the precision range.


Last edit: 2016-11-27 17:55:47
2016-11-26 20:49:33 cegprakash
may be this calculator will help you : http://keisan.casio.com/calculator
2016-11-26 20:48:42 cegprakash
no. It'll take exactly 1000000000000000026 time for n=28982938116442170
2016-11-26 20:38:56
Both 28982938116442170 and 28982938116442169 seem to be valid answers (for the third test case). How to decide which one to print?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.