---
tags: homework, 109, cpi
title: '[109-cpi] HW13'
---
# Homework 13
> Week 16 (12/28), Due: 01/04 09:00:00
* 範圍：**字串**
* NOJ
---
## Repeating Cycle
> [name=映達]
### Description
給定一個字串 $S$，請找出最短的子字串 $T$，使得 $T$ 可以重複 $n$ 次，剛好會是 $S$。
### Input
第一行有一個整數 $m$，代表字串 $S$ 的長度。
第二行為字串 $S$ 。
- 字串 $S$ 只包含大小寫英文字母。
### Output
輸出一個字串 $T$ 。
#### Subtasks
| | Limits |Score |
|:---|:---------|-----:|
| #0 | $0 \lt m \le 1000$ | $100$ |
| **Total** | | $100$ |
### Example Input 0
```
21
asdfghjasdfghjasdfghj
```
### Example Output 0
```
asdfghj
```
### Example Input 1
```
10
HelloWorld
```
### Example Output 1
```
HelloWorld
```
### Hint
---
## 愛吃拉麵的書記同學
> [name=博傑]
### Description
書記他非常的喜歡吃拉麵，時常出去尋覓好吃的拉麵，像是之前在[出去騎車減肥時](https://noj.tw/problem/44)，便順道去巢鴨（地名）品嘗了超辣的地獄拉麵。
說到拉麵，那可是一門學問，雖然同樣都是拉麵，但其內可是各有千秋，像是一幻拉麵、五之神製作所等店便是以濃郁的鮮蝦湯頭聞名；另外像是麵屋壹慶則以湯頭濃郁為特色的泡系拉麵；或是雞二、麵屋壹之穴等店便是以大份量為特色的二郎系拉麵聞名。
而書記他今天尋覓到的便是一間二郎系拉麵。講到二郎系的話還有一個特色便是他的配料（トッピング，topping）調整，總共會分成四種選項：
1. 蔬菜（ヤサイ，yasai）
2. 大蒜（ニンニク，ninniku）
3. 油脂（アブラ，abura）
4. 醬汁（カラメ，karame）
而這些配料的份量又會分成：
1. 加爆（マシマシ，mashimashi）
2. 增量（マシ，mashi）
3. 減量（少なめ，sukuname）
4. 不加（抜き，nuki）
舉例來說，當今天你想要的調整是
- 蔬菜加爆
- 大蒜增量
- 油脂正常
- 醬汁減量
那麼就要跟店員講
> ヤサイマシマシ、ニンニクマシ、カラメ少なめ
上面因為油脂的部分不用特別調整，因此可以省略不講。
另外還會有兩種特別的情況，一種是需要一致的調整時，可以用「全」來代替，例如說我想要全部配料都加爆，這時候你可以跟店員講「全マシマシ」，而另外一種是全部都不需要特別調整的「そのまま」。
另外還有麵量的調整，在二郎系店家當中，正常分量的拉麵會稱作「小ラーメン」（koramen），而加大份量的則是「大ラーメン」（dairamen），不過雖然叫做小，那麵的份量已經跟其他店家的大碗差不多了。
現在告訴你書記的點單，請你輸出她最後拉麵的數據吧。
### Input
輸入僅包含一行字串，代表書記的拉麵調整。
字串由各種調整參數組成，並且各參數以一個空白隔開。
參數會有以下幾種情況：
1. 麵量調整：
`koramen` 或是 `dairamen`，分別代表小或是大。
2. 配料調整：
用空白隔開的兩個字串，分別代表種類跟份量。
舉例來說：大蒜增量就會是 `ninniku mashi`、不加蔬菜是 `yasai nuki`。
3. 全部一起調整：
當全部都要一致調整時，第 2 點的配料種類會變成 `zen`。
例如當我想要全部都不加的時候，就會是 `zen nuki`。
需要注意的是，如果出現這種參數，則再出現**麵量以外**的調整時都會是**非法的輸入**。
4. 不需要調整：
會輸入一個 `sonomama`。
此時再出現除了**麵量以外**的調整都是**非法的輸入**。
另外需要注意的是，當任意一個種類的參數**重複出現**時，也會算做**非法的輸入**。
像是重複調整蔬菜份量、或是講了兩次麵量等等。
但題目保證不會出現沒有定義在上面的字串，像是在應該是配料的地方出現 `neko` 等情況。
#### Limit
輸入字串長度小於 $300$
### Output
輸出書記的點單，若是一個非法的輸入，請輸出一行 `imi wakannai`（日文的「意義不明」的羅馬拼音）。
點單格式如下所示：
```
ramen
yasai
ninniku
abura
karame
```
其中，`ramen` 的部分要填入 `koramen` 或是 `dairamen`，若輸入時沒有針對麵量調整時應填入 `koramen`。
剩下四行則依序分別填入`配料名稱`跟`份量`，若無調整則可以省略不填。
以題敘中提到的「蔬菜加爆、大蒜增量、油脂正常、醬汁減量」為例，會得到的輸出會是
```
koramen
yasai mashimashi
ninniku mashi
karame sukuname
```
#### Subtasks
| | Limits | Score |
|:--------- |:---------------------------------------- | -----:|
| #0 | 點單合法，不會出現 `zen` 或是 `sonomama` | $50$ |
| #1 | 點單合法 | $30$ |
| #2 | 無其他限制 | $20$ |
| **Total** | | $100$ |
### Example Input 0
```
dairamen yasai mashi ninniku mashimashi abura sukuname karame nuki
```
### Example Output 0
```
dairamen
yasai mashi
ninniku mashimashi
abura sukuname
karame nuki
```
### Example Input 1
```
yasai nuki
```
### Example Output 1
```
koramen
yasai nuki
```
### Example Input 2
```
sonomama dairamen
```
### Example Output 2
```
dairamen
```
### Example Input 3
```
zen mashimashi zen mashimashi abura sukuname
```
### Example Output 3
```
imi wakannai
```
### Hint
- 題敘中名詞中文部分為個人翻譯，可能與實際意思稍有出入。
---
## Sentence Count
> [name=Judge Girl]
### Description
寫一個程式計算輸入文章中的句子數。為求簡單起見我們假設一個句子的結束必定為一個句點。但是為了避免像 "Mr." "i.e." 這樣的問題，我們規定符合下面四種狀況之一才算是一個句子 :
* 句點後面必須有兩個連續空白 `' '`
* 句點後面就是換行 `'\n'`
* 句點後面就是 EOF `'\0'`
* 句點到 EOF 之前只有空白或換行
---
* **sentence.h**
```cpp=
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
int solve();
//optional
bool Is_Sentence(char str[], bool *have_dot);
char *read_input(char str[]);
```
---
* **main.c**
```cpp=
#include "sentence.h"
int main(){
printf("%d\n", solve());
return 0;
}
```
---
* **sentence.c**\
<font color="blue">你應該要<b>實作</b>的檔案</font>
```cpp=
#include "sentence.h"
bool Is_Sentence(char str[], bool *have_dot){
//optional
}
char *read_input(char str[]){
//optional
}
int solve(){
//一定要有
}
```
### Input
* 輸入為數行文字，直到 `EOF` 結束。
### Output
* 請輸出共有幾個符合題意的句子。
#### Subtasks
| |Score |
|:---|-----:|
| #0 | $30$ |
| #1 | $35$ |
| #2 | $35$ |
| **Total** | $100$ |
### Example Input 0
```
The Declaration of Independence was a
statement adopted by the Continental Congress
on July 4, 1776, which announced that the
thirteen American colonies then at war with
Great Britain regarded themselves as independent
states, and no longer a part of the British
Empire. Written primarily by Mr. Thomas Jefferson
the Declaration was a formal explanation of why
Congress had voted on July 2 to declare
independence from Great Britain, more than a
year after the outbreak of the American
Revolutionary War. The birthday of the United
States of America-Independence Day-is celebrated
on July 4, i.e., the day the wording of the
Declaration war approved by Congress.
```
### Example Output 0
```
3
```
### Hint
* 本題搬運自 [Judge Girl](https://judgegirl.csie.org/problem/0/220)
* scanf讀取字串，遇到空格會斷掉，因此建議使用 `fgets`
* `fgets(字元陣列位址, 讀取長度, stdin);`
* 可以用 `getchar` 或 `scanf("%c", &chr)`一一讀取，以一個`index`讓他能夠遞次放到一個字元陣列中
* 或也可以使用 `fgets`，會讀到該行末為止，且會包含`\n`，以及空格
* [可參考的網頁](https://openhome.cc/Gossip/CGossip/PutcharGetcharPutsGets.html)
* 使用方法參考：
```cpp=
char str[100];
fgets(str, 100, stdin);
```
---
## [Judge Girl](https://judgegirl.csie.org/problems/domain/0#8)
---
## Typesetting
> [name=Judge Girl]
### Description
編寫一個排版程式。程式必須將輸入的字逐一讀入，再逐一輸出。一個字的定義是「連續非空白的字元」，例如 `7`、`empire`. 都算是字。也就是說我們可以用 `scanf("%s", string)` 讀入一個字。
### Input
輸入的第一行是每行可輸出的字元數 $m$，之後就是要排版的文章，每個英文字的最大長度為 $256$ 個字元，輸入請讀取到 `EOF` 結束。
### Output
輸出請將所有的字依序印出，兩個字之間要以至少一個空格隔開。我們的目標是要利用最少且盡量平均分配的空格使得每一行輸出恰好 $m$ 個字元(包含空白，不包含換行)。也就是我們要盡量把字放在同一行，而當我們必須要開新的一行時，若原本的那行字串 + 空白的長度不足 $m$，我們要在字之間補上更多的空白。如果空格無法平均分配，則多的空格必須加在前面的字後面。
#### Limits
- $32 \le m \le 256$，每個字串的字元數保證不會超過 $m$ 個 。
### Sample Input
```
40
The Declaration of Independence
was a statement adopted by the
Continental Congress on July 4,
1776, which announced that the
thirteen
American colonies then at war with
Great Britain regarded themselves as
independent
states, and no longer a part of the British
Empire.
Written primarily by Thomas Jefferson,
the Declaration was a formal explanation of why Congress had
voted on July 2 to declare
independence from Great Britain, more than
a year
after the outbreak of the American Revolutionary War.
The birthday of the United States
of America-Independence Day-is celebrated on
July 4, the day
the wording of the Declaration was approved
by Congress.
```
### Sample Output
```
The Declaration of Independence was a
statement adopted by the Continental
Congress on July 4, 1776, which
announced that the thirteen American
colonies then at war with Great Britain
regarded themselves as independent
states, and no longer a part of the
British Empire. Written primarily by
Thomas Jefferson, the Declaration was a
formal explanation of why Congress had
voted on July 2 to declare independence
from Great Britain, more than a year
after the outbreak of the American
Revolutionary War. The birthday of the
United States of America-Independence
Day-is celebrated on July 4, the day the
wording of the Declaration was approved
by Congress.
```
### Hint
* 原題搬運至[Judge Girl](https://judgegirl.csie.org/problem/0/221)
---
## String Fusion
> [name=Judge Girl]
### Description
Write a program to do string `"fusion"`. The fusion is similar to string concatenation but it will combine the suffix of the first string and the prefix of the second string if they are the same. For example if you fuse `"abcd"` with `"cdef"` then you will get `"abcdef"`. Also the fusion will try to fuse as many characters as possible. For example, if you fuse `"abccc"` with `"cccde"` then you will get `"abcccde"`, not `"abccccde"`, nor `"abcccccde"`.
### Input
The input consists of a series of (at least two) nonempty strings consisting of lower case letters, and you need to fuse the next one to the result of previous fusion. You must process all string until `EOF`. Each string and all the intermediate results have no more than $127$ characters.
### Output
The final fusion result.
### Sample Input
```
a
b
c
bcde
bcde
cdefghi
ghi
ghi
ghijk
abcdefghijklmn
zzz
zzzz
abc
```
### Sample Output
```
abcdefghijklmnzzzzabc
```
### Hint
* 原題搬運自 [Judge Girl](https://judgegirl.csie.org/problem/0/260)
Sign in with Wallet
Connect another wallet