最省納智捷1年新車83萬起女大生禁不起誘惑!按了..輕忽小中風,當心變殘障不捨學生找「槌」 高中...
2012-01-12 20:03:08 人氣(458) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 11089 - Fi-binary Number

0
收藏
0
推薦

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
10
20
30
40

10010
101010
1010001
10001001




作法 : 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;
}

11089Fi-binary Number
台長:Morris
人氣(458) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 151 - Power Crisis
此分類上一篇:[UVA] 10327 - Flip Sort

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文