[UVA] 11089 - Fi-binary Number
I I U P C 2 0 0 6 |
|
|
Problem F: Fi-binary Number |
|
|
Input: standard input Output: standard output |
|
|
|
|
|
A Fi-binary number is a number that contains only 0 and 1. It does not contain any leading 0. And also it does not contain 2 consecutive 1. The first few such number are 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101 and so on. You are given n. You have to calculate the n’th Fi-Binary number.
|
|
|
Input |
|
|
The first line of the input contains one integer T the number of test cases. Each test case contains one integer n.
|
|
|
Output |
|
|
For each test case output one line containing the n’th Fi-Binary number.
|
|
|
Constraints |
|
|
- 1 ≤ N ≤ 109
|
|
|
Sample Input |
Output for Sample Input |
|
4 |
10010 |
作法 : Greedy
#include<stdio.h>
int main() {
int F[45] = {1,2}, T, N, i;
for(i = 2; i < 45; i++)
F[i] = F[i-1] + F[i-2];
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
i = 44;
while(F[i] > N) i--;
for(; i >= 0; i--) {
if(F[i] <= N)
printf("1"), N -= F[i];
else
printf("0");
}
puts("");
}
return 0;
}