# 1122 程式設計實習IV (資訊一乙) Week05 作業

## 1. Bangla Numbers

---

### 題目敘述

Bangla numbers normally use ’kuti’ (10000000), ’lakh’ (100000), ’hajar’ (1000), ’shata’ (100) while expanding and converting to text. You are going to write a program to convert a given number to text with them.

---

### 題目輸入

The input file may contain several test cases. Each case will contain a non-negative number $\le 999999999999999$.

---

### 題目輸出

For each case of input, you have to output a line starting with the case number with four digits adjustment followed by the converted text.

---

### 範例輸入

23764
45897458973958

---

### 範例輸出

   1. 23 hajar 7 shata 64
   2. 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58

---

## 2. Fibonaccimal Base

---

### 題目敘述

The well known Fibonacci sequence is obtained by starting with $0$ and $1$ and then adding the two last numbers to get the next one. For example the third number in the sequence is $1 (1=1+0)$, the forth is $2 (2=1+1)$, the fifth is $3 (3=2+1)$ and so on.


The sequence appears on many things in our life, in nature, and has a great significance. Among other things, do you know that all positive integer numbers can be represented as a sum of numbers in the Fibonacci sequence? More than that, all positive integers can be represented as a sum of a set of Fibonacci numbers, that is, numbers from the sequence, without repetition. For example: $13$ can be the sum of the sets {$13$}, {$5,8$} or {$2,3,8$} and $17$ is represented by {$1,3,13$} or {$1,3,5,8$}. Since all numbers have this property (do you want to try to prove this for yourself?) this set could be a nice way to use as a "base" to represent the number. But, as we have seen, some numbers have more than one set whose sum is the number. How can we solve that? Simple! If we add the constraint that the sets cannot have two consecutive Fibonacci numbers, than we have a unique representation for each number! This restriction is because the sum of any two consecutive Fibonacci numbers is just the following Fibonacci number.
Now that we know all this we can prepare a nice way to represent any positive integer. We will use a binary sequence (just zeros and ones) to do that. For example, $17 = 1 + 3 + 13$ (remember that no two consecutive Fibonacci numbers can be used). Let’s write a zero for each Fibonacci number that is not used and one for each one that is used, starting at the right. Then, $17 = 100101$. See figure 2 for a detailed explanation. In this representation we should not have zeros at the left, this is, we should only write starting with the first one. In order for you to understand better, note that in this scheme, not using two consecutive Fibonacci numbers means that the binary sequence will not have two consecutive ones. When we use this representation for a number we say that we are using the Fibonaccimal base, and we write it like $17 = 100101$ (fib)


Given a set of numbers in decimal base, your task is to write them in the Fibonaccimal base.

---

### 題目輸入

The first line of input contains a single number $N$ , representing the quantity of numbers that follow ($1 \le N \le 500$).
Than follow exactly $N$ lines, each one containing a single positive integer smaller than $100000000$. These numbers can come in any order.

---

### 題目輸出

You should output a single line for each of the N integers in the input, with the format ‘DEC_BASE = FIB_BASE (fib)’. DEC_BASE is the original number in decimal base and FIB_BASE is its representation in Fibonaccimal base. See the sample output for an example.

---

### 範例輸入

10
1
2
3
4
5
6
7
8
9
10

---

### 範例輸出

1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)

---

## 作業繳交方式

- 交至ilearn作業繳交區
- 原始碼檔名以 學號_題號.c 或 學號_題號.cpp 命名 (example. D1109070_01.c 或是 D1109070_01.cpp)
- 兩題分兩個檔案上傳
- 在OJ上面有可以讓你檢視是否正確的作答區
- 名稱: [112 (資訊一乙) 程式設計IV Week05 作業]
- 密碼: PUPC