---
# System prepended metadata

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

---

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

# Homework 6
> Week 7 (10/26), Due: 11/16 09:00:00

* 範圍：**Array**
* NOJ 

---

## 小畫家（一）
> [name=映達]

### Description

請模擬一個畫布大小為 $1 \times n$ 的小畫家，並可以支援以下 3 種操作：

1. 畫筆：
    - 給兩個座標 $P_1$、$P_2$，從 $P_1$ 畫到 $P_2$。
2. 擦布：
    - 給兩個座標 $P_1$、$P_2$，將 $P_1$ 到 $P_2$ 的筆跡清除。
3. 水桶：
    - 給一個座標 $P_1$，從該座標往左往右填滿至畫布邊緣或筆跡。
    - 換句話說，本操作會將與 $P_1$ 相鄰且顏色與 $P_1$ 相同的區塊畫上筆跡 `X`。
        - 若 $P_1$ 為 `.` ，則周圍所有的 `.`（包含 $P_1$）填成 `X`。
        - 若 $P_1$ 為 `X` ，則周圍所有的 `X`（包含 $P_1$）填成 `X`。（看起來相當於沒有變化）

座標範圍為 $0$ ~ $n - 1$。  
畫布一開始皆為空白（用 `.` 表示），筆跡用 `X` 表示。對於在畫布外的操作將會被忽略。

### Input

第 $1$ 行，輸入兩個整數 $n$ 和 $m$，代表這是一個 $1 \times n$ 的畫布，並且接下來將會有 $m$ 次的操作。  
第 $2$ ~ $m+1$ 行，首先會輸入一個整數，代表一種操作。接著會根據該操作，有 $1$ 到 $2$ 個不等的整數，代表操作所需的座標：

1. 畫筆：$2$ 個座標 $P_1$、$P_2$。
2. 擦布：$2$ 個座標 $P_1$、$P_2$。
3. 水桶：$1$ 個座標 $P_1$。

對於所有輸入：

- $1 \le n,\,m \le 10$
- $-2^{31} \le P_1,\,P_2,\,Q_1 \le 2^{31} - 1$

#### Subtasks

|    | Limits |Score |
|:---|:-------|-----:|
| #0 | 操作只會有畫筆 | $35$ |
| #1 | 操作只會有畫筆、擦布 | $35$ |
| #2 | 無其他限制 | $30$ |
| **Total** |  | $100$ |

### Output

輸出目前畫布的樣子，空白的地方用 `.`、筆跡用 `X` 表示。

### Example Input 0

```
10 3
1 5 5
1 3 -1
1 7 100
```

### Example Output 0

```
XXXX.X.XXX
```

### Example Input 1

```
10 2
1 2 6
2 5 100
```

### Example Output 1

```
..XXX.....
```

### Example Input 2

```
10 6
1 1 1
1 4 4
1 7 7
3 3
3 7
3 8
```

### Example Output 2

```
.XXXX..XXX
```

---


## 大小姐想要冷靜
> [name=博傑]

### Description

在某個平靜的午後，大小姐正坐在學生會室裡面整理著文件，想著幾日前與會長在體育倉庫內發生的意外，她的心跳又不由得逐漸加快，臉上也泛起兩片紅暈，隱約又有昏厥之勢。

> 「我這樣子可不行啊...如果又像上次一樣因為心跳過快而送醫了怎麼辦...」

正在她煩惱之際，門外突然傳來了會長的聲音！

> 「大小姐啊...關於奉心季的準備，差不多該上繳企劃給校長了，我們需要找個時間討論一下」  
> 「啊，會、會長，我今天還有急事，我先離開了！」

語畢，大小姐胡亂將文件塞進書包內，慌亂中便奪門而出，逃回家裡了。

回到家中，女僕小姐看到今日大小姐又沒出息的逃回家內，一邊說著自己是不是生了什麼重病云云，心道，「心臟病之後是腦袋出問題了嗎，看來得盡早擬訂對策才行...」

於是，為了避免大小姐又因為這種丟人的理由，跑去醫院請超貴的醫生看病，女僕小姐建議大小姐可以找到自己的 *Pre-Performance Routine*，這是一種運動員用於精神管理的方法，藉由特定的儀式（行為），來令自己精神放鬆，以進入適合比賽之最佳狀態。

期間，他們嘗試了許多方法，像是以下便是一種：

> 任意挑選兩個正整數 $a, b$（其中 $a \le b$），接著計算 $[a, b]$ 這個區間內總共出現了幾個 $1$，重複 $q$ 次

例如我們挑選 $a=1, b=10$，則這個區間內就會有 $2$ 個 $1$，分別出現在 $1$ 跟 $10$ 上面，現在告訴你 $a$ 跟 $b$，請你來計算看看，中間究竟會有幾個 $1$。

### Input

輸入的第一行包含一個正整數 $q$  
接下來有 $q$ 行，每行包含兩個整數，分別為 $a, b$，以一個空格隔開  
保證

- $1 \le q \le 10^3$
- $1 \le a, b \le 2^{30}-1$
- 答案可以存在 32 位整數（i.e., `int`）內

#### Subtasks

|    | Limits |Score |
|:---|:-------|-----:|
| #0 | $a=b, q=1$ | $10$ |
| #1 | $b-a \le 10^4, q \le 10$ | $30$ |
| #2 | $a, b \in \{10^k \| k \in \mathbb{N}\}$ | $30$ |
| #3 | 無其他限制 | $30$ |
| **Total** |  | $100$ |

### Output

對於每組 $a, b$，輸出 $[a, b]$ 區間內總共有幾個數字 $1$ 於一行

### Example Input 0

```
2
5 5
10 10
```

### Example Output 0

```
0
1
```

### Example Input 1

```
3
1 10
1 100
1 1000
```

### Example Output 1

```
2
21
301
```

### Example Input 2

```
3
10086 55688
1000000007 1073741777
20201026 1073741736
```

### Example Output 2

```
28634
136019106
1011818689
```

### Hint

- 本題須注意做法，如果是計算 $[a, b]$ 中每個數字內含的 $1$ 個數再加總，應可得 $40$ 分，可以尋找其他方式加速

---

## Upgrade?  Downgrade in the "Factorio" 
> [name=育辰]

### Description

異星工廠 是 Wube Software 公司所開發的一款冒險沙盒遊戲，遊戲畫面如下圖：
![](https://i.imgur.com/n8pQfn7.jpg)

在遊戲中，你意外墜入未知的星球，因此，我們必須運用星球上所有可運用的資源，想盡辦法逃離這裡！

一般來說，我們會建造生產線，去生產藥水、齒輪和電路板等材料，也可生產出機械手臂，不過...星球上還會有生物襲擊你的地盤！

因此，不僅是生產線的規劃，玩家還會在設施之間擺放砲塔，以保護設施的安全，而每個砲塔都有等級，隨著玩家設施的不同，生物也會進行不等的破壞...

今天，不用考慮設施\
我們著重在砲塔在地圖上的狀況\
你——必須模擬砲塔在地圖上的狀況，包括升級、破壞後的等級狀況之輸出。

起初，輸入會給定地圖所涵蓋畫面的 $\text{row}$，以及 $\text{col}$，接著，給定地圖上的砲塔數量 $n$。

接著一共會有 $\text{row}$ 行輸入
* 每行包括 ($\text{col +1}$)個整數
* 每行前 $\text{col}$ 個數字，若大於 $0$ 表示該格地圖上有砲塔，數值為該砲塔的等級
* 第 $\text{col+1}$ 個數字若為 $1$，則表示「玩家會升級整列砲塔的等級」，若為 $-1$ 則表示「該列砲塔遭到生物破壞。」
* 破壞、升級的程度依照該列砲塔等級之「平均」除以 $2$ 做計算，假設某列為 $\begin{bmatrix} 1 & 5 & 4 & 10 & 0 & 20 \end{bmatrix}$，其平均為 $\frac{(1+5+4+10+20)}{5 \times 2} = 4$ <br>
(**如果平均為小數，則無視小數部分，只取整數，接著再除以$2$，如果此數又是小數，一樣只取整數部分**)
* 承上，因此若該列遭到生物破壞，則每個砲塔等級扣 $4$，最低降至$0$，我們得到了$\begin{bmatrix} 0 & 1 & 0 & 6 & 0 & 16 \end{bmatrix}$，的新的砲塔情況($0$ 則表示該格地圖已遭夷為平地，為草地之意)
* 反之，若玩家進行升級，則每個砲塔等級加 $4$，因此得到$\begin{bmatrix} 5 & 9 & 8 & 14 & 0 & 24 \end{bmatrix}$，若該處為$0$表示為草地，因此無法升級砲塔，但當上頭有砲塔就必須升級。
* 平均是計算「該列砲塔等級平均」，因此非砲塔的地方不列入計算。

### 範例
假設今天輸入為 4 5 8，代表 $\text{row} = 4, \ \text{col} = 5, \ \text{砲塔總數} = 11$\
接著，我們按照下列的數字輸入：

|$\text{row}$||$\text{up/down}$|
|:--|:--|:--|
|$0$|$3\  5\ 7 \ 2 \ 0$|$1$|
|$1$|$0 \ 0 \ 2 \ 8 \ 5$|$-1$|
|$2$|$7 \ 0 \ 1 \ 0 \ 2$|$-1$|
|$3$|$0 \ 0 \ 0 \ 0 \ 1$|$1$|


* $\text{row  1}$：該列全部 升級 $2$ 等
* $\text{row  2}$：該列全部 降級 $2$ 等
* $\text{row  3}$：該列全部 降級 $1$ 等
* $\text{row  4}$：該列全部 升級 $0$ 等

得到：

|$\text{row}$||
|:--|:--|:--|
|$0$|$5\  7\ 9 \ 4 \ 0$|
|$1$|$0 \ 0 \ 0 \ 6 \ 3$|
|$2$|$6 \ 0 \ 0 \ 0 \ 1$|
|$3$|$0 \ 0 \ 0 \ 0 \ 1$|

接著，同學必須「反向輸出」，也就是輸出如下內容：

    1 0 0 0 0
    1 0 0 0 6
    3 6 0 0 0
    0 4 9 7 5

但是！\
你發現自己電腦記憶體太少(假設)\
如果建立二維陣列儲存上述 $20$ 個數字非常浪費空間\
像是 $0$ 是不必儲存的。

什麼！？\
玩家...你沒學過資料結構嗎？\
沒關係！「外星人」博士就來告訴你怎麼做！

---

**<博士>**
> 在資料結構中有這樣的儲存方式：

(下圖為原始輸入的儲存結果)

|$\text{index}$|$\text{row}$|$\text{col}$|$\text{value}$|
|:--|:--|:--|:--|
|0|$4$|$5$|$11$|
|1|$0$|$0$|$3$|
|2|$0$|$1$|$5$|
|3|$0$|$2$|$7$|
|4|$0$|$3$|$2$|
|5|$1$|$2$|$2$|
|6|$1$|$3$|$8$|
|7|$1$|$4$|$5$|
|8|$2$|$0$|$7$|
|9|$2$|$2$|$1$|
|10|$2$|$4$|$2$|
|11|$3$|$4$|$1$|

* 以上的儲存方式，表示了這樣的矩陣：
    $\begin{bmatrix} 3 & 5 & 7 & 2 & 0 \\ 0 & 0 & 2 & 8 & 5 \\ 7 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$
* **在 index = 0 中，row col表示該矩陣之行列，value則表示有多少個非零數。**
* 接著每列都代表非零數其在矩陣的位置狀況。

> 在疏散的矩陣 (sparse matrix) 中(也就是非常多0，只有少數非零數字)，這樣的儲存方式會大大節省需要的儲存空間，按照這樣的儲存方式去做升級、降級，最後再反向輸出(你只需從儲存的結構最後輸出到前面，並記得換行就完成了)。

如上範例，你可以用三個一維陣列儲存之：

```cpp
int Row[value+1] = {4, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3};
int Col[value+1] = {5, 0, 1, 2, 3, 2, 3, 4, 0, 2, 4, 4};
int Value[value+1] = {11, 3, 5, 7, 2, 2, 8, 5, 7, 1, 2, 1};
```

> 我們模擬的是在地圖上每一格的狀況，也許為 0，表示草地，也許有正整數，表示為砲塔的等級，因為一般砲塔在地圖上不會太密集分佈，因此可透過這種方式儲存地圖的資訊，節省所需空間。


#### Subtasks

|    | Limits |Score |
|:---|:-------|-----:|
|#0|$\text{row} = 1$，數字皆為非零，且只會**升級**，砲塔不會被破壞。|$25$|
|#1|$\text{value} \leq 10^4$, 會出現非零數，但只會**升級**，塔不會被破壞。|$35$|
|#2|$\text{value} \leq 10^4$, 會出現非零數。|$25$|
| #3 |$\text{value} \leq 10^6$，其餘部分無限制 | $15$ |
| **Total** |  | $100$ |


### Input
* 起初有一行輸入三個整數，依序為 $\text{row, col, value}$, $\text{value}表砲塔總數$。
* 接著有 $\text{row}$ 行，每行有 $\text{col} + 1$ 個整數，**最後一個數字**代表該列會升級還是被破壞。


#### Limit
* $\text{row, col} > 0$，為正整數
* $\text{value} \geq 0$，為正整數

### Output
* 按題述要求將列作相對應的升級或降級，並且以**相反**的方式輸出，請參考題述，或範例測資。


### Example Input 0
    4 5 0
    0 0 0 0 0 1
    0 0 0 0 0 -1
    0 0 0 0 0 1
    0 0 0 0 0 -1

### Example Output 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0

### Example Input 1
    4 5 11
    3 5 7 2 0 1
    0 0 2 8 5 -1
    7 0 1 0 2 -1
    0 0 0 0 1 1

### Example Output 1
    1 0 0 0 0
    1 0 0 0 6
    3 6 0 0 0
    0 4 9 7 5

### Example Input 2
    2 3 6
    1 2 3 1
    4 5 6 1

### Example Output 2
    8 7 6
    4 3 2


### Example Input 3
    3 4 7
    0 1 7 3 1
    2 0 0 1 1
    3 1 0 0 1


### Example Output 3
    0 0 2 4 
    1 0 0 2
    4 8 2 0

### Example Input 4
    3 4 7
    0 1 7 3 -1
    2 0 0 1 -1
    3 1 0 0 -1

### Example Output 4
    0 0 0 2
    1 0 0 2
    2 6 0 0

### Hint
* 應該會用到三個單維陣列，雙層迴圈處理
* 本題所有子任務使用二維陣列處理都有可能導致記憶體超出，應按照題目敘述以三個一維陣列處理。
* 陣列應該在讀取第一行後，根據 `value` 的數值宣告三個一維陣列(請參考題敘範例程式碼)[言下之意就是**不要先開好固定大小的陣列，而是根據讀入的數值去開相對應的大小**]
* 需要一個 `cur` 變數，紀錄目前在一維陣列中跑到的位置，你也需要一個`record`變數，去儲存該列最開頭在一維陣列中的位置，便可以利用`cur`和`record`去升級、降級。
* 需要一個 `num` 變數，儲存該列有多少非零數字，以及 `sum`變數記錄該列總和，透過這些資訊計算該列砲塔等級平均，也記得要除以2，在除的時候你應該要注意`num=0`的情況會發生除以零此類不應該出現的狀況，會導致`Runtime Error`，須加判斷式處理。
* 以上都是**建議**，本週訴求是考**一維陣列**，本題使用二維陣列寫的話，三個子任務都可能會`Memory Limit Exceeded`或`Runtime Error`導致無法通過。
* 範例測資3：
    * 第一列採取「升級」，因此升級為 $\frac{1+7+3}{3}=3.\bar{6}$，取整數部分得到 $3$，接著再將其除以 $2$，得到$1.5$，取整數部分得到 $1$，因此該列升級 $1$ 等，新的狀況為 `0 2 8 4`
    * 第二列仍採取「升級」，升級幅度為 $\frac{2+1}{2}=1.5$，取整數得 $1$，再將其除以二得到 $0.5$，取整數部分得 $0$，因此該列不用升級，仍為 `2 0 0 1`。
    * 第三列採取「升級」，幅度為 $\frac{3+1}{2} = 2$，除以二得到 $1$，因此該列升級 $1$ 等，得 `4 2 0 0`
    * 最終，你必須將這些數字從最後往前輸出，也就是先將第三列反過來輸出得到 `0 0 2 4`，再將第二列反過來輸出得到 `1 0 0 2`，最後將第一列反過來輸出得到 `4 8 2 0`
* 遊戲相關內容取至：[Link](https://zh.wikipedia.org/wiki/%E5%BC%82%E6%98%9F%E5%B7%A5%E5%8E%82)

> [測資載點](https://drive.google.com/open?id=1r-7Qd63HjPxptv4MheraqWXQwVa2j5Jx&authuser=40771131h%40gapps.ntnu.edu.tw&usp=drive_fs)

---

## [JG專區](https://judgegirl.csie.org/problems/domain/0#5)

## $Mn, Mn + 1, \cdots Mn + M - 1$

### Description

統計有多少整數被 $M$ 除餘 $0$、餘 $1$、$\cdots$、餘 $M - 1$

### Input

第一行包含一個正整數 $N$，接下來 $N$ 行每行都有一個數字，最後一行有一個整數 $M$。  
保證 $1 \le M \le 2 \times 10^5$

### Output

輸出總共有多少個數字可以被寫成 $M \cdot k, M \cdot k + 1, \cdots \text{and} M \cdot k + M - 1$，每個數字一行。

### Sample Input

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

### Sample Output

```
1
2
2
```

### Sample Input

```
10
3
1
4
1
5
9
2
6
5
3
3
```

### Sample Output

```
4
3
3
```

### Hint

- 搬運自 Judge Girl，[原題連結](https://judgegirl.csie.org/problem/0/74)

## Print the Sequence Backward

### Description

寫一隻程式來讀一個正整數 $n$ 和一連串 $n$ 個整數，然後反過來輸出。

### Input

輸入總共有兩行，第一行是一個正整數 $n$，第二行是 $n$ 個整數。

### Output

輸出一行數字，詳見題敘。

### Sample Input

```
5
1 4 8 9 10
```

### Sample Output

```
10 9 8 4 1
```

### Hint

- 搬運自 Judge Girl，[原題連結](https://judgegirl.csie.org/problem/0/14)




