TSHOW1 - Amusing numbers


Amusing numbers are numbers consisting only of digits 5 and 6. Given an integer k , display the k-th amusing number.

Input

FIrst line consists of integer N representing number of test cases

Next N lines consist of N integers (1 <= k <= 10^15)

Output

N lines each displaying corresponding k-th amusing number

Example

Input:
2
1
5

Output:
5
65

hide comments
vl4deee11: 2024-07-06 07:38:48

nice!

manish_thakur: 2020-05-27 09:45:39

bit manipulation would do!

vikash: 2019-10-15 12:15:11

Submitted the same solution in Java and scala.
Scala shows time limit exceeded. Jave runs fine.
In scala only code to take input also exceeds time.

nitin_uniyal21: 2019-07-13 06:50:53

I did it using binary tree..
Create a binary tree, with root node * (empty)..
5 is left child and 6 is right child..
for instance n=11
record the parent and path of 11 i.e. 5, Left (parent = floor(n-1)/2, path = L if int(parent)==parent else R)
push the path to the stack and keep find parents.
now n=5
parent, path = 2, L
now n =2
parent = 0, R
generate the num..
later generate the num using the stack of recorded path

Last edit: 2019-07-13 06:52:35
tanav_shah1: 2019-05-15 00:03:26

Excellent question, brilliant concept !

raftar2097: 2018-10-30 08:28:27

nice go

salman3007: 2018-10-27 20:04:38

think binary!!!

karan_yadav: 2018-06-29 17:56:24

Hints
#1. https://www.spoj.com/problems/SILVER/
#2. Knowing the no. of digits in Kth amusing no. will help
#3. We just have 2 numbers 5/6. We have to form a number system using these two numbers. The only catch is in this number system 0/00/000/0000.......... will also hold values

Last edit: 2018-06-29 21:05:38
sonorous: 2017-09-29 07:52:52

AC in one go!!! Very good question!

vi1: 2017-07-16 13:15:39

Easy, but fun :)


Added by:Pandian
Date:2012-04-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:AOL code contest