2017.10月大學程式設計先修檢測 實作題 第二題(交錯字串，Alternating Strings)

Python Code：

k=int(input())#輸入k值
s=input()#輸入交錯字串
prelow=None #前一個字元是小寫
upper=0#連續大寫的字元總數
low=0#連續小寫的字元總數
alterlen=0#目前的交錯的字串長度
longest=0#最長的交錯子字串長度
#處理第一個字元
if s[0].isupper()==True:
    prelow=False
    upper=1
    if k==1:
        alterlen=1
        longest=1
else:
    prelow=True
    low=1
    if k==1:
        alterlen=1
        longest=1

#處理第二個字元之後，大大
for i in range(1,len(s)):
    if (prelow==False and s[i].isupper()==True):
        upper+=1
        low=0
        if upper==k:
            alterlen+=k
            longest=max(alterlen,longest)
        if upper>k:alterlen=k
        
    elif (prelow==False and s[i].isupper()==False):#大小
        if upper<k:alterlen=0
        low=1
        upper=0
        if k==1:
            alterlen+=1
            longest=max(longest,alterlen)
        prelow=True
        
    elif (prelow==True and s[i].isupper()==True):#小大
        if low<k:alterlen=0
        upper=1
        low=0
        if k==1:
            alterlen+=1
            longest=max(alterlen,longest)
        prelow=False
            
    elif (prelow==True and s[i].isupper()==False):#小小
        low+=1
        upper=0
        if low==k:
            alterlen+=k
            longest=max(longest,alterlen)
        if low>k:
            alterlen=k
        

print(longest)

2017.10月大學程式設計先修檢測 實作題 第三題(樹狀圖分析)

Python Code：

2017.10月大學程式設計先修檢測 實作題 第四題(物品堆疊,Stacking)

問題描述
某個自動化系統中有一個存取物品的子系統，該系統是將N個物品堆在一個垂直的貨架上，每個物品各佔一層。系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。
每一次升高某些物品所需要消耗的能量是以這些物品的總重來計算，在此我們忽略貨架的重量以及其他可能的消耗。現在有N個物品，第i個物品的重量是w(i)而需要取用的次數為f(i)，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。舉例來說，有兩個物品w(1)=1、w(2)=2、f(1)=3、f(2)=4，也就是說物品1的重量是1需取用3次，物品2的重量是2需取用4次。我們有兩個可能的擺放順序(由上而下)：
 (1,2)，也就是物品1放在上方，2在下方。那麼，取用1的時候不需要能量，而每次取用2的能量消耗是w(1)=1，因為2需取用f(2)=4次，所以消耗能量數為w(1)*f(2)=4。
 (2,1)，也就是物品2放在1的上方。那麼，取用2的時候不需要能量，而每次取用1的能量消耗是w(2)=2，因為1需取用f(1)=3次，所以消耗能量數=w(2)*f(1)=6。
在所有可能的兩種擺放順序中，最少的能量是4，所以答案是4。再舉一例，若有三物品而w(1)=3、w(2)=4、w(3)=5、f(1)=1、f(2)=2、f(3)=3。假設由上而下以(3,2,1)的順序，此時能量計算方式如下：取用物品3不需要能量，取用物品2消耗w(3)*f(2)=10，取用物品1消耗(w(3)+w(2))*f(1)=9，總計能量為19。如果以(1,2,3)的順序，則消耗能量為3*2+(3+4)*3=27。事實上，我們一共有3!=6種可能的擺放順序，其中順序(3,2,1)可以得到最小消耗能量19。
輸入格式
輸入的第一行是物品件數N，第二行有N個正整數，依序是各物品的重量w(1)、w(2)、…、w(N)，重量皆不超過1000且以一個空白間隔。第三行有N個正整數，依序是各物品的取用次數f(1)、f(2)、…、f(N)，次數皆為1000以內的正整數，以一個空白間隔。
輸出格式
輸出最小能量消耗值，以換行結尾。所求答案不會超過63個位元所能表示的正整數。
範例一(第1、3子題)：輸入
2
20 10
1 1
範例一：正確輸出
10
範例二(第2、4子題)：輸入
3
3 4 5
1 2 3
範例二：正確輸出
19

Python Code：

參考資料：
https://henrybear327.github.io/CodingNotes/contest/apcs/1061028/

😌😌
原本的程式碼，在n>10會逾時，因為我的做法是找出所有的排列，再算出所有的energy，接著取最小值，這種做法是可以的，但是在n大的時候，效率就變差了~~~
網路上參考別人C語言的寫法，再利用泡沫排序法，可找到答案!!!

結論：大學與研究所時，怎麼沒去修演算法呢？

2017.10月大學程式設計先修檢測 實作題 第一題(邏輯運算子 Logic Operators)

邏輯運算子(Logic Operators)
問題描述
小蘇最近在學三種邏輯運算子 AND、OR和XOR。這三種運算子都是二元運算子，也就是說在運算時需要兩個運算元，例如a AND b。對於整數a與b，以下三個二元運算子的運算結果定義如下列三個表格：
舉例來說：
(1) 0 AND 0 的結果為0，0 OR 0 以及0 XOR 0 的結果也為0。
(2) 0 AND 3 的結果為0，0 OR 3 以及0 XOR 3 的結果則為1。
(3) 4 AND 9 的結果為1，4 OR 9 的結果也為1，但4 XOR 9的結果為0。
請撰寫一個程式，讀入a、b 以及邏輯運算的結果，輸出可能的邏輯運算為何。
輸入格式
輸入只有一行，共三個整數值，整數間以一個空白隔開。第一個整數代表a，第二個整數代表b，這兩數均為非負的整數。第三個整數代表邏輯運算的結果，只會是0 或1。
輸出格式
輸出可能得到指定結果的運算，若有多個，輸出順序為AND、OR、XOR，每個可能的運算單獨輸出一行，每行結尾皆有換行。若不可能得到指定結果，輸出IMPOSSIBLE。（注意輸出時所有英文字母均為大寫字母。）
範例一：輸入
0 0 0
範例一：正確輸出
AND
OR
XOR
範例二：輸入
1 1 1
範例二：正確輸出
AND
OR
範例三：輸入
3 0 1
範例三：正確輸出
OR
XOR
範例四：輸入
0 0 1
範例四：正確輸出
IMPOSSIBLE

Python 程式碼：
a,b,c=input().split()
a=int(a)
b=int(b)
c=int(c)
if a==0 and b==0 and c==0:
      print(" AND\n OR\n XOR\n")
elif a==0 and b==0 and c!=0:
      print("IMPOSSIBLE")
elif a==0 and b!=0 and c==0:
      print("AND")
elif a==0 and b!=0 and c!=0:
      print(" OR\nXOR")
elif a!=0 and b==0 and c==0:
      print("AND")
elif a!=0 and b==0 and c!=0:
      print(" OR\n XOR")
elif a!=0 and b!=0 and c==0:
      print("XOR")
elif a!=0 and b!=0 and c!=0:
      print(" AND\n OR")