---
# System prepended metadata

title: APCS實作練習解析

---


# Zerojudge實作詳解

**詳解連結：** [a054](https://hackmd.io/@oateacher/a054)
**詳解連結：** [a020](https://hackmd.io/@oateacher/a020)
**詳解連結：** [a065](https://hackmd.io/@oateacher/a065)
**詳解連結：** [a524](https://hackmd.io/@oateacher/a524)
**詳解連結：** [c317](https://hackmd.io/@oateacher/c317)
**詳解連結：** [c657](https://hackmd.io/@oateacher/c657)
**詳解連結：** [d097](https://hackmd.io/@oateacher/d097)
**詳解連結：** [d478](https://hackmd.io/@oateacher/d478)
**詳解連結：** [e566](https://hackmd.io/@oateacher/e566)
**詳解連結：** [a417](https://hackmd.io/@oateacher/a417)
**詳解連結：** [a468](https://hackmd.io/@oateacher/a468)



**題號：** a001
**名稱：** 哈囉
**說明：** 撰寫一個程式可以讀入指定的字串，並輸出另一個指定的字串

**測資：**
![image](https://hackmd.io/_uploads/B1dVuACET.png)


**程式碼(參考)：**
 ```javascript
# a001 使用連續 IPO 輸出入資料練習
    import sys

    for s in sys.stdin:
        print("hello, "+s)
```

**題號：** a002
**名稱：** 簡易加法
**說明：** 此題目需要輸入兩個數字，最後輸出兩個數字的總和
**測資：**
![image](https://hackmd.io/_uploads/Hk88dARNp.png)



**程式碼(參考)：**
 ```javascript
    import sys

    #start
    for s in sys.stdin:
        data = s.split()
        number = int(data[0])+int(data[1])
        print(number)
```
    
**題號：** a003
**名稱：** 兩光法師占卜術
**說明：** 
* 題目的占卜術能夠輸入一個日期並依照公式後換算得到三種結果 (普通、吉、大吉)
* 換算的公式如下:
M=月
D=日
S=(M*2+D)%3

**測資：**
![image](https://hackmd.io/_uploads/Skb_OACET.png)




**程式碼(參考)：**
 ```javascript
import sys

for s in sys.stdin:
    nums = [ int(i) for i in s.split() ]
    M = nums[0]
    D = nums[1]
    S = (M*2+D)%3
    if S==0:
        print("普通")
    elif S==1:
        print("吉")
    else:
        print("大吉")
```

**題號：** a004
**名稱：** 文文的求婚
**說明：** 
* 整理題目說明可以發現此題是閏年問題，給定一個年份，請依照閏年的檢查方法判斷是否為閏年
* 提示 ：
 西元年被4整除且不被100整除，或被400整除者即為閏年
 使用 cin , cout 來進行輸入輸出


**測資：**
![image](https://hackmd.io/_uploads/H1EoOC0Ea.png)





**程式碼(參考)：**
 ```javascript
while True:
   try:
      year = int(input())

      if year%4 == 0 and year%100 !=0:
          print("閏年")
      elif year%400 == 0:
          print("閏年")
      else:
          print("平年")
   except:
      break
```
**題號：** a005
**名稱：** Eva 的回家作業
**說明：** Eva的家庭作業裏有很多數列填空練習。填空練習的要求是：已知數列的前四項，填出第五項。因 為已經知道這些數列只可能是等差或等比數列，她決定寫一個程式來完成這些練習。


**測資：**
![image](https://hackmd.io/_uploads/Bk7vK8NB6.png)





**程式碼(參考)：**
 ```javascript
import sys

#start
t= int(input())

for i in range(t):
    seq = list(map(int, input().split()))

    isArithmetic = False
    isGeometric = True

    # 判斷等差
    diff1 = seq[1]-seq[0]
    diff2 = seq[2]-seq[1]
    diff3 = seq[3]-seq[2]

    if diff1 == diff2 and diff2 == diff3:
        isArithmetic = True

    diff = int(seq[3]/seq[2]);

    # 判斷等比
    for i in range(0, 3+1):
        if seq[i]%diff != 0:
            isGeometric = False
            break

    if isArithmetic == True:
        diff = diff1
        for i in range(4):
            print(seq[i], end=' ')
        print(seq[3]+diff)
    else:
        for i in range(4):
            print(seq[i], end=' ')
        print(seq[3]*diff)
```

**題號：** a009
**名稱：** 解碼器
**說明：** 
* 在密碼學裡面有一種很簡單的加密方式，就是把明碼的每個字元加上某一個整數K而得到密碼的字元（明碼及密碼字元一定都在ASCII碼中可列印的範圍內）。例如若K=2，那麼apple經過加密後就變成crrng了。解密則是反過來做。這個問題是給你一個密碼字串，請你依照上述的解密方式輸出明碼。至於在本任務中K到底是多少，請自行參照Sample Input及Sample Output推出來吧！相當簡單的。
* 提示 ：
cin.get(char) 可一次讀取一個字元
getline(cin, string) 可一次讀取完整的一行
中文翻譯 Lucky Cat


**測資：**
![image](https://hackmd.io/_uploads/r1t0A8VHp.png)






**程式碼(參考)：**
 ```javascript
import sys

for s in sys.stdin:
    data = list(s)

    for i in range(len(data)):
        t = ord(data[i])
        print(chr(t-7), end='')
    print()
```

**題號：** a024
**名稱：** 最大公因數(GCD)(註：先備知識-輾轉相除法)
**說明：** 
* 給定兩個整數，請求出它們的最大公因數
* 提示 ：
GCD 數學 最大公因數 迴圈


**測資：**
![image](https://hackmd.io/_uploads/rJh-J2NHT.png)

**程式碼(參考)：**
 ```javascript
def GCD(a, b):
    if a<b:
        a, b = b, a

    while True:
        if(b != 0):
            c= int(a%b)
            a = b
            b= c
        else:
            break

    return a


#start
s = input()
data = s.split()

a = int(data[0])
b = int(data[1])

r = GCD(a, b)

print(r)
```


**題號：** C295(作業-Hard)
**名稱：** 求和
**說明：** 
* 給定N群數字，每群都恰有M個正整數。若從每群數字中各選擇一個數字 (假設第 i群所選出數字為ti)，將所選出的N個數字加總即可得和 S = t1+t2+…+ +…+ tN。請寫程式計算 S的最大值 (最大總和 )，並判斷各群所選出的數字是否可以整除 S。
* 提示 ：
（範例一說明） 挑選的數字依序是 5, 6, 1，總和S=12。而此三數中可整除S的是 6與 1，6在第二群，1在第3群所以先輸出6再輸出1。注意，1雖然也出現在第一群，但她不是第一群中挑出的數字，所以順序是先 6後 1。
（範例二說明） 挑選的數字依序是6,9,7,9，總和 S= 31 。而此四數中沒有可整除 S的， 所以第二行輸出 -1。

* 評分說明：輸入包含若干筆測試資料，每一的執行時間限制 (time limit)均為 1秒，依正確通過測資筆數給分。 其中：

    第 1子題組 20 分： 1≦ N ≦ 20 ，M = 1。
    第 2子題組 30 分： 1≦ N ≦ 20 ，M = 2。
    第 3子題組 50 分： 1≦ N ≦ 20 ，1≦ M ≦ 20 。


**測資：**
![image](https://hackmd.io/_uploads/SJJCrUEBp.png)




**程式碼(參考)：**
 ```javascript
#
# c295: 最大和
#

while True:
    try:
        #start
        s1 = input()
        s1 = list(map(int, s1.split()))

        N = s1[0]
        M = s1[1]

        # data 為二維串列結構
        data = []

        for i in range(0, N):
            # 每次讀取一橫排資料, 轉成 row 串列, 接著加入 data 串列
            s2 = input()
            row = list(map(int, s2.split()))
            data.append(row)

        # 使用 i, j 變數直接存取單一元素的工具, 此段可刪除
        #for i in range(0, N):
        #    for j in range(0, M):
        #        print(data[i][j], end=' ')
        #    print()

        S = 0
        maxvalue = []
        
        for i in range(0, N):
            # 每組 row 之間的資料, 經排序後最後一個元素為最大值
            data[i].sort()
            S = S+ data[i][M-1]
            maxvalue.append(data[i][M-1])

        print(S)

        divisor_count =0
      
        for i in range(0, N):
            if S%maxvalue[i] == 0:
                divisor_count +=1
                print(maxvalue[i], end=' ')
        if divisor_count == 0:
            print("-1")
        else:
            print()

    except:
        break

```

**題號：** c462
**名稱：** apcs 交錯字串
**說明：** 
* 問題描述
一個字串如果全由大寫英文字母组成,我們稱為大寫字串;如果全由小寫字母组成則稱為小寫字串。字串的长度是它所包含字母的個數,在本题中,字串均由大小寫英文母組成假設k是一個自然數,一個字串被稱為「k-交錯字串」,如果它是由長度為k的大寫字串與長度為k的小寫字串交錯串接組成。舉例來說,「StRiNg」是一個1-交錯字,因為它一個大寫一個小寫交替出現;而「heLLow」是一個2-交錯字串,因為它是兩個小寫接兩個大寫再接兩個小寫。但不管k是多少,「aBBaaa」、「BaBaBB」、「aaaAAbbCCCC」都不是k-交錯字串。本題的目標是對於給定k值,在一個輸入字串找出最長一段連續子字串滿足k-交錯字串的要求。例如k=2且輸入「aBBaaa」,最長的k-交錯字串是「BBaa」,長度為4。又如k=1且輸入「BaBaBB」,最長的k-交錯字串是「BaBaB」,長度為5。
請注意,滿足條件的子字串可能只包含一段小寫或大寫字母而無交替,如範例二。此外,也可能不存在滿足條件的子字串,如範例四。
* 提示 ：
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為1秒，依正確通過測資筆數給分。
其中：
    第1子題組20分，字串長度不超過20且k=1。
    第2子題組30分，字串長度不超過100且k ≤ 2。
    第3子題組50分，字串長度不超過100,000且無其他限制。


**測資：**
![image](https://hackmd.io/_uploads/HJ7LIVSup.png)




**程式碼(參考)：**
 ```javascript
#
# c462 交錯字串
#

while True:
    try:
        #start
        K = int(input())
        string = input()

        upper = 0 #紀錄字串中，大寫數量
        lower = 0 #紀錄字串中，小寫數量

        lenTemp = 0 #目前找到的K-string長度
        maxLen = 0 #最長的K-string

        prevChar = '' #upper/lower

        if string[0].isupper() == True:
            prevChar = 'u'
            upper = 1
            
            if K == 1:
                lenTemp = K
                maxLen = lenTemp
        else:
            prevChar = 'l'
            lower = 1
            if K == 1:
                lenTemp = K
                maxLen = lenTemp


        for i in range(1, len(string)):
            # 大 -> 大
            #累加(if K>1)
            if string[i].isupper() and prevChar == 'u':
                upper += 1
                lower = 0

                if upper == K:
                    lenTemp += K
                    maxLen = max(lenTemp, maxLen)

                if upper > K:
                    #EX AAA,2string==>lenTemp=2
                    #EX aaAAA,2string==>lenTemp=2
                    lenTemp = K
            
            # 小 -> 小
            #累加(if K>1)
            elif string[i].islower() and prevChar == 'l':
                upper = 0
                lower +=1

                if lower == K:
                    lenTemp += K
                    maxLen = max(lenTemp, maxLen)

                if lower > K:
                    lenTemp = K

            # 小 -> 大
            elif prevChar == 'l' and string[i].isupper():
                if lower < K:
                    lenTemp = 0

                upper = 1
                lower = 0
                
                if K == 1:
                    lenTemp += K
                    maxLen = max(lenTemp, maxLen)

                prevChar = 'u'

            # 大 -> 小
            elif prevChar == 'u' and string[i].islower():
                if upper < K:
                    ## AAAaa 2string
                    lenTemp = 0

                upper = 0
                lower = 1
                
                if K == 1:
                    lenTemp += K
                    maxLen = max(lenTemp, maxLen)

                prevChar = 'l'

        print(maxLen)
    except:
        break

```

**題號：** c636
**名稱：** 12生肖
**說明：** 
* 民國元年 ( 1912 ) 是鼠年。
給定若干個民國年份   -100 ~ 107
請輸出該年生肖為何。
* 提示 ：
array number 餘數


**測資：**
![image](https://hackmd.io/_uploads/SkJ40jNrT.png)







**程式碼(參考)：**
 ```javascript
import sys

sign = ["鼠", "牛", "虎", "兔", "龍",
        "蛇", "馬", "羊", "猴", "雞",
        "狗", "豬"]

#start
for s in sys.stdin:
    year = int(s)

    if year>0:
        if year%12==0:
            print(sign[11])
        else:
            index = year%12-1
            print(sign[index])

    elif year<0:
        abs_year = abs(year)
        if abs_year%12==0:
            print(sign[0])
        else:
            index = 12-abs_year%12
            print(sign[index])
```

**題號：** e447
**名稱：** queue 練習
**說明：** 
* 請你實作queue相關的幾個基本操作：
    在隊伍尾端加入元素。
    輸出隊伍最前端的元素。
    刪除隊伍最前端的元素。

* 提示 ：



**測資：**
![image](https://hackmd.io/_uploads/S16_ON1I6.png)



**程式碼(參考)：**
 ```javascript
queue = []
MAX_SIZE = 100

def enqueue(data):
    queue.append(data)

def dequeue():
    data = queue.pop(0)
    return data

def isFull():
    if len(queue) == MAX_SIZE:
        return True
    else:
        return False

def isEmpty():
    if len(queue) == 0:
        return True
    else:
        return False

def front():
    return queue[0]

def rear():
    return queue[len(queue)-1]

#start
N = int(input())

for i in range(N):
    s = input()
    data = [ int(x) for x in s.split() ]

    if data[0] == 1:
        enqueue(data[1])

    elif data[0] == 2:
        if isEmpty() == True:
            print(-1)
        else:
            print(front())

    elif data[0] == 3:
        if isEmpty() == False:
            dequeue()


```

**題號：** f312
**名稱：** 人力分配
**說明：** 
![image](https://hackmd.io/_uploads/SkbwFoCu6.png)



**測資：**![image](https://hackmd.io/_uploads/Bk4YFsAdT.png)




**程式碼(參考)：**
 ```javascript
#
# f312 人力分配
#

#start
a1, b1, c1 = map(int, input().split())
a2, b2, c2 = map(int, input().split())

n = int(input())

max_benfit = -1000000

for x in range(0, n+1):
    x1 = x
    x2 = n-x1
    
    y1 = a1*x1*x1+b1*x1+c1
    y2 = a2*x2*x2+b2*x2+c2

    Y = y1+y2
    #print(x1, x2, Y)
    if Y > max_benfit:
        max_benfit = Y

print(max_benfit)
```

**題號：** f313
**名稱：** 人口遷移
**說明：** 
![image](https://hackmd.io/_uploads/H14vqoAdT.png)





**測資：**![image](https://hackmd.io/_uploads/SyZmqsAup.png)





**程式碼(參考)：**
 ```javascript
#
# f313 人口遷移
#

def show_population(arr, R, C):
    for i in range(R):
        for j in range(C):
            print(arr[i][j], end=' ')
        print()


#        ( 0,-1)
# (-1, 0)( 0, 0)( 1, 0)
#        ( 0, 1)

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#start
R, C, k, m = map(int, input().split())

population = []
move_per_day = [ [ 0 for i in range(C)] for j in range(R) ]

for i in range(R):
    row = list(map(int, input().split()))
    population.append(row)

idx = 1
while idx <= m:
    
    # 遷出人口
    for i in range(R):
        for j in range(C):
            now_move = population[i][j]//k
            #print("%d, %d, now move=%d" % (i, j, now_move))
            direction = 0

            if now_move > 0:
                for c in range(4):
                    now_c = j+dx[c]
                    now_r = i+dy[c]
                    #print(now_r, now_c)

                    if (0 <= now_c < C) and (0 <= now_r < R):
                        #print(now_r, now_c, population[now_r][now_c])
                        if population[now_r][now_c] != -1:
                            direction += 1
                            move_per_day[now_r][now_c] += now_move

            
            population[i][j] -= now_move*direction

    #show_population(move_per_day, R, C)

    # 遷入移動人口
    for i in range(R):
        for j in range(C):
            population[i][j] += move_per_day[i][j]

    #reset 移動量
    move_per_day = [  [ 0 for i in range(C)] for j in range(R) ]

    #show_population(population, R, C)
    
    idx += 1

#show_population(population, R, C)
max_p = 0
min_p = 100

for i in range(R):
    for j in range(C):

        if population[i][j] != -1:
            max_p = max(max_p, population[i][j])
            min_p = min(min_p, population[i][j])

print(min_p)
print(max_p)
```



**題號：** f579
**名稱：** 購買力
**說明：** 
* 給兩個整數a、b 代表你要觀察的商品編號。商場在每一位客人的購物車都放置了一個感應器，能夠得知每位客人將商品放入購物車或拿出購物車。感應器存放的紀錄是一連串的整數，一個正整數x表示這位客人將一個編號是x的商品放入他的購物車，一個負數-x表示這位客人將一個編號是x的商品從他的購物車移除。現在有n 位客人的購物車紀錄，你想要統計有幾位客人最後有購買商品a與商品b，一個客人有購買商品x表示商品x在他的購物車中放入的次數比拿出還多。

* 提示 ：



**測資：**![image](https://hackmd.io/_uploads/rJjVG4Sd6.png)
![image](https://hackmd.io/_uploads/rklUMES_p.png)






**程式碼(參考)：**
 ```javascript
#
# f579 購買力
#

a, b = map(int, input().split())

n = int(input())

num = 0

for i in range(n):
    record = list(map(int, input().split()))

    buy_A = 0
    buy_B = 0

    for x in range(len(record)):
        if record[x] > 0:
            if record[x] == a:
                buy_A += 1
                
            if record[x] == b:
                buy_B += 1

        elif record[x] < 0:
            if abs(record[x]) == a:
                buy_A -= 1

            if abs(record[x]) == b:
                buy_B -= 1

    if buy_A>0 and buy_B>0:
        num += 1

print(num)

```

**題號：** g275
**名稱：** 七言對聯
**說明：** 
* 中文依照發音方式可以分為平聲與仄聲，假設我們把平聲標記為1、而仄聲標記為0、一個七言對聯包含兩個句子，每個句子包含恰好七個字。


*   七言對聯有三個限制：
    A: 二四不同二六同：每一句第二、四個字必須不同平仄，而第二、六個字必須相同平仄
    B: 仄起平收：第一句的結尾必須為仄聲，第二句的結尾必須為平聲
    C: 上下相對：第一、二句的第二、四、六個字平仄必須不同


* 給你n 組對聯，分別用0，1代表平仄，請輸出它違反了哪幾條規則
  若以上規則皆無違反，請輸出None 
* 提示 ：



**測資：**
![image](https://hackmd.io/_uploads/B1fxg4SOT.png)
)



**程式碼(參考)：**
 ```javascript
#
# g275: 七言對聯
#
# 0: 平聲
# 1: 仄聲

#start
n = int(input())

for i in range(n):
    p1 = list(map(int, input().split()))
    p2 = list(map(int, input().split()))

    violation = 0
    
    #A
    if p1[1] != p1[3] and p2[1] != p2[3]:
        if p1[1] == p1[5] and p2[1] == p2[5]:
            pass
        else:
            violation += 1
            print("A", end='')
    else:
        violation += 1
        print("A", end='')
    
    #B
    if p1[6] == 1 and p2[6] == 0:
        pass
    else:
        violation += 1
        print("B", end='')
    
    #C
    if (p1[1]+p2[1]) == 1 and (p1[3]+p2[3]) == 1 and (p1[5]+p2[5]) == 1:
        pass
    else:
        violation += 1
        print("C", end='')
    
    if violation >0:
        print()
    else:
        print("None")

```



**題號：** h081
**名稱：** 程式交易
**說明：** 
![image](https://hackmd.io/_uploads/BJbp5iCOa.png)




**測資：**
![image](https://hackmd.io/_uploads/BygAqoA_6.png)

**提示：**
![image](https://hackmd.io/_uploads/rk2xsjR_T.png)


**程式碼(參考)：**
 ```javascript
#
# h081: 程式交易
#

#start
n, D = map(int, input().split())

prices = list(map(int, input().split()))

x=0
haveStock = False
benfit = 0

for i in range(n):
    #print(x, prices[i], benfit)
    if x==0 or (prices[i] <= (x-D) and haveStock == False):
        x = prices[i]
        haveStock = True
    if prices[i] >= (x+D) and haveStock == True:
        benfit += prices[i]-x
        x = prices[i]
        haveStock = False

print(benfit)

```



**題號：** i213
**名稱：** stack 練習
**說明：** 
* 請你實作stack相關的幾個基本操作：
    在堆疊頂端加入元素。
    輸出堆疊最頂端的元素。
    刪除堆疊最頂端的元素。
* 提示 ：



**測資：**
![image](https://hackmd.io/_uploads/HJHluE18p.png)


**程式碼(參考)：**
 ```javascript
#
# i213: stack 練習
#

stack = []

def push(data):
    stack.append(data)

def pop():
    r = stack.pop()
    return r

def top():
    now_size = len(stack)
    t = stack[now_size-1]
    return t

def size():
    print(len(stack))

def empty():
    if len(stack) == 0:
        return True
    else:
        return False

#start
N = int(input())

for i in range(N):

    row = list(map(int, input().split()))

    if len(row) == 1:
        k = row[0]
    else:
        k = row[0]
        d = row[1]
    
    if k == 1:
        push(d)
    elif k == 2:
        if empty() == True:
            print(-1)
        else:
            print(top())
    elif k == 3:
        if empty() == False:
            pop()


```

**題號：** i400
**名稱：** 字串解碼
**說明：** 
![image](https://hackmd.io/_uploads/SymLooAua.png)

**測資：**
![image](https://hackmd.io/_uploads/ByV_soCOT.png)

* 提示 ：

範例測資一，如題目所述
範例測資二過程如下
e = 111110，
 出現的數量為奇數次，因此需要將字串 "QWERTY" 切半翻轉成 "RTYQWE"，經過 01 字串的轉換後會得到 "EWQYTR"。
e = 101101，
 出現的數量為偶數次，因此不用翻轉字串，經過 01 字串的轉換後會得到 "RETYWQ"。
e = 000000，
 出現的數量為偶數自，因此不用翻轉字串，經過 01 字串的轉換後會得到 "RETYWQ"。








**程式碼(參考)：**
 ```javascript
#
# i400: 字串解碼
#
def step2(T, ei, n):
    tString = ""

    T = list(T)

    for dx in range(n-1, -1, -1):
        if ei[dx] == '0':
            tString = T[len(T)-1] + tString
            #print("R, ", end=' ')
        else:
            tString = tString + T[len(T)-1]
            #print("F, ", end=' ')

        T.pop()
        #print(T, tString)
    return tString


def step1(T, ei, n):
    checkE = 0
    for i in ei:
        if i == '1':
            checkE += 1

    if checkE%2 == 0:
        return T
    else:
        if n%2 == 0:
            subT1 = T[0:n//2]
            subT2 = T[n//2:n]
            #print(subT2, subT1)

            return subT2+subT1
        else:
            subT1 = T[0:n//2]
            mid = T[n//2]
            subT2 = T[n//2+1:n]
            #print(subT2, mid, subT1)
            
            return subT2+mid+subT1

#start
m, n = map(int, input().split())

e = []

for i in range(m):
    encode = list(input())
    e.append(encode)

T = input()

S = ""

temp = T

for i in range(m-1, -1, -1):
    temp = step2(temp, e[i], n)
    #print(temp)
    temp = step1(temp, e[i], n)
    #print(temp)

print(temp)

```





# **回家作業挑戰題詳解**

**題號：** 9-5挑戰題
**名稱：** 解碼器(參考Zerohudge-a009)
**說明：** 
![image](https://hackmd.io/_uploads/ryYVvINra.png)




**程式碼(參考)：**
 ```javascript
import sys

#start
for s in sys.stdin:
    data = s.split()
    code = data[0]
    K = int(data[1])

    decode = ""
    for i in range(len(code)):
        value = ord(code[i]) + K
        decode += chr(value)

    print(decode)

```