---
tags: 2021CRC
title: 期中社內賽題目
---

<h2 style="text-align:center">注意事項</h2>

本次比賽由於輸入/輸出資料較多，請使用[`scanf`](`scanf`)/[`printf`](https://www.cplusplus.com/reference/cstdio/printf/)或 IO優化(`cin`/`cout`) 來做資料讀取的動作。
請注意不要將`scanf`/`printf`和`std::cin`/`std::cout`混用，並且在使用`std::cin`/`std::cout`時不要使用`std::endl`。

`scanf`/`printf`的範例程式碼:

#include <cstdio>

int main(void) {
    int a, b, c;
    scanf("%d%d", &a, &b);
    c = a+b;
    printf("%d\n", c);
    return 0;
}

IO優化的範例程式碼:

#include <iostream>

int main(void) {
    // IO優化
    std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
    
    int a, b, c;
    std::cin >> a >> b;
    c = a+b;
    std::cout << c << '\n';
}

---

<h2 style="text-align:center"> A. 打招呼 </h2>

<p style="text-align:center"><font size=3>Time limit: 1s, Memory limit: 256Mb</font></p>

歡迎加入附中電算大家庭，剛加入社團的第一件事就是要和大家打招呼阿:D，不用擔心，學長姐們都會很「熱情」的（應該吧），試著輸入一個名字然後跟他說Hello吧

### 格式

**輸入說明：** 輸入一個字串$s \left (|s| \leq 10^6 \right )$，代表你要打招呼的對象
**輸出說明：** 輸出`Hello, s!`

**範例輸入：**

Foxyy

**範例輸出：**

Hello, Foxyy!

---

<h2 style="text-align:center"> B. 瀕臨絕種的猴子社長 </h2>

<p style="text-align:center"><font size=3>Time limit: 1s, Memory limit: 256Mb</font></p>

猴子社長是個即將瀕臨絕種的生物，他非常關心他在其他國家夥伴剩下的數量，畢竟這個稀有種是個非常聽人話而且還會扮女裝取悅大家的生物（誤），你可以幫幫他算算世界中還有幾隻猴子社長嗎？

### 格式

**輸入說明：** 輸入一個整數$n \left ( 1 \leq n \leq 10^6 \right )$，代表有幾個國家，接著輸入$n$個數字$a_i \left (1 \leq i \leq n \right )$，代表第$i$個國家中有$a_i$隻猴子社長 $0 \leq a_i \leq 10^9$
**輸出說明：** 輸出總共有幾隻猴子社長

**範例輸入：**

5 
1 2 3 4 5

**範例輸出：**

15

### 子題
- 子題1 (30%)
$\sum_{i=1}^{n}a_i \leq 2^{31}-1$
- 子題2 (70%)
無特別限制

---

<h2 style="text-align:center"> C. 質數判斷 </h2>

<p style="text-align:center"><font size=3>Time limit: 1s, Memory limit: 256Mb</font></p>

承恩活動長是數資班電神，數學好的他常常仗著自己爆開的能力去欺負別人，但由於只有爆開強，每次遇到要判斷質數的方面總是會難倒他，搞得承恩活動長都很崩潰，你可以幫幫他嗎

### 格式

**輸入說明：** 輸入一個整數$n$
**輸出說明：** 若$n$是質數，輸出`yes`，否則輸出`no`
（$2 \leq n \leq 10^{14}$）

**範例輸入1：**

5

**範例輸出1：**

yes

**範例輸入2：**

16

**範例輸出2：**

no

**範例輸入3：**

48763

**範例輸出3：**

no

### 子題
- 子題1 (30%)
$n \leq 10^8$
- 子題2 (70%)
無特別限制

### 註記
`yes`與`no`的大小寫不影響答案的正確性

---

<h2 style="text-align:center"> D. 宵夜時間 </h2>

<p style="text-align:center"><font size=3>Time limit: 2.5s, Memory limit: 256Mb</font></p>

彥彥小公主副社長喜歡吃東西，尤其是宵夜，導致他的體重一直掉不下來。現在又到了宵夜時間，彥彥又要來吃他最喜歡的宵夜了！

已知桌上有$n$個食物排成一列，從左到右的卡路里含量分別是$a_1, a_2, ..., a_n$，但他吃東西有個怪癖，就是他只喜歡吃**連續**排在一起的食物。為了避免彥彥小公主過胖，你想要詢問$q$次、如果彥彥小公主吃掉位在區間$[l_i, r_i]\left(1 \leq i \leq q\right)$的食物的話，攝取的卡路里會是多少。

### 格式

**輸入說明：**
第一行輸入二個整數$n$和$q$
第二行輸入$n$個數字$a_1, a_2, ..., a_n$
接下來有$q$行，每一行會輸入兩個數字$l_i$以及$r_i$

**輸出說明：**
請對每次詢問輸出彥彥小公主所攝取的的卡路里含量
（$1 \leq n \leq 10^6$，$1 \leq q \leq 10^6$，$1 \leq a_i \leq 10^3$，$1 \leq l_i \leq r_i \leq n, \forall i \in [1,n]$）

**範例輸入：**

5 3
4 8 7 6 3
2 5
1 4
2 2

**範例輸出：**

24
25
8

### 子題
- 子題1 (5%)
$q=1$
- 子題2 (30%)
$q \leq 10^3$
- 子題3 (65%)
無特別限制

---

<h2 style="text-align:center"> E. 保險箱 </h2>

<p style="text-align:center"><font size=3>Time limit: 1s, Memory limit: 256Mb</font></p>

火龍果視錢如命，他把他所有的錢都放在一個保險箱裡面，這個保險箱有一個五位數的密碼，而解開這個鎖有步驟可循

您擁有由 5 位十進制數字組成的保險箱鎖。如果你旋轉某個數字，它會增加一，除了 9 變成 0。

最初，鎖包含數字$X$. 要解鎖保險箱，您必須按順序執行以下操作。

如果位置 1 和 4 上的數字總和大於 10，則將位置 1 上的數字旋轉 3 次，否則將位置 4 上的數字旋轉 8 次。

如果位置 3 和 2 上的數字總和大於 8，則將位置 4 上的數字旋轉 9 次，否則將位置 5 上的數字旋轉 8 次。

如果位置 3 上的數字是奇數，則將位置 3 上的數字旋轉 3 次，否則將位置 3 上的數字旋轉 4 次。

如果位置 5 上的數字大於位置 2 上的數字，則將位置 4 上的數字旋轉 1 次，否則將位置 2 上的數字旋轉 7 次。

如果位置 1 上的數字是奇數，則將位置 1 上的數字旋轉 3 次，否則將位置 3 上的數字旋轉 5 次。

如果位置 4 上的數字是奇數，則將位置 4 上的數字旋轉 7 次，否則將位置 1 上的數字旋轉 9 次。

如果位置 4 上的數字大於位置 1 上的數字，則將位置 4 上的數字旋轉 9 次，否則將位置 4 上的數字旋轉 2 次。

如果位置 1 上的數字大於位置 3 上的數字，則將位置 2 上的數字旋轉 1 次，否則將位置 3 上的數字旋轉 1 次。

如果位置 5 上的數字大於位置 3 上的數字，則將位置 4 上的數字旋轉 5 次，否則將位置 5 上的數字旋轉 8 次。

如果位置 1 和 3 上的數字總和大於 8，則將位置 4 上的數字旋轉 5 次，否則將位置 2 上的數字旋轉 5 次。

如果位置 1 上的數字大於位置 4 上的數字，則將位置 4 上的數字旋轉 3 次，否則將位置 2 上的數字旋轉 3 次。

如果位置 3 和 1 上的數字總和大於 9，則將位置 2 上的數字旋轉 9 次，否則將位置 2 上的數字旋轉 2 次。

如果位置 4 和 3 上的數字總和大於 10，則將位置 4 上的數字旋轉 7 次，否則將位置 5 上的數字旋轉 7 次。

如果位置 3 上的數字大於位置 2 上的數字，則將位置 3 上的數字旋轉 2 次，否則將位置 4 上的數字旋轉 6 次。

如果位置 1 上的數字大於位置 3 上的數字，則將位置 1 上的數字旋轉 9 次，否則將位置 2 上的數字旋轉 9 次。

如果位置 3 上的數字是奇數，則將位置 3 上的數字旋轉 9 次，否則將位置 1 上的數字旋轉 5 次。

如果位置 3 和 5 上的數字總和大於 9，則將位置 3 上的數字旋轉 4 次，否則將位置 3 上的數字旋轉 9 次。

如果位置 3 上的數字大於位置 1 上的數字，則將位置 5 上的數字旋轉 1 次，否則將位置 5 上的數字旋轉 7 次。

如果位置 1 上的數字大於位置 3 上的數字，則將位置 2 上的數字旋轉 9 次，否則將位置 4 上的數字旋轉 6 次。

如果位置 2 和 3 上的數字總和大於 10，則將位置 2 上的數字旋轉 2 次，否則將位置 3 上的數字旋轉 6 次。

但火龍果因為記性太差，常常忘記密碼，你可以幫他解開密碼嗎？

### 格式

**輸入說明：** 輸入一個由五位數組成的數字$X$
**輸出說明：** 操作後的數字

**範例輸入1：**

00000

**範例輸出1：**

51926

**範例輸入2：**

12345

**範例輸出2：**

47782

**範例輸入3：**

48763

**範例輸出3：**

99588

---

<h2 style="text-align:center"> F. Hanoi </h2>

<p style="text-align:center"><font size=3>Time limit: 1s, Memory limit: 256Mb</font></p>

Tony老師最近被課業壓的喘不過氣來QQ，但喜歡動腦的他常常做一些動腦的題目作為休閒之舉，例如數獨啊、文字填空遊戲之類的，最近，Tony老師發現了一個很好玩的遊戲，那就是「河內塔」，遊戲規則如下：

你會有三根柱子分別編號為$1、2、3$，接著會有$n$個套環，分別編號$1、2、...、n-1、n$，開始時套環$i$會在柱子$a_i$的上面，並且每根柱子上的套環都依編號小到大由上到下排列，你的目標就是將每個套環$i$移到柱子$b_i$上，但注意，在操作時編號小的套環一定要在編號大的套環上面。

Tony老師看到這個就傻住了，不知道要如何下手，你可以幫幫他解開謎題嗎

### 格式

**輸入說明：**
第一行輸入一個整數$n$,代表有$n$個套環
第二行輸入$n$個整數$a_1, a_2, ..., a_n$
第三行輸入$n$個整數$b_1, b_2, ..., b_n$
**輸出說明：** 輸出最少步數的整個移動過程
（$3 \leq n \leq 20$）

**範例輸入1：**

3
1 1 1
3 3 3

**範例輸出1：**

Ring 1 from 1 to 3
Ring 2 from 1 to 2
Ring 1 from 3 to 2
Ring 3 from 1 to 3
Ring 1 from 2 to 1
Ring 2 from 2 to 3
Ring 1 from 1 to 3

**範例輸入2：**

3
2 3 1
2 2 1

**範例輸出2：**

Ring 1 from 2 to 1
Ring 2 from 3 to 2
Ring 1 from 1 to 2

### 子題
- 子題1 (25%)
$\forall i \in [1, n], a_i=1, b_i=3$
- 子題2 (30%)
$\forall i \in [1, n], a_i\in[1,3], b_i=3$
- 子題3 (45%)
無特別限制