---
# System prepended metadata

title: '[109-cpi] HW4'
tags: [' 109', ' cpi', homework]

---

---
tags: homework, 109, cpi
title: '[109-cpi] HW4'
---

# Homework 4
> Week 5 (10/12), Due: 10/19 09:00:00

* 範圍：Loop
* NOJ 

---

## Print a Repeated Pattern

> [name=Judge Girl]

### Description
請寫一個程式，讀入正整數 $n$\
接著會劃分為 $n$ phases\
第 $i-th$ phases 由正整數序列 $1$ 至 $i$ 所構成


### Input
一行輸入，包含一正整數 $n$


### Output
一行輸出，將每個phases輸出並換行


### Example Input \#1
    5


### Example Output \#1
    112123123412345

### Example Input \#2
    8
    
### Example Output \#2
    112123123412345123456123456712345678

### Hint
* 利用迴圈即可
* 原題連結請見[Link](https://judgegirl.csie.org/problem/0/13)

---

## Three Circles

> [name=Judge Girl]

### Description

You are given three circles, $C_1$, $C_2$, and $C_3$. The center of $C_1$ is at $(x_1,y_1)$, and its radius is $r_1$. The centers and radius of $C_2$ and $C_3$ are defined similarly. A point $(x,y)$ is within a circle if its distance is less than or equal to the radius of the circle. For example, Both $(1,0)$ and $(0,0)$ are within the circle that centered at $(0,0)$ and has radius $1$. Now given the centers and radius of the three circles, please find the number of points $(x,y)$ where both $x$, and $y$ are integers, that are within odd number of circles. Note that the circles can overlap arbitrarily, however, the radius is no more than $10$. As a result you must be careful about how to test points, so that your program will run fast, and without doing unnecessary testing.

給定三個圓圈 $C_1$, $C_2$ 和 $C_3$。其中 $C_1$ 以 $(x_1,y_1)$ 為圓心、$r_1$ 為半徑。$C_2$ 和 $C_3$ 的圓心與半徑定義與 $C_1$ 類似。當一個點 $(x,y)$ 至圓心的距離小於或等於半徑時，我們可以說這個點位於圓內。例如，$(1,0)$ 和 $(0,0)$ 位於一個以 $(0,0)$ 為圓心、$1$ 為半徑的圓內。現在給定三個圓的圓心與半徑，請找到有多少個格子點位於奇數個圓內。圓與圓之間可以任意重疊，並且圓的半徑不會大於 $10$。注意測試格子點的方法，使得你的程式能夠跑得足夠快、避免做一些不必要的測試。

### Input

The first line of the input is the number of input cases. Each input case has three lines and each line has the $x$, $y$, coordinates of a circle, followed by the radius. The radius is no more than $10$.

第一行輸入一個整數，代表接下來將會有幾組的測試。對於每一組的測試，將會輸入三行。每一行包含三個整數 $x, y, r$，分別代表圓心 $(x, y)$ 以及半徑 $r$。

- $r \le 10$

### Output

對於每一組測試，輸出有多少個格子點位於奇數個圓內。

### Example Input

```
2
0 0 1
0 0 2
2 0 1
0 0 1
1000000 0 1
0 1000000 1
```

### Example Output

```
11
15
```

### Hint

格子點 $(x, y)$ 是當 $x$、$y$ 皆是整數的點。

### Subtask

---

## 心跳！戀愛占卜

> [name=博傑]

### Description

奉心祭，秀知院學園在每年的寒假之前所舉辦的文化祭，是學校裡非常重要的活動之一，今年經過會長的努力爭取，變成了為期兩天的大型活動，全校上下無不熱火朝天的迎接這個年度盛事，當然，大家的亂源 --- 書記也不例外。

關於奉心祭，在學校內一直流傳個一個傳說，只要在這天送出心型的禮物，就可以得到永恆的愛情，而自詡為戀愛偵探的書記，自然也要在這天參一腳，她決定要在奉心祭擺一個攤位 --- 戀愛占卜！

書記她占卜的步驟如下

1. 首先，她會準備一條長 1 公尺($10^9$ 奈米)的透明膠帶，並且我們以一個整數來描述膠帶上的位置，$p$ 代表的是距離膠帶最左邊 $p$ 奈米遠的位置
1. 然後來占卜的客人會隨機挑選兩個數字 $p_1, q_1$，書記也會隨機挑選兩個數字 $p_2, q_2$
2. 將 $[p_1, p_2], [q_1, q_2]$ 這兩個區間塗上紅色
1. 書記接下來會在心中選定一個數字 $n$，並在接下執行 $n$ 次的摺膠帶操作
1. 每次摺膠帶時，她會隨機挑選一個座標 $x$，以它為中心點，由左向右摺，並且更新膠帶上的座標，原本座標為 $p$ 的位置，在對摺過後會變成 $|p - x|$
1. 執行完 $n$ 次操作之後，如果紅色的長度她看得順眼的話，那麼她就會為客人送上一個心型吊飾祝福他的愛情

然而，要計算這麼複雜的數學對於 IQ 只有 3 的書記來說實在是太困難了，現在請你寫個程式幫幫書記，算出最後的紅色區域覆蓋長度。

### Input

第一行為四個以空白隔開之正整數 $p_1, q_1, p_2, q_2$  
第二行為一個正整數 $n$  
接下來 $n$ 行，每行皆為一個整數 $x$

#### Limits

$0 \le p_1 < p_2 < q_1 < q_2 \le 10^9$  
$1 \le n \le 10^5$  
$0 \le x \le 10^9$

### Output

請輸出一個整數於一行，代表最後的紅色覆蓋長度

### Example Input

```
0 10 5 15
1
0
```

### Example Output

```
10
```

### Example Input

```
1 3 2 4
1
2
```

### Example Output

```
1
```

### Example Input

```
0 110 100 120
3
60
10
10
```

### Example Output

```
40
```

### Hint

1. 改編自 TOPC 2020, pB
1. 最後書記因為沒辦法以奈米為單位來摺膠帶而沒有擺成，可喜可賀。

#### 第一組範例測資

這組範測給定了兩個線段 $[0, 5]$ 和 $[10, 15]$，兩者長度皆為 $5$，並且後續摺膠帶的位置是 $0$，並沒有影響到兩個紅色線段，所以答案會是 $5 + 5 = 10$

#### 第二組範例測資

這組的線段分別是 $[1, 2]$ 和 $[3, 4]$，並且摺在 $2$ 這個位置上，所以兩個線段的座標都被更新成了 $[0, 1]$，最後覆蓋長度為 $1$

### Subtask

| Case      | Describe     | Per. |
|:--------- |:------------ | ----:|
| #1        | $n=1$, $x=0$ |  10% |
| #2        | 所有 $x=1$   |  50% |
| #3        | 無特殊限制   |  40% |
| **Total** |              | 100% |

---

## HS Value

> 感覺出 digit 還是比較經典\
> 資結 => matrix感覺會被罵XD
> [name=育辰]

### Description

阿弘上課時，一心覺得無趣，看著窗外發呆...在腦海中他定義了 $\text{Happy value}$ & $\text{Sad value}$，合稱為 $\text{HS Value}$。
\
\
是這樣的，今給定一組 $\text{Type}, \  \text{Integer}$, 若型態為 $1$，則為 $\text{Happy value}$, 型態為 $2$，則為 $\text{Sad value}$。
\
\
假使 $\text{Integer}$ 給定為 $2458$, $\ \text{Happy value}$ 計算則由 $2$ 開始乘以 $1$，加上 $4$ 乘以 $2$...每加一位數，乘的基數就會增加 $1$，因此 $2458$ 的 $\text{Happy value}$ 為$$2 \times 1 + 4 \times 2 + 5 \times 3 + 8 \times 4 = 57$$
\
而 $\text{Sad value}$ 則是從個位數開始，與以上計算相同，因此 $2458$ 的 $\text{Sad value}$ 為$$8 \times 1 + 5 \times 2 + 4 \times 3 + 2 \times 4 = 38$$
\
$\text{HS value}$ 則為 $\text{Happy value}$ 以及 $\text{Sad value}$ 的「差」，換句話說就是在一維數線上的「距離」，例如上題，則其 $\text{HS value}$ 為 $$|57-38|=19$$\
**正式定義如下：**\
假定將第 $i$ 位數之數值，定為 $\text{digit}_i$, 則： $$\text{Happy value} = \sum_{i=1}^n{(\text{digit}_i \times (n-i+1))}$$

$$\text{Sad value}=
\sum_{i=1}^n{(\text{digit}_i \times  i)}$$

$$\text{HS value} = | \, \text{Happy value} - \text{Sad value} \, |$$


### 測資說明
起初給定一整數 $n$，表示接著有 $n$ 筆資料，接著每行會有一整數 $a_i$，對於每筆資料：
* 在該行輸出兩個數值，以一格空格分開，注意**行末沒有空格**，先輸出 $\text{Happy value}$ 再輸出 $\text{Sad value}$
* 隔一行輸出一個整數 $\text{HS value}$，因此，輸出總共應該會有 $2n$ 行


### Input
Line $1$: 一整數 $n$，表示接著有 $n$ 筆輸入資料\
Line $2$ ~ $(n+1)$: 一整數 $a_i$

### Limit
* $1 \leq n \leq 4.5 \times 10^6, \ n \in \mathbb{N}$
* $0 \leq a_i \leq 2^{31}-1, \ a_i \in \mathbb{N}$
* Output的答案不會超出 $2^{31}-1$



### Output

* 針對輸入的每筆資料，先以一行輸出 $\text{Happy value}$ 以及 $\text{Sad value}$，請以空格隔開，行末**沒有空格**
* 接著，隔行輸出 $\text{HS value}$



### Example Input 0
    1
    2458


### Example Output 0
    57 38
    19
    
    
### Example Input 1
    4
    54321
    12345
    0
    86355231

### Example Output 1
    35 55
    20
    55 35
    20
    0 0
    0
    115 182
    67


### Hint
* 拿出紙筆模擬，並標明每次跑的位置，從中觀察規律去設計迴圈
* 注意 Happy value & Sad value是同行以空格隔開，VS value則在隔行輸出
* 範例測資1中 `54321`：
    1. `Happy value` 
    $$=5 \times 1 + 4 \times 2 + 3 \times 3 + 2 \times 4 + 1 \times 5$$
    $$= 5 + 8 + 9 + 8 + 5$$
    $$=35$$
    2. `Sad value`
    $$=5 \times 5 + 4 \times 4 + 3 \times 3 + 2 \times 2 + 1 \times 1$$
    $$= 25 + 16 + 9 + 4 + 1$$
    $$= 55$$
    3. `HS value`
    $$=| \ 35 - 55 \ | = 20$$
* 範例測資1中 `86355231`
    1. `Happy value`
    $$=8 \times 1 + 6 \times 2 + 3 \times 3 + 5 \times 4 + 5 \times 5 + 2 \times 6 + 3 \times 7 + 1 \times 8$$
    $$=8+12+9+20+25+12+21+8$$
    $$=115$$
    2. `Sad value`
    $$=8 \times 8 + 6 \times 7 + 3 \times 6 + 5 \times 5 + 5 \times 4 + 2 \times 3 + 3 \times 2 + 1 \times 1$$
    $$=64+42+18+25+20+6+6+1$$
    $$=182$$
    3. `HS value`
    $$=| \ 115 - 182 \ | = 67$$

### Subtask
|Case|Describe|Per.|
|:--|:--|--:|
|#1|$n=1$, $a_i \neq 0$|30%|
|#2|無特殊限制|70%|
|**Total**||100%|

> 該題切入點，百年不變的經典，給定一個數字將其digit全部相加，當然要把題目改難一點，在計算digit的同時需要做額外的處理，這題難度還是不高，但就上週情況看感覺這題AC率猜測會在33%

### [測資載點](https://drive.google.com/file/d/1YY_AfnHWx_yXVL2ALOhSpb8EICNwQtxc/view?usp=sharing)

---

## 大小姐的放學路

> [name=映達]

### Description

放學後學生們皆已離校，學生會室裡也只剩下會長和大小姐。平時的話，大小姐上下學都有專人接送；今天不湊巧，大小姐的手機因為沒電而關機，無法聯絡司機來接她。一切都看在眼裡的會長，決定護送大小姐走路回家。

此時正逢小雪，銀白色中只有兩人的身影，悄然散落的雪花使得整條街格外寧靜。在這樣的時空裡，會長和大小姐必須透過聊天才能免於尷尬。聰明機靈的他們，此時卻因為害羞和緊張，需要間隔一段路程才能找到話題。更嚴重的是，因為變得反應遲緩，兩人皆成為了句點王！好不容易開啟的話題，總會神奇地在三步路以內被結束。

聊天的過程中（雖然話題過於短暫）有一種情況特別讓人心跳加速。「四宮（大小姐）啊⋯⋯」「會長啊⋯⋯」。沒錯！就是當男女同時開口的時候！當兩人同時開口時，總是會頓時語塞，並產生「啊，這個人跟我好有默契啊」的想法（錯覺），不由地心頭一緊、小鹿亂撞。

假設從「校門口」至「大小姐家大門」的距離為 $m$、「兩人目前的位置」至「校門口」的距離為 $x$。每當 $m$ 可以被 $x$ 整除時，會長便會想到一個新的話題，並且開口：「四宮啊⋯⋯」；每當 $x$ 為質數時，大小姐便會想到一個新的話題，並且開口：「會長啊⋯⋯」。每一個話題（因為很短暫）保證都會在其中一人想到新話題前結束、同時開口的情況只會在開啟新話題時發生。請你計算一路上總共會出現幾次，兩人因為同時開口導致的心動時刻（最後一次同時開口有可能發生在大小姐家的大門口）。

### Input

輸入一個整數 $m$，代表從「校門口」至「大小姐家大門」的距離（先不管距離的單位是什麼，或這個距離合不合理）。對於所有輸入：

- $2 \le m \le 10^8$

### Output

輸出一個整數，代表一路上總共會出現幾次，兩人同時開口的心動時刻。

### Example Input 0

```
88318230
```

### Example Output 0

```
8
```

### Example Input 1

```
99999989
```

### Example Output 1

```
1
```

### Hint
