總網頁瀏覽量

2018年4月25日 星期三

第三題:軍隊部署

問題描述
亞歷山大將軍準備派遣一支精銳部隊前往攻打鄰國,他麾下有三個種族 – 「人類」、
「骷髏族」和「哥布林族」;每個種族各有不同兵種,例如人類有騎士、法師、弓箭手,而
哥布林族有勇士、投矛手、吹箭手等等。
為了平衡部隊的組成份子,亞歷山大會從三個種族各選擇一個兵種。此外,他還會考慮
這個部隊是否能涵蓋「對空攻擊」、「範圍攻擊」和「遠距攻擊」三種特性。舉例來說,亞歷山大將軍麾下的三個種族各有三個兵種如下:

亞歷山大可以選擇法師、骷髏兵團和勇士這個組合,因為這個組合涵蓋了三個種族和三個特
性;但他不能選擇弓箭手、骷髏兵團和投矛手這個組合,因為這個組合未能涵蓋「範圍攻
擊」這個特性;他也不能選擇弓箭手、炸彈兵和炸彈塔這個組合,因為這個組合未能涵蓋
「哥布林」這個種族。
亞歷山大為這個問題想了很多天,國王感到很不解,這麼簡單的事情怎麼想那麼久。亞
歷山大為了向國王解釋,他想要告訴國王總共有多少種可能的組合,請你幫幫他。
輸入格式
第一列為一個正整數 N (1  N  10000),代表亞歷山大麾下有多少種兵種。接下來的 N
列,每一列有四個正整數 ci (ci  {1, 2, 3})、ai、ri 和 di (ai, ri, di  {0, 1}),彼此間以一個空
白隔開,分別代表種族、對空攻擊、範圍攻擊和遠距攻擊。ai、ri 和 di 的值若為 1,代表
具有該特性;否則,不具有該特性。
輸出格式
輸出共有多少個兵種組合可以涵蓋三個種族和三個特性。
Python Code:
n=int(input()) # 輸入兵種
x,y=[],[]
for i in range(n): # 輸入兵種、對空攻擊、範圍攻擊、遠距攻擊
    data=input().split(' ')
    x.append(data)
for i in range(n): # 將輸入的字串轉成數字
    x[i]=[int(p) for p in x[i]]

flag=0  # 合乎條件的組合加1
for i in range(n):
    if x[i][0]==1:
        for j in range(n):
            if x[j][0]==2:
                for k in range(n):
                    if x[k][0]==3:
                        if (x[i][1]+x[j][1]+x[k][1])>=1 and \
                        (x[i][2]+x[j][2]+x[k][2])>=1 and \
                        (x[i][3]+x[j][3]+x[k][3])>=1:
                            flag+=1
print(flag)

2018年4月20日 星期五

第二題:自戀數

問題描述
一個d 位數整數 𝑁 = n1n2n3...nd,ni ∈ {1,2,3,4,5,6,7,8,9,0}被稱為自戀數 (narcissistic
number) 若𝑁 = n1^d+n2^d+....+nd^d
例如3 位數整數153 是自戀數因為153=13+53+33,
而4 位數整數1321 不是自戀數因為14+34+24+14=99 非1321。
非十進位制數字也會有自戀數,例如3 進位制數字(122)3=17 且13+23+23=17,或5 進位
制數字(3134)5=419 且34+14+34+44=419。
請寫一個程式判斷一整數是否為自戀數。
輸入格式
第一列有兩個非負整數 𝑏 與 𝑁,代表 𝑁 為 𝑏 進位制整數。
輸出格式
若輸出之整數為自戀數,輸出YES,若否則輸出 NO。
評分說明
本題共有二個子題,每一子題可有多筆測試資料:
第一子題的測試資料 𝑏 = 10,𝑁 最大為 8 位數整數,全部解出可獲 83 分;
第二子題的測試資料 2 ≤ 𝑏 ≤ 10,𝑁 最大為 8 位數整數,全部解出可獲 17 分。
輸入範例1
10 153
輸出範例1
YES
輸入範例2
10 1321
輸出範例2
NO
輸入範例3
3 122
輸出範例3
YES
輸入範例4
5 3134
輸出範例4
YES

Python Code:
import math as lp
data=input() 
li=data.split() #輸入的字串,將之分開
n,x=[],[]
n=[int(x) for x in li] #將輸入的字串改成整數
b=n[0]
N=n[1] # N為b進位制整數
d=lp.floor(lp.log10(N))+1 # 取出N的位數 
for i in range(d): #取出N的各位數字
    ls=N%10
    x.append(ls)
    N//=10
s=0 # 計算每個數字的次方和
for j in range(d):
    s+=x[j]**d
ss=0 # 計算b進位制和
for k in range(d):
    ss+=x[k]*(b**(k))
if s==ss:
    print('YES')
else:

    print('NO')

第一題:連號或不連號

問題描述
生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近,因此在
不同的基因序列中如果都看見相同基因構成的連續片段 (順序不重要),這些基因構成的集合
就被認為是有意義的,稱為基因群 (gene cluster)。例如: 如果在一條基因序列上看到一個片段
內容為 (a, b, c, d),同時在另外一條基因序列上看到一個片段內容為 (d, b, a, c),那麼 {a, b,
c, d} 就構成一組基因群。
找出基因群並不是一件容易的工作,有一個計算生物學家想到一個聰明的方法來簡化這
個問題。經過他的簡化後,基因群辨識的主要工作會被轉換成: 輸入一個由相異正整數組成的
序列 S,然後判斷 S 的內容是否構成連續的一串整數。例如: S = (2, 5, 3, 4) 的內容構成連續
的一串整數 2, 3, 4, 5;但是 S = (2, 6, 3, 4) 的內容並不構成連續的一串整數 (缺了 5)。
給定一個數字所構成的序列,請撰寫一個程式來判斷這個序列中的數字是否構成連續的
一串整數。
輸入格式
測試資料是由一行的數字所構成 (數字間以一個以上的空白隔開),第一個數字 n 表示
所給定數字序列的長度,1 < n  100,接下來會有 n 個相異的正整數 mi,1  i  n 且 1  mi
 1000,表示數字序列的內容。
輸出格式
輸出一行,如果此序列中的數字構成連續的一串整數,請輸出: a b yes;不行則輸出: a b
no,其中 a 和 b 分別代表序列中所有數字的最小值與最大值。a 和 b 之間以及 b 和 yes/no
之間,請以剛好一個空白隔開。(yes/no 請用小寫)

第一子題 輸入範例1
2 6 5
第一子題 輸出範例1
5 6 yes
第一子題 輸入範例2
2 5 7
第一子題 輸出範例2
5 7 no
2
第二子題 輸入範例1
3 9 8 7
第二子題 輸出範例1
7 9 yes
第二子題 輸入範例2
3 10 9 7
第二子題 輸出範例2
7 10 no
第三子題 輸入範例1
5 2 3 4 5 6
第三子題 輸出範例1
2 6 yes
第三子題 輸入範例2
5 2 3 4 5 7
第三子題 輸出範例2
2 7 no

Python Code:
data=input()  # 輸入數字序列長度n與n個相異正整數
li=data.split()  # 輸入的字串,將之分開
s,t,u=[],[],[]
s=[int(x) for x in li]  # 將輸入的字串改成正整數
for i in range(1,len(s)):
    t.append(s[i])  # 列表t存放這n個相異正整數
u=sorted(t)  # 將n個相異正整數由小到大排列
M=max(u)  # 取出u的最大值
m=min(u)  # 取出u的最小值
if M-m==len(u)-1:
    print(m,M,'yes')
else:
    print(m,M,'no')

2018年4月13日 星期五

分堆問題

「分堆問題」到底何時要除(乘),又要除(乘)多少呢?
統整「分堆問題」如下~~~
Q:8本不同的書,求下列的分法數?
      (1)平分成2堆     
      (2)平分給甲乙2人
      (3)分成4本,3本,1本三堆   
      (4)分給3人,其中1人4本,1人3本,1人1本
      (5)甲得4本,乙得3本,丙得1本
      (6)分成4本,2本,2本三堆
      (7)分給3人,其中1人4本,1人2本,1人2本
      (8)甲得4本,乙得2本,丙得2本

口訣:先分堆,再分人,有指定,不要動

解答:
      

     

爬樓梯與費氏數列

現在高一講到排列組合,在爬樓梯的題目中,它是跟費氏數列有關係的~~~(用這種解法,學生似乎比較容易做對)

Q:樓梯有8階,每步可爬1階或2階,則共有多少種不同的上

       樓方法?
解:(利用費氏數列)
       若樓梯只有1階,f(1)=1(一種走法)
       若樓梯只有2階,f(2)=2(一次走2階或走2步1階)
       費氏數列~~~f(n)=f(n-1)+f(n-2)
       1,2,3,5,8,13,21,34,所以f(8)=34種上樓法
       解釋
       爬到第n階的上樓法會等於爬到第(n-1)階,再爬1階加上爬
       到第(n-2)階再爬2階(不能爬2次1階的,因為會回到f(n-1))
       ,所以f(n)=f(n-1)+f(n-2)

       同理,改成每步爬1階或2階或3階,則費氏數列會變成

       f(n)=f(n-1)+f(n-2)+f(n-3)