uva 11089 - Fi-binary Number- fi-binary number > 문제은행 : 정보올림피아드&알고리즘



1422 : fi-binary number

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
14 회   
시도횟수
63 회   

문제

Fi-binary 수는 0 과 1 로만 이루어진 숫자이다. 이 숫자는 앞에 0 이 붙지 않으며, 2개의 연속된 1 이 나타나지 않는 숫자이다. 이 숫자를 크기 순 으로 늘어놓으면 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101... 와 같다. n이 주어졌을 때 n번째 Fi-binary 숫자를 찾는 프로그램을 작성하라.


입력형식

첫 번째에는 테스트 케이스의 개수 T가 주어진다(T≤10,000). 두 번째 줄부터 T개의 줄에는 찾고자 하는 Fi-binary 숫자의 순서 n(1≤n≤109)이 주어진다.

출력형식

각각의 테스트 케이스에 대해 n번째의 Fi-binary 숫자를 출력한다.

입력 예

4 
10 
20 
30 
40

출력 예

10010
101010
1010001
10001001


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP