<div style="display: flex; justify-content: space-between;">
<a href="https://hackmd.io/@vientoligero/S1TVZchL6" style="margin-left: auto; color: grey; font-size: 14px;">下一頁 a017~</a>
</div>
# zerojudge基礎題庫題解 a001~a015
## 傳送門
* [a001 哈囉](#a001)
* [a002 簡單加法](#a002)
* [a003 兩光法師占卜術](#a003)
* [a004 文文的求婚](#a004)
* [a005 Eva 的回家作業](#a005)
* [a006 一元二次方程式](#a006)
* [a009 解碼器](#a009)
* [a010 因數分解](#a010)
* [a013 羅馬數字](#a013)
* [a015 矩陣的翻轉](#a015)
<a id=a001></a>
## zerojudge-a001 哈囉
### [題目](https://zerojudge.tw/ShowProblem?problemid=a001)
:::info
> 內容
學習所有程式語言的第一個練習題
請寫一個程式，可以讀入指定的字串，並且輸出指定的字串。
比如：輸入字串 "world", 則請輸出 "hello, world"
>輸入說明
輸入總共一行，內含一組文字
>輸出說明
輸出題目指定的文字。
> 標籤
基本輸入輸出
:::
### 範例輸入&輸出
:::info
> 範例輸入 #1
world
> 範例輸出 #1
hello, world
>範例輸入 #2
C++
>範例輸出 #2
hello, C++
>範例輸入 #3
Taiwan
>範例輸出 #3
hello, Taiwan
:::
### 題解
:::warning
讀入字串後, 加上"hello, "輸出
:::
### Python
> 程式碼
```python=
#處理輸入
s = input()
#依題意輸出
print("hello,", s)
```
_註1: ```print()```輸出多個東西時(Eg: `print(1, 2, 3, 4, 5`)， 每個東西之間會用空白(` `)隔開。_
_註2: 註1說的東西其實只是預設啦，有興趣的可以上網查查看。`print()`裡面可以放`, sep=""`來改變`print()`輸出多個東西時，要用甚麼分隔，預設就是空白`" "`)_
### C
> 程式碼
```c=
#include <stdio.h>
int main(){
// 處理輸入
char s[100]; scanf("%s", s);
// 依題意輸出
printf("hello, %s", s);
return 0;
}
```
### C++
> 程式碼
```cpp=1
//引入必要header
#include <iostream>
#include <string>
//讓之後的程式不用加std::
using namespace std;
int main(){
//處理輸入
string s; cin>>s;
//依題意輸出
cout << "hello, " << s;
return 0;
}
```
### Java
> 程式碼
```java=1
//導入處理輸入的Scanner
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//處理輸入
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
//依題意輸出
System.out.println("hello, " + s);
//關閉Scanner物件
scanner.close();
}
}
```
###### 感謝[M_SQRT](https://zerojudge.tw/UserStatistic?id=195452)勘誤。「對象」(Object)是對岸的說法，在台灣應翻譯為「物件」
<a id=a002></a>
## zerojudge-a002 簡易加法
### [題目](https://zerojudge.tw/ShowProblem?problemid=a002)
:::info
> 內容
請寫一個程式，讀入兩個數字，並求出它們的和。
>輸入說明
每組輸入共一行，內含有兩個整數a, b，以空白隔開，a, b絕對值皆小於$10^6$。
>輸出說明
對於每組輸入，輸出該兩整數的和。
> 標籤
基本輸入輸出
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
5 10
>範例輸出 #1
15
>範例輸入 #2
1 2
>範例輸出 #2
3
:::
### 題解
:::warning
讀取兩個整數後，將其相加並輸出
:::
### Python
> 程式碼
```python=
#讀取輸入
a, b = map(int, input().split())
#輸出
print(a+b)
```
_註1: `.split()`能將字串依照特定字串分割(預設是空白`' '`)，並且回傳一個list_
_註2: `map(函數, 序列)`可以將一序列中的每個元素做某個函式，並回傳一個map物件(迭代器)，裡面放執行完的結果，通常外面會包一個`list()`把它轉成陣列。_
### C
> 程式碼
```c=
#include <stdio.h>
int main(){
//處理輸入
int a, b; scanf("%d %d", &a, &b);
//輸出答案
printf("%d", a+b);
return 0;
}
```
### C++
> 程式碼
```cpp=1
#include <iostream>
using namespace std;
int main(){
//處理輸入
int a, b; cin >> a >> b;
//輸出答案
cout << a+b;
return 0;
}
```
### Java
> 程式碼
```java=1
import java.util.Scanner;
public class Main{
public static void main(String[] args){
//處理輸入
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
//輸出答案
System.out.println(a+b);
scanner.close();
}
}
```
<a id=a003></a>
## zerojudge-a003 兩光法師占卜術
### [題目](https://zerojudge.tw/ShowProblem?problemid=a003)
:::info
> 內容
兩光法師時常替人占卜，由於他算得又快有便宜，因此生意源源不絕，時常大排長龍，他想算 得更快一點，因此找了你這位電腦高手幫他用電腦來加快算命的速度。
他的占卜規則很簡單，規則是這樣的，輸入一個日期，然後依照下面的公式：
M=月
D=日
S=(M*2+D)%3
得到 S 的值，再依照 S 的值從 0 到 2 分別給與 普通、吉、大吉 等三種不同的運勢
>輸入說明
輸入資料共一行，包含兩個整數，分別為月份及日期
>輸出說明
運勢
> 標籤
if-else
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
1 1
>範例輸出 #1
普通
> 範例輸入 #2
1 2
>範例輸出 #2
吉
:::
### 題解
:::warning
算出S後，用if-else判斷S的值並輸出對應答案
:::
### Python
> 程式碼 (if-else版本)
```python=
#讀入資料 map, split用法請見a002
m, d = map(int, input().split())
#算出s的值
s = (m*2+d)%3
#判斷s是否為0, 1, or 2 ，條件成立時輸出對應答案
if s==0:
print("普通")
elif s==1:
print("吉")
else: #整數%3 只有0, 1, 2三種結果。 會跑到else的情況只有s==2，就不多加判斷了
print("大吉")
```
> 程式碼 (match-case版本) (欣賞一下就好)
```python=1
m, d = map(int, input().split())
s = (m*2 + d) % 3
match s:
case 0:
print("普通")
case 1:
print("吉")
case 2:
print("大吉")
```
_註1: Python從3.10版本才開始有```match-case```，用法類似C++，Java的```switch-case```。目前zerojudge不支援_
### C
>程式碼 (if-else 版)
``` c=
#include <stdio.h>
int main() {
// 讀取輸入
int m, d;
scanf("%d %d", &m, &d);
// 算出s的數值
int s = (2 * m + d) % 3;
// 判斷s的值並輸出對應答案
if (s == 0) {
printf("普通\n");
} else if (s == 1) {
printf("吉\n");
} else { // 整數%3只有0, 1, 2三種結果，會跑到else的情況只有s==2
printf("大吉\n");
}
return 0;
}
```
> 程式碼 (switch-case版)
```c=
#include <stdio.h>
int main() {
// 讀取輸入
int m, d;
scanf("%d %d", &m, &d);
// 算出s的數值
int s = (2 * m + d) % 3;
// 判斷s的值並輸出對應答案
switch (s) {
case 0:
printf("普通\n");
break;
case 1:
printf("吉\n");
break;
case 2:
printf("大吉\n");
break;
}
return 0;
}
```
_註1: 每個case的內容結束完後都要加`break`來中止整個switch的區塊(除非要特殊運用case的機制)，不然s==0(case 0成立)又沒有加上`break`時case 0 1 2的內容都會被執行，也就是會輸出`普通吉大吉`_
### C++
> 程式碼 (if-else版)
```cpp=1
#include <iostream>
using namespace std;
int main(){
//讀取輸入
int m, d;
cin >> m >> d;
//算出s的數值
int s = (2*m+d)%3;
//判斷s是否為0, 1, or 2 ，條件成立時輸出對應答案
if (s==0){
cout << "普通";
} else if(s==1){
cout << "吉";
} else{ //整數%3 只有0, 1, 2三種結果。 會跑到else的情況只有s==2，就不多加判斷了
cout << "大吉";
}
}
```
> 程式碼 (switch-case版)
```cpp=1
#include <iostream>
using namespace std;
int main(){
//讀取輸入
int m, d;
cin >> m >> d;
//算出s的數值
int s = (2*m+d)%3;
//判斷s是否為0, 1, or 2 ，條件成立時輸出對應答案
switch (s){
case 0:
cout << "普通";
break;
case 1:
cout << "吉";
break;
case 2:
cout << "大吉";
break;
}
}
```
_註1: 每個case的內容結束完後都要加`break`來中止整個switch的區塊(除非要特殊運用case的機制)，不然s==0(case 0成立)又沒有加上`break`時case 0 1 2的內容都會被執行，也就是會輸出`普通吉大吉`_
### Java
> 程式碼 (if-else版)
```java=1
import java.util.Scanner;
public class Main{
public static void main(String[] args){
//處理輸入
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
//算出s的值
int s = (2*a+b)%3;
//#判斷s是否為0, 1, or 2 ，條件成立時輸出對應答案
if (s==0){
System.out.println("普通");
} else if (s==1){
System.out.println("吉");
} else{ //整數%3 只有0, 1, 2三種結果。 會跑到else的情況只有s==2，就不多加判斷了
System.out.println("大吉");
}
}
}
```
> 程式碼 (switch-case版)
```java=1
import java.util.Scanner;
public class Main{
public static void main(String[] args){
//處理輸入
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
//算出s的值
int s = (2*a+b)%3;
//#判斷s是否為0, 1, or 2 ，條件成立時輸出對應答案
switch(s){
case 0:
System.out.println("普通");
break;
case 1:
System.out.println("吉");
break;
case 2:
System.out.println("大吉");
break;
}
}
}
```
*_註1: 每個case的內容結束完後都要加`break`來中止整個switch的區塊(除非要特殊運用case的機制)，不然s==0(case 0成立)又沒有加上`break`時case 0 1 2的內容都會被執行，也就是會輸出`普通\n吉\n大吉`_
<a id=a004></a>
## zerojudge-a004 文文的求婚
### [題目](https://zerojudge.tw/ShowProblem?problemid=a004)
:::info
> 內容
文文為即將出國的珊珊送行，由於珊珊不喜歡別人給文文的那個綽號，意思就是嘲笑文文不夠 聰明，但珊珊沒把握那個綽號是不是事實，所以珊珊決定考驗文文，於是告訴文文說，如果你能在 我回國之前回答我生日那年是不是閏年，則等她回國後就答應他的求婚。文文抓抓腦袋想不出來， 於是決定讓最擅長做運算的電腦來幫忙。
>輸入說明
輸入有若干行直到 EOF 結束，每行包含一個整數代表年份
>輸出說明
閏年 或 平年
> 標籤
EOF
if-else
:::
### 範例輸入&輸出
:::info
> 範例輸入 #1
1977
1980
> 範例輸出 #1
平年
閏年
:::
<a id=a004-1></a>
### 題解
:::warning
第一條路:判斷閏年
* 閏年條件: ((能被4整除)`and`(不能被100整除)) `or` (能被400整除)
第二條路:判斷平年
* 平年條件: ((不能被4整除) `or` (能被100整除)) `and` (不能被400整除)
再配上EOF輸入輸出處理即可
:::
### EOF處理方法
:::danger
1. #### Python
* way1: `while true` + `try-except`
* **way2:** 用`sys.stdin`回傳標準輸入流的內容
2. #### C
* **way1:** `while(scanf(~~) != EOF)` scanf如果讀到檔案尾部(`End-Of-File`)會回傳`EOF`
* way2: `while(scanf(~~) == [a number])` scanf如果有讀到東西會回傳它讀取的數量
3. #### C++
* **way1:** ```while(cin>>inp)``` cin如果沒有抓到東西會回傳`false`
* way2: 用 `cin.eof()`判斷還有沒有輸入
4. #### Java
* **way1:** 用 `scanner.hasNext()`判斷還有沒有輸入
_註1:實際的運用在底下程式碼有_
_註2:粗體表示建議的_
:::
### Python
> 程式碼 (try-except版)
```python=1
while True:
try:
#讀取輸入
n = int(input())
#判斷並輸出對應答案
if ((n%4==0) and (n%100!=0)) or (n%400==0):
print("閏年")
else:
print("平年")
except EOFError:
break #如果沒輸入了，就終止整個while迴圈
```
_註1: `try-except-finally`用法: 運行程式進入`try-except-finally`時，程式會先執行`try`的內容，這時:_
* _**如果有出錯**：會進入`except`的內容 (except後可以加上各種錯誤，讓各種不同的錯誤發生時，跑進對應的excpet內；也可以不加，這樣各種不同的錯誤都會跑到同一個`expect`裡面)_
* _**如果沒有出錯**：會跑完`try`_
_`try` `except`跑完後，會進入`finally`內，最後結束整個`try-except-finally`_
***簡單來說: 如果try內有發生錯誤就會跑 `try`(出錯前的程式部分)-`except`-`finally` 沒有出錯就會跑`try`-`finally`***
> 程式碼 (sys.stdin版)
```python=1
import sys
#用for迴圈一一讀取標準輸入流的內容，讀完就跳出for迴圈，跳出程式
for inp in sys.stdin:
inp = int(inp) #str-->int
#判斷並輸出對應答案
if ((inp%4==0) and (inp%100!=0)) or (inp%400==0):
print("閏年")
else:
print("平年")
```
_註1: sys.stdin 會回傳標準輸入流的內容。使用`for-loop`迭代時，通常後面會加上`inp = inp.strip()`來去掉不需要的換行符號和空白，只是在此程式中因為會把inp轉換成`int`來處理，就沒加了_
### C
> 程式碼
```c=
#include <stdio.h>
int main() {
int n;
while (scanf("%d", &n) != EOF) { //處理EOF部分: 如果scanf沒有抓到東西 會回傳EOF
// 這裡使用判斷閏年的 if-else
if (((n % 4 == 0) && (n % 100 != 0)) || (n % 400 == 0)) {
printf("閏年\n");
} else {
printf("平年\n");
}
}
return 0;
}
```
### C++
> 程式碼 ( while(cin>>inp) 版)
```cpp=1
#include <iostream>
using namespace std;
int main(){
int n;
while (cin>>n){ //處理EOF部分: 如果cin沒有抓到東西 會回傳false, while迴圈就會終止
//這裡使用判斷閏年的if-else
if (((n%4==0) && (n%100!=0)) || (n%400==0)){
cout << "閏年" << endl;
}else{
cout << "平年" << endl;
}
}
return 0;
}
```
> 程式碼 ( cin.eof() 版)(沒很建議，看看就好)
```cpp=1
#include <iostream>
using namespace std;
int main(){
int n;
while (true){
cin >> n;
//處理EOF部分:如果輸入流裡面沒資料了(若第11行的cin沒抓到東西)會break掉while迴圈
if (cin.eof()){
break;
}
if (((n%4==0) && (n%100!=0)) || (n%400==0)){
cout << "閏年" << endl;
}else{
cout << "平年" << endl;
}
}
return 0;
}
```
_註1: `cin.eof()`:只要在最近一次cin達到輸入流尾端，`cin.eof()`就會返回`true`。消除方法是使用`cin.clear()`(把cin中的eofbit重置)_
_註2: 這個方法真的蠻爛的。很難應付許多情況(例如:明明變數是`int`結果使用者輸入`string`之類的)。 如果要用`while-true`+`cin`時，大多會多加上`cin.fail()`來判斷使用者輸入有沒有合乎預期 (當然，zerojudge的題目會說清楚輸入資料的形式)_
### Java
> 程式碼
```java=1
import java.util.Scanner;
public class JAVA{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n;
//用scanner.hasNext()判斷輸入流中還有沒有資料
while (scanner.hasNext()){
n = scanner.nextInt();
//這裡是用判斷閏年的if-else
if (((n%4==0) && (n%100!=0)) || (n%400==0)){
System.out.println("閏年");
}else{
System.out.println("平年");
}
}
}
}
```
<a id=a005></a>
## zerojudge-a005 Eva 的回家作業
### [題目](https://zerojudge.tw/ShowProblem?problemid=a005)
:::info
> 內容
Eva的家庭作業裏有很多數列填空練習。填空練習的要求是：已知數列的前四項，填出第五項。因 為已經知道這些數列只可能是等差或等比數列，她決定寫一個程式來完成這些練習。
>輸入說明
>
第一行是數列的數目t（0 <= t <= 20）。 以下每行均包含四個整數，表示數列的前四項。 約定數列的前五項均為不大於$10^5$的自然數，等比數列的比值也是自然數。
>輸出說明
對輸入的每個數列，輸出它的前五項。
> 標籤
(o_ _)o. o(´д｀o).想不到
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
2
1 2 3 4
1 2 4 8
>範例輸出 #1
1 2 3 4 5
1 2 4 8 16
:::
### 題解
:::warning
由前三項判斷出是等差或是等比數列，再算出第五項
:::
### Python
>程式說明
:::success
針對每一筆資料，用if判斷出數列是否為等差($a_3-a_2==a_2-a_1$)
如果是等差:
$a_5=a_4+d$ ($d$ : 公差 = $a_2-a_1$)
如果是等比:
$a_5=a_4*r$ ($r$ : 公比 = $\dfrac{a_2}{a_1}$)
下面的程式碼因為python的list是從0開始的，所以第一項記做`p[0]`, 第二項記做`p[1]`...
:::
> 程式碼
```python=
n = int(input())
for _ in range(n):
p = list(map(int, input().split()))
if (p[1]-p[0] == p[2]-p[1]): #True:=>是等差
ans = p[3] + (p[3]-p[2]) #p[4] = p[3]+d
else:
ans = p[3] * (p[3]//p[2]) #p[4] = p[3]*r
print(p[0], p[1], p[2], p[3], ans) #亦可寫作print(*p, ans)
```
### C
>程式說明
:::success
針對每一筆資料，用if判斷出數列是否為等差($a_3-a_2==a_2-a_1$)
如果是等差:
$a_5=a_4+d$ ($d$ : 公差 = $a_2-a_1$)
如果是等比:
$a_5=a_4*r$ ($r$ : 公比 = $\dfrac{a_2}{a_1}$)
下面的程式碼因為c的array是從0開始的，所以第一項記做`p[0]`, 第二項記做`p[1]`...
:::
> 程式碼
```c=1
#include <stdio.h>
int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; i++) {
int p[5]; // 宣告一個大小為 5 的陣列
scanf("%d %d %d %d", &p[0], &p[1], &p[2], &p[3]);
if (p[1]-p[0] == p[2]-p[1]) { // true ->是等差
p[4] = p[3] + (p[3]-p[2]); //p[4] = p[3] + d
} else { // 等比
p[4] = p[3] * (p[3]/p[2]); //p[4] = p[3] * r
}
printf("%d %d %d %d %d\n", p[0], p[1], p[2], p[3], p[4]);
}
return 0;
}
```
### C++
> 程式說明
:::success
針對每一筆資料，用if判斷出數列是否為等差($a_3-a_2==a_2-a_1$)
如果是等差:
$a_5=a_4+d$ ($d$ : 公差 = $a_2-a_1$)
如果是等比:
$a_5=a_4*r$ ($r$ : 公比 = $\dfrac{a_2}{a_1}$)
下面的程式碼因為C++的array是從0開始的，所以第一項記做`p[0]`, 第二項記做`p[1]`...
:::
> 程式碼
```cpp=1
#include <iostream>
using namespace std;
int main(){
int n; cin>>n;
for (int i=0; i<n; i++){
int p[5]; //宣告一個大小為5的陣列
cin >> p[0] >> p[1] >> p[2] >> p[3];
if (p[1]-p[0] == p[2]-p[1]){ //true:=>是等差
p[4] = p[3] + (p[3]-p[2]); //p[4] = p[3]+d
} else{
p[4] = p[3] * (p[3]/p[2]); //p[4] = p[3]*r
}
cout << p[0] << ' ' << p[1] << ' '
<< p[2] << ' ' << p[3] << ' '
<< p[4] << endl;
}
return 0;
}
```
### Java
>程式說明
:::success
針對每一筆資料，用if判斷出數列是否為等差($a_3-a_2==a_2-a_1$)
如果是等差:
$a_5=a_4+d$ ($d$ : 公差 = $a_2-a_1$)
如果是等比:
$a_5=a_4*r$ ($r$ : 公比 = $\dfrac{a_2}{a_1}$)
下面的程式碼因為Java的array是從0開始的，所以第一項記做`p[0]`, 第二項記做`p[1]`...
:::
> 程式碼
```java=1
import java.util.Scanner;
public class JAVA{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i=0; i<n; i++){
int[] p = new int[5]; // 宣告一個大小為 5 的陣列
//讀取測資
for (int j=0; j<4; j++){
p[j] = scanner.nextInt();
}
if (p[1]-p[0] == p[2]-p[1]) { // true=>等差
p[4] = p[3] + (p[2]-p[1]); //p[4] = p[3]+d
} else {
p[4] = p[3] * (p[2]/p[1]); //p[4] = p[3]*r
}
//輸出答案
for (int j=0; j<5; j++) {
System.out.print(p[j] + " ");
}
System.out.println(); //換行
}
scanner.close();
}
}
```
_註1:第24行用for迴圈輸出答案只是因為全部寫出來有點長~_
<a id=a006></a>
## zerojudge-a006 一元二次方程式
### [題目](https://zerojudge.tw/ShowProblem?problemid=a006)
:::info
> 內容
求一元二次方程式 $ax^2+bx+c=0$ 的根
>輸入說明
每組輸入共一行，內含三個整數 a, b, c 以空白隔開。
>輸出說明
Two different roots x1=?? , x2=??
Two same roots x=??
No real root
PS: 答案均為整數，若有兩個根則大者在前
> 標籤
算數學
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
1 3 -10
>範例輸出 #1
Two different roots x1=2 , x2=-5
>範例輸入 #2
1 0 0
>範例輸出 #2
Two same roots x=0
>範例輸入 #3
1 1 1
>範例輸出 #3
No real root
:::
### 題解
:::warning
先算出判別式，再根據判別式的結果輸出答案
:::
### 二元一次方程式公式
:::warning
一元二次方程式$ax^2+bx+c=0$的~
**公式解**: $x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$
**判別式**: $\Delta = b^2 - 4ac$
如果判別式~
$\Delta > 0$ =>有兩個不同的實根 $\frac{-b + \sqrt{\Delta}}{2a}$ $\frac{-b - \sqrt{\Delta}}{2a}$
$\Delta = 0$ =>有兩個一樣的實根 $\frac{-b}{2a}$
$\Delta < 0$ =>沒有實根
:::
### 各語言開根號方法
:::danger
1. #### Python
* way1: `math.sqrt(a)` = a開2次方根的値 (= $\sqrt{a}$)，a不能是負數
* **way2**: `a**(1/x)` = a開x次方根的値 (= $a^\frac{1}{x}$ = $\sqrt[x]{a}$)
_註1: 此兩種方法的回傳型態都是float_
_註2: way1需要`import math`_
2. #### C
* way1: `sqrt(a)` = a開2次方根的値 (= $\sqrt{a}$)，a不能是負數
* **way2**: `pow(a, 1.0/x)` = a開x次方根的値 (= $a^\frac{1}{x}$ = $\sqrt[x]{a}$)
_註1: 此兩種方法的回傳型態都是double_
_註2: 此兩種方法都要`#include<math.h>`_
_註3: way2不能寫成`pow(a, 1/x)`，不然編譯器會把1/x當成int而砍掉小數點_
3. #### C++
* way1: `std::sqrt(a)` = a開2次方根的値 (= $\sqrt{a}$)，a不能是負數
* **way2**: `std::pow(a, 1.0/x)` = a開x次方根的値 (= $a^\frac{1}{x}$ = $\sqrt[x]{a}$)
_註1: 此兩種方法的回傳型態都是double_
_註2: 此兩種方法都要`#include<cmath>`_
_註3: way2不能寫成`std::pow(a, 1/x)`，不然編譯器會把1/x當成int而砍掉小數點_
4. #### Java
* way1: `Math.sqrt(a)` = a開2次方根的値 (= $\sqrt{a}$)，a不能是負數
* **way2**: `Math.pow(a, 1.0/x)` = a開x次方根的値 (= $a^\frac{1}{x}$ = $\sqrt[x]{a}$)
_註1: 此兩種方法的回傳型態都是double_
_註2: way2不能寫成`Math.pow(a, 1/x)`，不然編譯器會把1/x當成int而砍掉小數點_
:::
### Python
> 程式碼
```python=
import math
a, b, c = map(int, input().split())
delta = b**2 - 4*a*c
if delta==0:
root = -b//(2*a)
print(f"Two same roots x={root}")
elif delta>0:
root1 = int( ( -b+math.sqrt(delta) )/(2*a) )
root2 = int( ( -b-math.sqrt(delta) )/(2*a) )
print(f"Two different roots x1={root1} , x2={root2}")
else: #delta<0
print("No real root")
```
_註1: 第8行: 題目有保證答案是正整數且不能輸出小數點，所以用`//`而非`/`_
_註2: 第12, 13行: 理由同上，所以答案用`int()`包起來去除小數點_
### C
> 程式碼
```c=
#include <stdio.h>
#include <math.h>
int main() {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
int delta = pow(b, 2) - 4 * a * c;
if (delta == 0) {
int root = -b / (2 * a);
printf("Two same roots x=%d\n", root);
} else if (delta > 0) {
int root1 = (int)(-b + sqrt(delta)) / (2 * a);
int root2 = (int)(-b - sqrt(delta)) / (2 * a);
printf("Two different roots x1=%d , x2=%d\n", root1, root2);
} else { //delta<0
printf("No real root\n");
}
return 0;
}
```
### C++
> 程式碼
```cpp=1
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int a, b, c; cin>>a>>b>>c;
int delta = pow(b, 2) - 4*a*c;
if (delta==0){
int root = -b / (2*a);
cout << "Two same roots x=" << root;
}else if(delta>0){
int root1 = ( -b+sqrt(delta) ) / (2*a);
int root2 = ( -b-sqrt(delta) ) / (2*a);
cout << "Two different roots x1=" << root1 << " , x2=" << root2;
}else{ //delta<0
cout << "No real root";
}
return 0;
}
```
_註1: 第13, 17, 18行會拿int去存答案是因為題目有保證答案會是整數_
### Java
> 程式碼
```java=1
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
int c = scanner.nextInt();
int delta = (int) Math.pow(b, 2) - 4*a*c;
if (delta==0){
int root = -b / (2*a);
System.out.println("Two same roots x="+root);
}else if(delta>0){
int root1 = (int)( -b+Math.sqrt(delta) ) / (2*a);
int root2 = (int)( -b-Math.sqrt(delta) ) / (2*a);
System.out.println("Two different roots x1="+root1+" , x2="+root2);
}else{ //delta<0
System.out.println("No real root");
}
scanner.close();
}
}
```
_註1: 第14, 18, 19行會拿int去存答案是因為題目有保證答案會是整數_
_註2: 第18, 19行: 拿int去存還可以順便去掉小數點(4.0-->4)(題目規定的)_
_註3: **顯式轉換**(英文: Explicit Casting)與**隱式轉換**(英文: Implicit Casting)_
* _**顯示轉換**:把一個較大的資料型態給比較小的資料型態時，要用顯示轉換，即在待轉換的變數前面加上`( 想要轉成的資料型態 )`，要小心這樣可能導致精度降低或是溢位_
* _**隱式轉換**:把一個較小的資料型態給比較大的資料型態時，Java會自動轉換其資料型態，所以甚麼都不用做\_(:3 」∠ )\__
* _**資料型態大小**: `double`>`float`>`long`>`int`>`short`>`byte`_
_因此~第11, 18, 19行因為是`double`-->`int`，要使用顯示轉換，所以在待轉換的數值前面加上`(int)`_
<a id=a009></a>
## zerojudge-a009 解碼器
### [題目](https://zerojudge.tw/ShowProblem?problemid=a009)
:::info
在密碼學裡面有一種很簡單的加密方式，就是把明碼的每個字元加上某一個整數K而得到密碼的字元（明碼及密碼字元一定都在ASCII碼中可列印的範圍內）。例如若K=2，那麼apple經過加密後就變成crrng了。解密則是反過來做。這個問題是給你一個密碼字串，請你依照上述的解密方式輸出明碼。
至於在本任務中K到底是多少，請自行參照Sample Input及Sample Output推出來吧！相當簡單的。
>輸入說明
輸入共一行，每行含有1個字串，就是需要解密的明碼。
>輸出說明
對每一測試資料，請輸出解密後的密碼。
> 標籤
字元處理
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
>範例輸出 #1
*CDC is the trademark of the Control Data Corporation.
>範例輸入 #2
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
> 範例輸出 #2
*IBM is a trademark of the International Business Machine Corporation.
:::
### 題解
:::warning
從範例輸入輸出照到規律，在寫程式時按照那個規律把每一筆輸入解密成原文
:::spoiler 規律
把密文的每一個字往前移7個就是原文了
:::
### Python
> 程式碼
```python=
s = input()
decrypt = ""
for char in s:
trans = chr( ord(char)-7 ) #把每個字元抓出來轉換
decrypt = decrypt + trans #把轉換好的字元和已經轉換的字串組合起來
print(decrypt)
```
_註1: python字元與ASCII的轉換: `chr(n)`能回傳ASCLL値`n`所對應的字元(回傳`str`)；`ord(s)`能回傳字元`s`所對應的ASCII値(回傳`int`) (ps: 字元在python中就是只有一個字的字串)_
### C
> 程式碼
```c=
#include <stdio.h>
int main() {
char s[1000];
scanf("%s", s);
//遍歷s，把s中的每一個字元抓出來-7
for (int i = 0; s[i] != '\0'; i++) {
s[i] -= 7;
}
printf("%s\n", s);
return 0;
}
```
_註1: C要改變字元的ASCII(往前往後多少個位置)，直接把它加上一個整數即可 (char會被自動轉換成int)_
### C++
> 程式碼
```cpp=1
#include <iostream>
#include <string>
using namespace std;
int main(){
string s; cin>>s;
//遍歷s，把s中的每一個字元抓出來-7
for (char &c: s){
c-=7;
}
cout << s;
}
```
_註1: C\+\+要改變字元的ASCII(往前往後多少個位置)，直接把它加上一個整數即可 (char會被自動轉換成int)_
_註2: C++的**引用變數**: 在11行的`char &c`中，宣告的c是一個引用變數。他在遍歷s時，會和 s 中的字元共用一塊記憶體(也可以說兩個東西指向同一塊記憶體)。因此，當改變c的値的時候，s中的字元也會改變，這樣就可以直接修改 s 的內容了。_
### Java
> 程式碼
```java=1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
char[] chars = s.toCharArray(); //String --> char[]
//遍歷chars，把每一個元素都-7
for (int i = 0; i < chars.length; i++) {
chars[i] = (char)(chars[i] - 7);
}
String decrypt = new String(chars);//char[] --> String
System.out.println(decrypt);
}
}
```
_註1: Java要要改變字元的ASCII(往前往後多少個位置)，直接把它加上一個整數即可 (char會變成int與int相加)。要注意`chars[i]-7`(上面第10行做舉例)是一個int，要存進char遍數時要顯示轉換`(char)~~~`_
<a id=a010></a>
## zerojudge-a010 因數分解
### [題目](https://zerojudge.tw/ShowProblem?problemid=a010)
:::info
> 內容
各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。
因數分解就是把一個數字，切分為數個質數的乘積，如 12=2^2 * 3
其中, 次方的符號以 ^ 來表示
>輸入說明
輸入共一行。每行包含一個整數，符合 大於1 且 小於等於 100000000
>輸出說明
針對每一行輸入整數輸出一個因數分解字串
> 標籤
╮(￣▽￣)╭
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
20
>範例輸出 #1
2^2 * 5
>範例輸入 #2
17
>範例輸出 #2
17
>範例輸入 #3
999997
>範例輸出 #3
757 * 1321
:::
### 題解
:::warning
這題要處理的東西大概可以分成兩個部分
#### Part1: 把數字分解
* 這個部分比較好想。可以使用最簡單(也最暴力)的方法——試除法(英文: Trial Division)。 具體的做法是從2開始往上除，除到$\sqrt{n}$為止。 (這樣好像沒有很清楚... 請參考[中文的維基百科](https://zh.wikipedia.org/zh-tw/%E8%AF%95%E9%99%A4%E6%B3%95)、[英文的維基百科(詳細一點)](https://en.wikipedia.org/wiki/Trial_division)和底下的流程圖~)
正常試除法: 如上圖做法一直除到 $p >$$\sqrt{待分解的數}$ 之後。`所有除過p的數`和`除完還有剩的n`乘起來就是該數的質因數分解
但是~ 用上面的寫法實在是太麻煩了。考量到n最大只有到100000000。直接硬除除到`n==1`也是可以。雖然效率一定比較差，但是不差那一點啦d(\`･∀･)b
#### Part2: 把答案印出
* 要印出答案的方法有很多~ 找到一個質因數就輸出一次，用**映射(mapping)**(Java和C++的map, Python的dict) 或是**陣列**儲存答案最後後一次輸出等等。就看個人喜好。
:::
### Python
>流程 (偷懶版)
:::success
#### Part1 分解:
按照上面題解的流程圖分解到目標數字剩下1為止(即分解完了)，並把答案存入`result陣列`中
#### Part2 印出答案:
把裡面放tuple的`result陣列`中的元素一一取出，轉換成string後存入另一個陣列`ans` (轉換方法見程式碼)。最後把所有string連接起來印出
:::
> 程式說明 (偷懶版)
```python=
n = int(input())
#part1: 把數字分解
target = n #待試除的數字
p = 2
result = []
while target!=1:
times = 0 #紀錄除了幾次
while target%p ==0: #除到不能再除為止
times+=1
target //= p
if times==0: #True=>沒除到=>非質因數
pass
else:
result.append( (p, times) )
p += 1
#part2-1: 處理答案
ans = []
for base, power in result:
if power==1:
ans.append(str(base)) #Eg: result中的(2, 1)到ans中會變成'2'
else:
ans.append(f"{base}^{power}") #Eg: result中的(3, 5)到ans中會變成'3^5'
#part2-2: 輸出答案
print(" * ".join(ans))
```
_註1: **`string.join(iterable object)`的功能**: `A.join(B)` 可以把`B陣列(或是任何可以迭代的物件)中的所有元素`用`A字串`接起來，最後回傳一個字串。 例如`" ".join(['a', 'b', 'c'])`會回傳字串`a b c`。_
_**注意:** 上面的B陣列中的元素必須是字串型態，否則直譯器會報錯`TypeError`_
_註2: 第34行的`print(" * ".join(ans))`也可以寫成`print(*ans, sep=" * ")`_
>程式說明 (比較有效率版)
:::success
比較有效率版更改的地方是...
1. while的條件改成 $p^2 \leq n$ (意思就是 $p \leq \sqrt{n}$) (第8行)
2. while中加一段`if`判斷target是否早已被分解完 (第24, 25行)
3. while後加上else以確保n還有`(被分解剩的)target`這個質因數 (第29, 30行)
:::
> 程式碼 (比較有效率版)
```python=
n = int(input())
#part1: 把數字分解
target = n
p = 2
result = []
while p*p <= n:
times = 0
while target%p ==0:
times+=1
target //= p
if times==0:
pass
else:
result.append( (p, times) )
if target==1: #已經分解完了，結束while-loop
break
p += 1
else: #while-loop沒有被break掉=>n還有一個質因數target
result.append( (target, 1) )
#part2-1: 處理答案
ans = []
for base, power in result:
if power==1:
ans.append(str(base))
else:
ans.append(f"{base}^{power}")
#part2-2: 輸出答案
print(" * ".join(ans))
```
_註1: 第8行的`while p*p <= n:`可以寫成`for p in range(2, int(n**0.5) + 1)` 然後把第26的`p+=1`跟第5行的`p = 2`去掉_
### C
> 程式說明(偷懶版)
::: success
#### Part1 分解:
按照上面題解的流程圖分解到目標數字剩下1為止(即分解完了)，並把答案存入`bases` `powers`兩個陣列中
#### Part2 印出答案:
把`bases` `powers`中的元素一一取出，並輸出答案
:::
>程式碼 (偷懶版)
```c=
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
// Part 1: 分解數字
int target = n; //待試除的數字
int p = 2;
int bases[30];
int powers[30];
int count = 0; //紀錄已找到幾個質因數
while (target != 1) {
int times = 0; //紀錄除了多少次
while (target%p == 0) { //除到不能再除為止
times++;
target /= p;
}
if (times > 0) {
bases[count] = p;
powers[count] = times;
count++;
}
p++;
}
// Part 2: 輸出答案
for (int i=0; i<count; i++) {
if (powers[i] == 1) {
printf("%d", bases[i]);
} else {
printf("%d^%d", bases[i], powers[i]);
}
if (i != count-1) { //true: 不是最後一個
printf(" * ");
}
}
return 0;
}
```
> 程式說明(比較有效率版)
:::success
比較有效率版更改的地方是...
1. while的條件改成 $p^2 \leq n$ (意思就是 $p \leq \sqrt{n}$) (第15行)
2. while中加一段`if`判斷target是否早已被分解完 (第29~31行)
3. while後加上if以確保n還有`(被分解剩的)target`這個質因數 (第36~40行)
:::
> 程式碼(比較有效率版)
```c=
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
// Part 1: 分解數字
int target = n;
int p = 2;
int bases[30];
int powers[30];
int count = 0;
while (p*p <= n) {
int times = 0;
while (target%p == 0) {
times++;
target /= p;
}
if (times > 0) {
bases[count] = p;
powers[count] = times;
count++;
}
if (target==1){ //true: target已經分解完了，結束while-loop
break;
}
p++;
}
if (target != 1){ //true: n還有一個質因數: 分解剩的target
bases[count] = target;
powers[count] = 1;
count++;
}
// Part 2: 輸出答案
for (int i=0; i<count; i++) {
if (powers[i] == 1) {
printf("%d", bases[i]);
} else {
printf("%d^%d", bases[i], powers[i]);
}
if (i != count-1) {
printf(" * ");
}
}
return 0;
}
```
### C++
> 程式說明 (偷懶版)
:::success
#### Part1 分解:
按照上面題解的流程圖分解到目標數字剩下1為止(即分解完了)，並把答案(以pair型態)存入`result vector`中
#### Part2 印出答案:
把`result vector`中的pair一一取出，並輸出答案
:::
> 程式碼 (偷懶版)
```cpp=1
#include <iostream>
#include <vector>
#include <utility> //pair&make_pair
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
// Part 1: 分解數字
int target = n; //待試除的數字
int p = 2;
vector<pair<int, int>> result;
while (target != 1) {
int times = 0; //紀錄除了多少次
while (target % p == 0) { //除到不能再除為止
times+=1;
target /= p;
}
if (times > 0) {
result.push_back(make_pair(p, times));
}
p+=1;
}
// Part 2-1: 處理答案
vector<string> ans;
for (auto &data : result) { //auto也可寫成pair<int, int>
int base = data.first;
int power = data.second;
if (power == 1) {
ans.push_back(to_string(base)); //Eg: result中的{2, 1}到ans中會變成"2"
} else {
ans.push_back(to_string(base) + "^" + to_string(power));
//Eg: result中的{3, 5}到ans中會變成"3^5"
}
}
//Part 2-2:輸出結果
for (int i = 0; i < ans.size(); i++) {
cout << ans[i];
if (i < ans.size() - 1) { //還不是最後一個
cout << " * ";
}
}
return 0;
}
```
_註1:第27行的`result.push_back(make_pair(p, times));`可以寫成`result.push_back({p, times});`或是`result.emplace_back(p, times);`_
> 程式說明 (比較有效率版)
:::success
比較有效率版更改的地方是...
#### Part1:
1. while的條件改成 $p^2 \leq n$ (意思就是 $p \leq \sqrt{n}$) (第18行)
2. while中加一段`if`判斷target是否早已被分解完 (第31~33行)
3. while後加上if以確保n還有`(被分解剩的)target`這個質因數 (第38~40行)
#### Part2:
4. 加了個sstream，會提高一點效率，程式碼也好看一點
:::
> 程式碼 (比較有效率版)
```cpp=1
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <sstream>
using namespace std;
int main() {
int n;
cin >> n;
// Part 1: 分解數字
int target = n;
int p = 2;
vector<pair<int, int>> result;
while (p*p <= n) {
int times = 0;
while (target % p == 0) {
times+=1;
target /= p;
}
if (times > 0) {
result.push_back(make_pair(p, times));
}
if (target==1){ //true: target已經分解完了，結束while-loop
break;
}
p+=1;
}
if (target != 1){ //true: n還有一個質因數: 分解剩的target
result.push_back(make_pair(target, 1));
}
// Part 2-1: 處理答案
stringstream ans;
for (auto &data : result) {
int base = data.first;
int power = data.second;
if (power == 1) {
ans << base;
} else {
ans << base << "^" << power;
}
if (&data != &result.back()) {
ans << " * ";
}
}
//Part 2-2:輸出結果
cout << ans.str();
return 0;
}
```
_註1: 第19行的`while (p*p <= n) {`也可以寫成`for(int p=2; p<=sqrt(n); p++) {`，(要`#include <cmath>`)然後第34行`p+=1;`跟第15行的`int p = 2;`去掉_
_註2: **sstream中的stringstream簡介**: stringstream可以把字串(string)變成字符串流(stringstream)，讓他有和`cin`, `cout`一樣用`>>` `<<`寫入跟讀取的功能。詳細用法請詢問Google大神為您解惑。_
### Java
>程式說明 (偷懶版)
:::success
#### Part1 分解:
按照上面題解的流程圖分解到目標數字剩下1為止(即分解完了)，並把答案分別存入`bases`, `powers`兩個ArrayList中
#### Part2 印出答案:
把`bases`, `powers`的元素一一取出，組合起來後直接輸出
_註1: 這個作法和上面C++，Python略有不同。因為Java的二維ArrsyList太難寫了，所以改用兩個ArrayList存答案(ゝ∀･)b_
:::
> 程式碼 (偷懶版)
```java=1
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//Part1: 分解數字
int target = n;
int p = 2;
ArrayList<Integer> bases = new ArrayList<>(); //儲存答案
ArrayList<Integer> powers = new ArrayList<>();
while (target != 1) {
int times = 0; // 記錄除了多少次
while (target % p == 0) { // 除到不能再除為止
times++;
target /= p;
}
if (times > 0) {
bases.add(p);
powers.add(times);
}
p++;
}
//Part2: 輸出答案
for (int i=0; i<bases.size(); i++){
if (powers.get(i) == 1) { //一次方不用印'^'
System.out.print(bases.get(i));
}else {
System.out.print(bases.get(i) + "^" + powers.get(i));
}
if (i != bases.size()-1){
System.out.print(" * ");
}
}
scanner.close();
}
}
```
_註1: 來向各位分享一下敝人犯的智障錯誤:
第39行的 **`System.out.print(bases.get(i) + "^" + powers.get(i));`** 的意思是把`bases的第i個`和`^`和`powers的第i個`組合起來輸出。如果像我第一次寫寫成 **`System.out.print(bases.get(i) + '^' + powers.get(i));`** 會變成把兩個數字和`^的ASCII`加起來輸出。結果會不如預期喔_
>程式說明 (比較有效率版)
::: success
比較有效率版更改的地方是...
#### Part1:
1. while的條件改成 $p^2 \leq n$ (意思就是 $p \leq \sqrt{n}$) (第20行)
2. while中加一段`if`判斷target是否早已被分解完 (第30-32行)
3. while後加上if以確保n還有`(被分解剩的)target`這個質因數 (第37-40行)
#### Part2:
4. 加了StringBuilder，會提高一點效率
:::
>程式碼 (比要有效率版)
```java=1
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//Part1: 分解數字
int target = n;
int p = 2;
ArrayList<Integer> bases = new ArrayList<>();
ArrayList<Integer> powers = new ArrayList<>();
while (p*p <= n) {
int times = 0;
while (target % p == 0) {
times++;
target /= p;
}
if (times > 0) {
bases.add(p);
powers.add(times);
}
if (target==1){ //true=>已經分解完了
break;
}
p++;
}
if (target != 1){ //true: n還有一個質因數: 分解剩的target
bases.add(target);
powers.add(1);
}
//Part2: 輸出答案
StringBuilder strbld = new StringBuilder();
for (int i = 0; i < bases.size(); i++) {
if (powers.get(i) == 1) {
strbld.append(bases.get(i));
} else {
strbld.append(bases.get(i)).append("^").append(powers.get(i));
}
if (i != bases.size() - 1) {
strbld.append(" * ");
}
}
System.out.println(strbld.toString());
scanner.close();
}
}
```
_註1: 第17行的`while (p*p <= n) {`可以改成 `for (int p=2; p<=Math.sqrt(n); p++) {` 然後把第34行`p++;`跟第13行`int p = 2;`去掉_
_註2: **java.lang.StringBuilder簡介:** StringBuilder能讓Java有一個可以改變內容的字串(本來的String不行)。裡面有`.append()`, `.insert()`, `.delete()`等等的函式。詳細用法請詢問Google大神。_
<a id=a013></a>
## zerojudge-a013 羅馬數字
### [題目](https://zerojudge.tw/ShowProblem?problemid=a013)
:::info
> 內容
如果生活在數世紀之前的古羅馬，你應該用過 V 來表示五。V 和 5 這兩個符號都可以用來表示數目五。用來表示數目的符號稱作數字。而羅馬人用來表示數目的符號就是羅馬數字。
以下是七個基本的羅馬數字︰
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #BECFD8;">
<th style="width: 50%; border: 1px solid #ddd; padding: 8px;">羅馬數字</th>
<th style="width: 50%; border: 1px solid #ddd; padding: 8px;">數目</th>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">I</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">1</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">V</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">5</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">X</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">10</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">L</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">50</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">C</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">100</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">D</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">500</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">M</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">1,000</td>
</tr>
</table>
所有其他的數目都是由這些數字組合而成。數目都是由左寫到右，通常值是等於組成的羅馬數字加起來。
例如十七可以表示為
<table style="width:100%; border-collapse: collapse; background-color: #D9EDF7;">
<tr style="background-color: #D9EDF7;">
<td style="border: 1px solid #D9EDF7; text-align: right; padding: 8px; background-color: #D9EDF7;">X</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">+</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">V</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">+</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">I</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">+</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">I</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">=</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">XVII</td>
</tr>
<tr style="background-color: #D9EDF7;">
<td style="border: 1px solid #D9EDF7; text-align: right; padding: 8px; background-color: #D9EDF7;">10</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">+</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">5</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">+</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">1</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">+</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">1</td>
<td style="border: 1px solid #D9EDF7; text-align: center; padding: 8px; background-color: #D9EDF7;">=</td>
<td style="border: 1px solid #D9EDF7; text-align: left; padding: 8px; background-color: #D9EDF7;">17</td>
</tr>
</table>
表示羅馬數字可以使用減法來取代加法的規則。例如四可以不用四個一相加來表示 IIII，而採用五減一來表示 IV。利用這類規則，羅馬人能夠減化許多數目的表示方式，例如 IX 取代 VIIII 表示 9，及 CD 取代 CCCC 表示 400。
今日我們並不確定羅馬符號的起源為何。例如符號 V 的起源主要有兩個理論。有些學者認為五最早是用握拳、拇指在外的手勢來表示。最後以象形文字書寫而簡化為 V。
另一個理論認為 X 源自在 10 條線加上交叉線。因此五可以表示為 X 的一半，或是 V。
羅馬數字可以很容易地用來相加或相減，但算起乘除法就相當不順手。這就是為什麼現在羅馬數字並不常用的原因了。
**問題**
然而，羅馬數字還是經常用於書本章節及頁碼的編號。在這一題工作是讀入兩個正整數，然後輸出兩個數字差的絕對值。所有的數字都必須以羅馬數字來表示。而連續四個相同符號出現時，必須用減法規則來化簡之。
>輸入說明
每個輸入檔中會有一個或以上的測試資料。每一行由兩個數字組成一筆測試資料，且所有數字將會小於4,000。檔案最後會以符號 # 表示結束。
>輸出說明
每筆測試資料的答案必須輸出到檔案中，並且換行。如果答案為零，則須輸出字串 ZERO
> 標籤
進位制
:::
### 範例輸入&輸出
:::info
> 範例輸入 #1
I I
MM II
\#
> 範例輸出 #1
ZERO
MCMXCVIII
:::
<a id=a013-1></a>
### 題解Part1 羅馬數字-->阿拉伯數字
:::warning
**原理:**
這個部分比較好想，只要判斷每個羅馬數字符號是被加的還是被減的就好了。判斷方法也很簡單——**只要他後面的數字比它大，它就是被減的，不然就是被加的**
(Eg: `IV`中的`I`, `XC`中的`X`, `CD`中的`C`分別是代表`-1`, `-10`, `-100`的意思； `III`中的`I`, `DCC`中的`D`和`C`則是代表`+1`, `+100`, `+500`。
**作法:**
在寫程式的時候我們可以建立一個`map(在python叫做dict)`裡面長這樣:
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Key</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Value</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Key</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Value</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">I</td>
<td style="border: 1px solid #ddd; padding: 8px;">1</td>
<td style="border: 1px solid #ddd; padding: 8px;">V</td>
<td style="border: 1px solid #ddd; padding: 8px;">5</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
<td style="border: 1px solid #ddd; padding: 8px;">10</td>
<td style="border: 1px solid #ddd; padding: 8px;">L</td>
<td style="border: 1px solid #ddd; padding: 8px;">50</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">C</td>
<td style="border: 1px solid #ddd; padding: 8px;">100</td>
<td style="border: 1px solid #ddd; padding: 8px;">D</td>
<td style="border: 1px solid #ddd; padding: 8px;">500</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">M</td>
<td style="border: 1px solid #ddd; padding: 8px;">1,000</td>
<td style="border: 1px solid #ddd; padding: 8px;">~</td>
<td style="border: 1px solid #ddd; padding: 8px;">~</td>
</tr>
</table>
就可以使用`for-loop`遍歷每一個羅馬數字符號，把它和它的下一個抓出來後比較，並用第一段說的規則判斷出該符號是被加的還是被減的。
**舉例:**
要轉換`CXLIX`成149時: 會長這樣
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="border: 1px solid #ddd; padding: 8px;">抓出的符號</th>
<th style="border: 1px solid #ddd; padding: 8px;">它的下一個</th>
<th style="border: 1px solid #ddd; padding: 8px;">比較</th>
<th style="border: 1px solid #ddd; padding: 8px;">結果</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">C</td>
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
<td style="border: 1px solid #ddd; padding: 8px;">C>X</td>
<td style="border: 1px solid #ddd; padding: 8px;">C是+100</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
<td style="border: 1px solid #ddd; padding: 8px;">L</td>
<td style="border: 1px solid #ddd; padding: 8px;">X<L</td>
<td style="border: 1px solid #ddd; padding: 8px;">X是-10</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">L</td>
<td style="border: 1px solid #ddd; padding: 8px;">I</td>
<td style="border: 1px solid #ddd; padding: 8px;">L>I</td>
<td style="border: 1px solid #ddd; padding: 8px;">L是+50</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">I</td>
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
<td style="border: 1px solid #ddd; padding: 8px;">I<X</td>
<td style="border: 1px solid #ddd; padding: 8px;">I是-1</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
<td style="border: 1px solid #ddd; padding: 8px;">沒了</td>
<td style="border: 1px solid #ddd; padding: 8px;">X>沒東西</td>
<td style="border: 1px solid #ddd; padding: 8px;">X是+10</td>
</tr>
<tr style="background-color: #EFEBD7;">
<td style="border: 1px solid #ddd; padding: 8px;text-align: center;" colspan="4">~end~</td>
</tr>
</table>
最後的結果就是$100-10+50-1+10 = 149$
:::
<a id=a013-2></a>
### 題解Part2 阿拉伯數字-->羅馬數字
::: warning
先講作法，再講原理。大概會好懂一點
**作法:**
在這裡我們會建立一個長這樣的map:
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Key</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Value</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Key</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">Value</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">1000</td>
<td style="border: 1px solid #ddd; padding: 8px;">M</td>
<td style="border: 1px solid #ddd; padding: 8px;">40</td>
<td style="border: 1px solid #ddd; padding: 8px;">XL</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">900</td>
<td style="border: 1px solid #ddd; padding: 8px;">CM</td>
<td style="border: 1px solid #ddd; padding: 8px;">10</td>
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">500</td>
<td style="border: 1px solid #ddd; padding: 8px;">D</td>
<td style="border: 1px solid #ddd; padding: 8px;">9</td>
<td style="border: 1px solid #ddd; padding: 8px;">IX</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">400</td>
<td style="border: 1px solid #ddd; padding: 8px;">CD</td>
<td style="border: 1px solid #ddd; padding: 8px;">5</td>
<td style="border: 1px solid #ddd; padding: 8px;">V</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">100</td>
<td style="border: 1px solid #ddd; padding: 8px;">C</td>
<td style="border: 1px solid #ddd; padding: 8px;">4</td>
<td style="border: 1px solid #ddd; padding: 8px;">IV</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">90</td>
<td style="border: 1px solid #ddd; padding: 8px;">XC</td>
<td style="border: 1px solid #ddd; padding: 8px;">1</td>
<td style="border: 1px solid #ddd; padding: 8px;">I</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">50</td>
<td style="border: 1px solid #ddd; padding: 8px;">L</td>
<td style="border: 1px solid #ddd; padding: 8px;">~</td>
<td style="border: 1px solid #ddd; padding: 8px;">~</td>
</tr>
</table>
處理流程是 從map的第一個`key`開始，一直減那個數字減到減到不能減，再換下一個`key`。重複那個過程到`key=1`結束為止。每減一次就印出那個`key`所對應的`value`，程式跑完答案就出來了。 _(有點像是a010因數分解那一題)_
**舉例**: 把`2964`轉換成`MMCMLXIV`
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="border: 1px solid #ddd; padding: 8px;">Step...</th>
<th style="border: 1px solid #ddd; padding: 8px;">減掉的數字</th>
<th style="border: 1px solid #ddd; padding: 8px;">輸出的符號</th>
<th style="border: 1px solid #ddd; padding: 8px;">剩下~</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">1</td>
<td style="border: 1px solid #ddd; padding: 8px;">1000</td>
<td style="border: 1px solid #ddd; padding: 8px;">M</td>
<td style="border: 1px solid #ddd; padding: 8px;">1964</td>
</tr>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">2</td>
<td style="border: 1px solid #ddd; padding: 8px;">1000</td>
<td style="border: 1px solid #ddd; padding: 8px;">M</td>
<td style="border: 1px solid #ddd; padding: 8px;">964</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">3</td>
<td style="border: 1px solid #ddd; padding: 8px;">900</td>
<td style="border: 1px solid #ddd; padding: 8px;">CM</td>
<td style="border: 1px solid #ddd; padding: 8px;">64</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">4</td>
<td style="border: 1px solid #ddd; padding: 8px;">50</td>
<td style="border: 1px solid #ddd; padding: 8px;">L</td>
<td style="border: 1px solid #ddd; padding: 8px;">14</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">5</td>
<td style="border: 1px solid #ddd; padding: 8px;">10</td>
<td style="border: 1px solid #ddd; padding: 8px;">X</td>
<td style="border: 1px solid #ddd; padding: 8px;">4</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">6</td>
<td style="border: 1px solid #ddd; padding: 8px;">4</td>
<td style="border: 1px solid #ddd; padding: 8px;">IV</td>
<td style="border: 1px solid #ddd; padding: 8px;">0</td>
</tr>
<tr style="background-color: #EFEBD7;">
<td style="border: 1px solid #ddd; padding: 8px;text-align: center;" colspan="4">~end~</td>
</tr>
</table>
最後把答案組合起來就會變成: $MMCMLXIV$
**原理:**
其實這個作法背後的原理要講...還需要一個表比較好理解
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="width: 25%; border: 1px solid #ddd; padding: 8px; text-align: center;">阿拉伯數字</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px; text-align: center;">羅馬數字</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px; text-align: center;">阿拉伯數字</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px; text-align: center;">羅馬數字</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">1</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">I</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">6</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">VI</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">2</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">II</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">7</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">VII</td>
</tr>
<!-- 其他數字的行 -->
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">3</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">III</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">8</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">VIII</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">4</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">IV</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">9</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">IX</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">5</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">V</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">10</td>
<td style="border: 1px solid #ddd; padding: 8px; text-align: center;">X</td>
</tr>
</table>
如果不考慮`4`, `9`這兩個數字，1~10的羅馬數字都是基於加法運算來表示的。這個時候要轉換就簡單啦\~開一個`{10, 5, 1}`的map 從大的開始一直減減減就結束了。
但是，加了`4`, `9`這兩個用減法表示的數字就不一樣了。持續使用上面的做法的話，`9`會變成`VIII`(X), 4會變成`IIII`(X)。除了特別使用`if-else`等等作法特別考慮這些情況之外，有一個更好的方法——就是把map改成`{10, 9, 5, 4, 1}`。因為上述方法是**從大的數字往小的數字減的**，所以在數字是9的時候，程式會直接把數字減9然後輸出`IX`，而不會發生減5減4輸出`VIV`等荒謬情況。map的設計是Part2解法的關鍵。
:::
### Python
> 程式碼
```python=
#題解Part1:
def rom_to_ara(romnum):
#建立dict
translation = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500,'M': 1000}
result = 0
#比較每一個字母和它的下一個，為了避免IndexError，迴圈只有算到倒數第二個
for idx in range(len(romnum)-1):
now = translation[ romnum[idx] ]
nex = translation[ romnum[idx+1] ]
if (now>=nex):
result+=now
else:
result-=now
result += translation[ romnum[-1] ] #把最後一個字母補算完
return result
#題解Part2:
def ara_to_rom(aranum):
if aranum==0:
return "ZERO"
#建立dict
translation = {1000: "M", 900: "CM", 500: "D", 400: "CD", 100: "C", 90: "XC",
50: "L", 40: "XL", 10: "X", 9: "IX", 5: "V", 4: "IV", 1:"I" }
result = ""
#從第一個key開始，開始減減減減到最後一個
for key, value in translation.items():
while aranum >= key:
aranum -= key
result = result + value
return result
#主程式開始
inp = input()
while inp != "#":
roma, romb = inp.split()
araa, arab = rom_to_ara(roma), rom_to_ara(romb)
araans = abs(araa-arab)
print(ara_to_rom(araans))
inp = input()
```
_註1: `mydict.items()`會把mydict中的keys和values抓出來，兩兩一組組成tuple，最後包成`dict_items`物件回傳。`dict_items`可以用迭代器(`iter() + next()`, `for-loop`...)遍歷，但是不能隨機訪問(`~~[idx]`)，所以通常會轉成list來用_
### C
> 程式說明
:::success
因為C沒有map這種好東西，所以C的程式碼會和題解說的有點不一樣
#### Part1:
羅馬數字符號-->阿拉伯數字，可以另外寫一個函式來取代map的功能 (下面寫作romc_to_aran)
#### Part2:
阿拉伯數字-->羅馬數字，可以用兩個陣列來取代map。還有，要把阿拉伯數字答案再存入字元陣列中太麻煩了，下面的程式採用一邊轉換一邊輸出的方法。
:::
> 程式碼
```c==
#include <stdio.h>
#include <string.h> //strlen
#include <stdlib.h> //abs
int romc_to_aran(char romc){
switch(romc){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return -999;
}
}
int rom_to_ara(char romnum[]){
int result = 0;
int length = strlen(romnum);
//比較每一個字母和它的下一個，為了避免超出string長度範圍，迴圈只有算到倒數第二個
for (int idx=0; idx<length-1; idx++){
int now = romc_to_aran( romnum[idx] );
int next = romc_to_aran( romnum[idx+1] );
if (now>=next) result+=now;
else result-=now;
}
result += romc_to_aran( romnum[length-1] ); //把最後一個字母補算完
return result;
}
void ara_to_rom(int aranum){
if (aranum==0){
printf("ZERO\n");
return; //提前終止函式
}
//建立兩個陣列，兩個長度都是13，下面會用到
int arakey[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
char* romvalue[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
for (int idx=0; idx<13; idx++){
int key = arakey[idx];
char* value = romvalue[idx];
while (aranum>=key){
aranum -= key;
printf("%s", value);
}
}
printf("\n"); //換行
}
int main(){
char roma[16], romb[16];
while (scanf("%s %s", roma, romb)==2){
int arra = rom_to_ara(roma);
int arrb = rom_to_ara(romb);
int araans = abs(arra-arrb);
ara_to_rom(araans);
}
return 0;
}
```
_註1: 題目有說所有數字小於4000。羅馬數字最長也就3888(`MMMDCCCLXXXVIII`)一共15位。所以讀取輸入的字串(`char[]`)只要開15+1(`\0`)個就好_
_註2: 第55行的 `char* romvalue[]` 在這裡是宣告一個指向`char[]`的指針陣列_
### C++
> 程式碼
```cpp=1
#include <iostream>
#include <map>
#include <string>
#include <functional> //greater
using namespace std;
//題解Part1:
int rom_to_ara(string romnum){
//建立map
map<char, int> translation = {
{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
{'C', 100}, {'D', 500}, {'M', 1000}};
int result = 0;
//比較每一個字母和它的下一個，為了避免超出string長度範圍，迴圈只有算到倒數第二個
for (int idx=0; idx<romnum.size()-1; idx++){
int now = translation[ romnum[idx] ];
int next = translation[ romnum[idx+1] ];
if (now>=next) result+=now;
else result-=now;
}
result += translation[ romnum.back() ]; //把最後一個字母補算完
return result;
}
string ara_to_rom(int aranum){
if (aranum==0) return "ZERO";
//建立map
map<int, string, greater<int>> translation = {
{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
{10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}};
string result = "";
//從第一個key開始，開始減減減減到最後一個
for (pair<const int, string> &data: translation){
int key = data.first;
string value = data.second;
while (aranum >= key){
aranum -= key;
result = result+value;
}
}
return result;
}
int main(){
string roma, romb;
while(cin>>roma>>romb){
int arra = rom_to_ara(roma), arrb = rom_to_ara(romb);
int araans = abs(arra-arrb);
cout << ara_to_rom(araans) << endl;
}
}
```
_註1:functional\-std\:\:greater: 詳細的資訊大家可以去google, 這裡就講結論就好了。`greater`放在`priority_queue`, `sort`, `map`, `set`這種可以自訂排序規則的容器時，它會讓容器內的元素**由大到小排**。_
_在本程式中，為了讓translation的key值是遞減排序的，所以map在初始化時放了`greater<int>`來排序key值_
_註2: `while(cin>>roma>>romb)`寫的時候的想法: `cin`在`failbit`(錯誤讀取)或是`eofbit`(輸入檔到底了)被設置時，cin會回傳false。_
_因此可以利用這個特性。當程式讀取到會後一行`#`時， `#`會存入roma，然後就沒有東西可以讀入romb了。因此`cin`會回傳false，進而跳脫`while-loop`_
### Java
> 程式碼
```java=1
import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map; //for Map.Entry
import java.util.Comparator; //for Comparator.reverseOrder
public class Main{
//題解Part1
private static int rom_to_ara(String romnum){
//建立map
TreeMap<Character, Integer> translation = new TreeMap<>();
translation.put('I', 1);
translation.put('V', 5);
translation.put('X', 10);
translation.put('L', 50);
translation.put('C', 100);
translation.put('D', 500);
translation.put('M', 1000);
int result=0;
//比較每一個字母和它的下一個，為了避免超出string長度範圍，迴圈只有算到倒數第二個
for (int idx = 0; idx < romnum.length() - 1; idx++) {
int now = translation.get( romnum.charAt(idx) );
int next = translation.get( romnum.charAt(idx + 1) );
if (now >= next) result += now;
else result -= now;
}
//把最後一個字母補算完
result += translation.get( romnum.charAt(romnum.length() - 1) );
return result;
}
//題解Part2
private static String ara_to_rom(int aranum){
if (aranum == 0) return "ZERO";
//建立map
TreeMap<Integer, String> translation =
new TreeMap<>(Comparator.reverseOrder());
translation.put(1000, "M");
translation.put(900, "CM");
translation.put(500, "D");
translation.put(400, "CD");
translation.put(100, "C");
translation.put(90, "XC");
translation.put(50, "L");
translation.put(40, "XL");
translation.put(10, "X");
translation.put(9, "IX");
translation.put(5, "V");
translation.put(4, "IV");
translation.put(1, "I");
StringBuilder result = new StringBuilder();
//從第一個key開始，開始減減減減到最後一個
for (Map.Entry<Integer, String> data : translation.entrySet()) {
int key = data.getKey();
String value = data.getValue();
while (aranum >= key) {
aranum -= key;
result.append(value);
}
}
return result.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
String roma = scanner.next();
if ("#".equals(roma)) {
break; //碰到#就結束了
}
String romb = scanner.next();
int araa = rom_to_ara(roma);
int arab = rom_to_ara(romb);
int araans = Math.abs(araa-arab);
System.out.println(ara_to_rom(araans));
}
scanner.close();
}
}
```
_註1: `Comparator.reverseOrder()`: 會回傳一個比較器(comparator)，放在`TreeMap`, `TreeSet`, `sort`...時，可以讓元素**反自然排序**。如果是數字就是由大到小排 (Eg: `2 3 1` --> `3 2 1`)，字串就是...字典排序後反過來(Eg: `banana cherry apple` --> `cherry banana apple`)。_
_在本程式中，為了讓translation的key值是遞減排序的，所以map在初始化時放了`Comparator.reverseOrder()`來排序key值_
_註2: `Map.Entry`: 用`Map.Entry`建立的物件可以存某個map的key&value，用`entry.getKey()` `entry.getValue()`可以把值給提出來。_
_比起把一個map的keys(`.keySet()`)和values(`.values()`)抓出來再遍歷，使用Map.Entry會直觀一點。 (只是要`import java.util.Map`就是了030)_
<a id=a015></a>
## zerojudge-a015 矩陣的翻轉
### [題目](https://zerojudge.tw/ShowProblem?problemid=a015)
:::info
> 內容
已知一(m x n)矩陣**A**，我們常常需要用到另一個將**A**中之行與列調換的矩陣。這個動作叫做矩陣的翻轉。舉例來說，
若**A=**
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #D6EAF4;">
<td style="width: 20%; border: 1px solid #ddd; padding: 8px;">3</td>
<td style="width: 20%; border: 1px solid #ddd; padding: 8px;">1</td>
<td style="width: 20%; border: 1px solid #ddd; padding: 8px;">2</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 20%; border: 1px solid #ddd; padding: 8px;">8</td>
<td style="width: 20%; border: 1px solid #ddd; padding: 8px;">5</td>
<td style="width: 20%; border: 1px solid #ddd; padding: 8px;">4</td>
</tr>
</table>
則**AT=**
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #D6EAF4;">
<td style="width: 33%; border: 1px solid #ddd; padding: 8px;">3</td>
<td style="width: 33%; border: 1px solid #ddd; padding: 8px;">8</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 33%; border: 1px solid #ddd; padding: 8px;">1</td>
<td style="width: 33%; border: 1px solid #ddd; padding: 8px;">5</td>
</tr>
<tr style="background-color: #D6EAF4;">
<td style="width: 33%; border: 1px solid #ddd; padding: 8px;">2</td>
<td style="width: 33%; border: 1px solid #ddd; padding: 8px;">4</td>
</tr>
</table>
現在 請您針對所讀取到的矩陣進行翻轉。
>輸入說明
第一行會有兩個數字，分別為 列(row)<100 和 行(column)<100，緊接著就是這個矩陣的內容
** 測資檔會包含多組矩陣資料
>輸出說明
直接輸出翻轉後的矩陣
> 標籤
二維陣列
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
2 3
3 1 2
8 5 4
>範例輸出 #1
3 8
1 5
2 4
:::
### 題解
:::warning
這個所謂的"矩陣的翻轉"其實有一個專有名詞，叫做**轉置(transpose)**，也就是把陣列的行和列互換。
舉例來說，有個$2\times3$的矩陣A長這樣:
$$ A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} $$
那他的轉置矩陣AT就會是一個$3\times2$的矩陣(因為A的行換到AT的列了)，長這樣:
$$ A^T = \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} $$
換到矩陣的一般形式來看\~
大小為$m\times n$原矩陣A和轉置矩陣AT:
$$ A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} ~~~~~~~~~~~~~~~ A^T = \begin{pmatrix} a_{11} & a_{21} & \cdots & a_{m1} \\ a_{12} & a_{22} & \cdots & a_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{mn} \end{pmatrix} $$
眼尖的各位應該發現了，轉置矩陣有幾個特性:
* 原本矩陣是$m\times n$，新矩陣就是$n\times m$
* $AT_[c][r]~~=~~A[r][c]$
_(對沒錯前面鋪那個多梗只是為了講這個)_
:::
### Python
> 程式說明
::: success
為了讓程式更清楚一點，寫了transpose函式，拿來讀取並轉置矩陣用
:::
> 程式碼 original
```python=
import sys #該死的多筆輸入...
def transpose(A, row, column):
#先建立大小為column * row的空陣列
AT = []
for _ in range(column): AT.append( [0]*row )
#轉置
for c in range(column):
for r in range(row):
AT[c][r] = A[r][c]
return AT
for inp in sys.stdin:
row, column = map(int, inp.split())
matrix = []
for _ in range(row):
matrix.append( list(map(int, sys.stdin.readline() .split())) )
#轉置&輸出
ans = transpose(matrix, row, column)
for ele in ans:
print(*ele)
```
<a id=a015-1></a>
_註1: 第27行的`*ele`: `*`在這裡的作用為**解包(unpacking)**，也就是把一個陣列(或是其他可以迭代的東西)拆解成很多個元素。運用場景蠻多的，舉例如下:_
::: spoiler _有點長 有興趣的請自行點開來看_
1. 假設你有一個函式`func(a, b, c)` 還有一個陣列`args = [1, 2, 3]` 你想要把arg的元素丟到func裡面去，可以這樣寫
```python
def func(a, b, c):
#...
pass
args = [1, 2, 3]
func(*args) #等同於func(1, 2, 3)
```
2. 假設你有一個陣列`args = [1, 2, 3, 4, 5]` 你想要把他print出來。除了用`for-loop`或是`map(str, ...) + ''.join()`，還可以用`*`
```python
args = [1, 2, 3, 4, 5]
print(*args) #等同於print(1, 2, 3, 4, 5) #output: 1 2 3 4 5
#也可以改變中間要間隔甚麼喔
print(*args, sep="*") #output: 1*2*3*4*5
print(*args, sep="") #output: 12345
```
3. 假設你有一個陣列`args = [1, 2, 3, 4, 5]` 你想把第一個數字賦予變數a，其他全部丟到陣列b。除了用slice (`[start:end:step]` / `slice(start, end, step)`) 之外，你也可以這樣寫
```python
args = [1, 2, 3, 4, 5]
a, *b = args
print(a, b) #output 1 [2, 3, 4, 5]
a, b, c, *d = args
print(a, b, c, d) #output: 1 2 3 [4, 5]
a, *b, c = args
print(a, b, c) #ourput: 1 [2, 3, 4] 5
*a, *b = args #SyntaxError:不能在賦值的時候解包兩個東西(畢竟直譯器也不知道要怎麼分配嘛)
#這個時候就乖乖用slice吧
a, b = args[:2], args[2:]
print(a, b) #output: [1, 2] [3, 4, 5]
```
:::
<br>
> 程式碼 list comprehension
```python=
import sys
def transpose(A, row, column):
AT = [[A[r][c] for r in range(row)] for c in range(column)]
return AT
for inp in sys.stdin:
row, column = map(int, inp.split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(row)]
ans = transpose(matrix, row, column)
for ele in ans: print(*ele)
```
_註1: 第4, 11行的list comprehension(中文翻譯蠻多的: 列表理解,列表推導式...)簡介_
::: spoiler _有點長 有興趣的請自行點開_
* list comprehension的結構 (乾好像在學英文文法)
* 一般結構:
`[表達式 for 元素 in 可迭代物件]`
* 在for後面加上if，只有條件成立時元素才會加入list，達成過濾的效果。 長這樣:
`[表達式 for 元素 in 可迭代物件 if 條件]`
好啦我知道那個很難看懂。來個舉例
1. 假設你想要建立一個陣列 裡面有1~5的平方數。除了用`for-loop`，你還可以這樣寫
```python
square = [num**2 for num in range(1, 6)]
print(square) #output: [1, 4, 9, 16, 25]
```
2. 假設你想要建立一個陣列 裡面有1~10中的偶數的平方數。除了用`for-loop`，你還可以這樣寫
```python
even_square = [num**2 for num in range(1, 11) if num%2==0]
#想這樣寫也...可以啦
even_square = [num**2 for num in range(2, 11, 2)]
print(even_square) #output: [4, 16, 36, 64, 100]
```
3. **表達式裡面還可以再塞一個if-else**
假設你有一個陣列`args = [1, 4, 3]` 你想要建立一個陣列，裡面儲存args的每一個元素是奇數還是偶數。除了用`for-loop`或是`map()`，你還可以這樣寫
```python
args = [1, 4, 3]
judge = ["even" if ele%2==0 else "odd" for ele in args]
print(judge) #output: ['odd', 'even', 'odd']
```
_註1-1: `"even" if ele%2==0 else "odd"` 這個東西的意思是: **如果`ele%2==0`(條件)成立就回傳`even`, 不成立就回傳`odd`**。 用法有點類似C\+\+ Java的`條件? 表達式1:表達式2`_
_註1-2: 註1-1的東西其實有個專有名詞，叫做三元運算子(Ternary Operator)。他的名字沒有很重要就是了，會用就好_
4. **一個方括號內是可以放兩個for的。**
假設你有兩個陣列`arga=[1, 2, 3]`, `argb=[4, 5, 6]`，你想要把arga, argb的所有組合方式列出來。除了用`for-loop`，你還可以這樣
```python
arga = [1, 2, 3]
argb = [4, 5, 6]
pairs = [(elea, eleb) for eleb in argb for elea in arga]
print(pairs)
#output: [(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (1, 6), (2, 6), (3, 6)]
```
5. **表達式的if else(三元運算子) 和 list comprehesion的if(拿來篩選) 是分開的，也就是說可以同時出現**
假設你有一個陣列`args = [1, 3, 5, 7, 8, 11]` 你想要把介於3~10的數字依照以下規則轉換，並塞入一個list中。
* 如果數字是奇數，把它減1
* 如果數字是偶數，把它加1
除了用`for-loop`+`if-else`，你還可以這樣寫
```python
args = [1, 3, 5, 7, 8, 11]
#小括號只是為了方便理解，沒一定要加
ans = [(ele+1 if ele%2==0 else ele-1) for ele in args if 3<= ele <=10]
ans = [ele^1 for ele in args if 3<= ele <=10] #其實也可以用位元運算
print(ans) #output: [2, 4, 6, 9]
```
6. **list comprehension裡面可以再放一個list comprehension**
假設你有一個二維陣列`A = [[1, 2, 3], [4, 5, 6]]`，你想要建立一個陣列B，內容和A一模一樣。你很任性不想用`.copy()`或是`for-loop`，就是想用list comprehension，你可以這樣寫:
_(對不起我知道這個例子超爛)_
```python
A = [[1, 2, 3], [4, 5, 6]]
row = 2
col = 3
B = [[A[r][c] for c in range(col)] for r in range(row)]
print(B) #output: [[1, 2, 3], [4, 5, 6]]
```
:::
<br>
> 程式碼 zip
```python=
import sys
def transpose(A):
AT = list(zip(*A))
return AT
for inp in sys.stdin:
row, column = map(int, inp.split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(row)]
ans = transpose(matrix)
for ele in ans: print(*ele)
```
_註1: `zip(*A)`意思: `*`拿來解包的用法請見[第一個程式碼的註解](#a015-1)。在這裡，`*`會先把二維陣列解包成多個一維陣列，再用`zip()`包起來。以達到轉置矩陣的目的。_
::: spoiler 例如: _(嘿舉例還是有點長 ~~今天幹話很多~~ ，有興趣的請自行點開來看)_
原本矩陣A長這樣
```python
A = [ [1, 2, 3], [4, 5, 6] ]
```
把A解包後會變成兩個陣列
```python
[1, 2, 3]
[4, 5, 6]
```
這個時候zip起來會變成一個zip物件，裡面長這樣 (zip物件裡裝的是tuple喔)
```python
(1, 4), (2, 5), (3, 6)
```
最後再用`list()`包起來就可以使用了。轉置矩陣AT:
```python
[(1, 4), (2, 5), (3, 6)]
```
:::
### C
> 程式說明
::: success
為了讓程式更清楚一點，寫了transpose函式，拿來讀取並轉置矩陣用
:::
> 程式碼
```c=1
#include <stdio.h>
void transpose(int A[100][100], int AT[100][100], int row, int column) {
for (int c = 0; c < column; c++) {
for (int r = 0; r < row; r++) {
AT[c][r] = A[r][c];
}
}
}
int main() {
int row, column;
int matrix[100][100], ans[100][100];
while(scanf("%d %d", &row, &column) != EOF){ //見註1
// 讀取輸入
for (int r = 0; r < row; r++) {
for (int c = 0; c < column; c++) {
scanf("%d", &matrix[r][c]);
}
}
// 轉置
transpose(matrix, ans, row, column); //見註2
// 輸出
for (int r = 0; r < column; r++) {
for (int c = 0; c < row; c++) {
printf("%d ", ans[r][c]);
}
printf("\n");
}
}
return 0;
}
```
_註1: C的`scanf()`會回傳它讀到了幾個東西，如果讀到檔案尾部(End-Of-File)，就會回傳`EOF`。這裡也可以寫成` while (scanf("%d %d", &row, &column) == 2) {`_
_註2: `transpose(matrix, ans, row, column);`: `matrix`, `ans`兩個原生陣列被當作參數傳入函式時，其實是傳入那兩個陣列的記憶體位址。所以transpose在修改`AT`的內容時，其實就是在修改main中`ans`的內容。 (C++也是喔)_
### C++
> 程式說明
::: success
為了讓程式更清楚一點，寫了transpose函式，拿來讀取並轉置矩陣用
:::
> 程式碼
```cpp=1
#include <iostream>
#include <vector> //想要用函式處理轉置+int**表示矩陣太麻煩=>用vector
using namespace std;
vector<vector<int>> transpose(vector<vector<int>> &A, int row, int column){
//先建立大小為column, row的陣列
vector<vector<int>> AT = vector<vector<int>>(column, vector<int>(row));
//轉置
for (int c=0; c<column; c++){
for (int r=0; r<row; r++){
AT[c][r] = A[r][c];
}
}
return AT;
}
int main(){
int row, column;
while (cin >> row >> column){
//讀取輸入
vector<vector<int>> matrix=vector<vector<int>>(row, vector<int>(column));
for (int r=0; r<row; r++) for (int c=0; c<column; c++) cin>>matrix[r][c];
//轉置
vector<vector<int>> ans = transpose(matrix, row, column);
//輸出
for (vector<int> &rows: ans){
for (int ele: rows){
cout << ele << ' ';
}
cout << endl;
}
}
return 0;
}
```
### Java
> 程式說明
::: success
為了讓程式更清楚一點，寫了transpose函式，拿來讀取並轉置矩陣用
:::
> 程式碼
```java=1
import java.util.Scanner;
public class Main{
private static int[][] transpose(int[][] A, int row, int column){
//先建立大小為column, row的陣列
int [][] AT = new int[column][row];
//轉置
for (int c=0; c<column; c++){
for (int r=0; r<row; r++){
AT[c][r] = A[r][c];
}
}
return AT;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){ //EOF處理
//讀取輸入
int row = scanner.nextInt();
int column = scanner.nextInt();
int[][] matrix = new int[row][column];
for (int r = 0; r < row; r++) {
for (int c = 0; c < column; c++) {
matrix[r][c] = scanner.nextInt();
}
}
//轉置
int[][] ans = transpose(matrix, row, column);
//輸出
for (int[] rows: ans){
for (int ele: rows){
System.out.print(ele+" ");
}
System.out.println();
}
}
scanner.close();
}
}
```
Sign in with Wallet
Connect another wallet