---
# System prepended metadata

title: 114 程式設計實習II (資訊一乙) Week09 作業

---

# 114 程式設計實習II (資訊一乙) Week09 作業
password: night
## 1. Power Strings

### 題目敘述

給你兩個字串 a ,b. 我們定義 a*b 是他們的連結.
例如:如果a="abc" ,b="def" 則 a*b ="abcdef".
如果我們把這種連結想成乘法,一個正常的整數指數會變成: $a^0$ =""(空字串) 與 $a^{(n+1)}=a\cdot(a^n)$. 

---

### 題目輸入

測試資料中有若干行
每一行代表著一個字串 s 
對於每個字串s,你應該要找出最大的 s = a^n 的n
s的長度最少為1最大不超過1百萬.
測試以"."作為結尾

---

### 題目輸出

對每個s輸出最大的n

---

### 範例輸入1

```
ABCD
AAAA
ababab
.
```

### 範例輸出1

```
1
4
3
```

## 2. Coin Collector

### 題目敘述

Sultan到某個國家旅行，那裡有n種不同類型的硬幣。
他想儘可能蒐集最多種不同類型的硬幣。如果他想從銀行提取X筆錢，銀行將使用以下算法將這筆錢給他：
```c
withdraw(X) {
    if(X == 0)
        return;
    令 Y 為其值不超過 X 且面額最大的硬幣。
    給客戶一個 Y 元的硬幣。
    withdraw(X-Y);
}
```
現在Sultan可以從銀行提取任意金額。他想要在一次提款中蒐集最多種不同類型的硬幣。

---

### 題目輸入

輸入的第一行包含一個整數T，代表測資數量。
每組測資第一行有一個整數n (1 ≤ n ≤ 1000)，代表不同類型硬幣的數量。
下一行包含n個整數C1、C2、...、Cn，分別代表每種硬幣的面額。
其中C1 < C2 < C3 < ... < Cn < 1000000000，且C1 = 1。

---

### 題目輸出

對於每組測資，輸出Sultan一次提款最多可以從銀行拿到幾種不同的硬幣。

---

### 範例輸入1

```
2
6
1 2 4 8 16 32
6
1 3 6 8 15 20
```

### 範例輸出1

```
6
4
```

## 作業繳交方式 Assignment Submission Instructions
* 交至ilearn作業繳交區
* 原始碼檔名以 學號_題號.c 命名 (example. D1109070_01.c, D1109070_02.c)
* 分爲兩個檔案上傳(限定 C 語言)
