第十二屆藍橋杯模擬賽Python組（第三期）

第一題

# 問題描述
# 　　請問在 1 到 2020 中，有多少個數與 2020 互質，即有多少個數與 2020 的最大公約數為 1，
# 答案提交
# 　　這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
co = 0
for i in range(1,2021):
    if i % 2 == 0 or i % 5 == 0 or i % 101 == 0:
        co += 1
print(2020-co)

答案：800

第二題

# 問題描述
# ASCII 碼將每個字符對應到一個數值（編碼），用于資訊的表示和傳輸，在 ASCII 碼中，英文字母是按從小到大的順序依次編碼的，例如：字母 A 編碼是 65, 字母 B 編碼是 66，字母 C 編碼是 67，請問字母 Q 編碼是多少？
# 答案提交
# 　　這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
print(ord('Q'))
'''
ord() 函式是 chr() 函式（對于8位的ASCII字串）或 unichr() 函式（對于Unicode物件）的配對函式，
它以一個字符（長度為1的字串）作為引數，回傳對應的 ASCII 數值，或者 Unicode 數值，如果所給的 Unicode 
字符超出了你的 Python 定義范圍，則會引發一個 TypeError 的例外，
'''

答案：81

第三題

n2 = 1000
n0 = n2 + 1         # 二叉樹最重要的性質
print(n0)

答案：1001

第四題

'''
問題描述
　　對于整數 v 和 p，定義 Pierce 序列為：
　　a[1] = v
　　a[i] = p % a[i-1]
　　例如，當 v = 8, p = 21 時，對應的 Pierce 序列為
　　a[1] = 8
　　a[2] = 5
　　a[3] = 1
　　再往后計算，值變為 0，不在我們考慮的范圍內，因此當 v = 8, p = 21 時， Pierce 序列的長度為 3，
　　當 p 一定時，對于不同的 v 值，Pierce 序列的長度可能不同，當 p = 8 時，若 1<=v<p，最長的 Pierce 序列出現在 v=13時，為(13, 8, 5, 1)，長度為 4，
　　當 p=2021 時，最長的 Pierce 序列出現在 v=1160 時，請問這個序列有多長？'''

def Pierce(p,v):
    a = []
    while v>0:
        for i in range(1,100):
            if i==1:
                a.append(v)
            else:
                if a[i-2]==0:
                    break
                else:
                    a.append(p%a[i-2])
                    v = a[i-1]
    a.pop()
    return a,len(a)
print(Pierce(2021,1160))

答案：12

第五題

# 問題描述
# 　　在 Excel 中，第 1 列到第 26 列的列名依次為 A 到 Z，從第 27 列開始，列名有兩個字母組成，第 27 列到第 702 列的列名依次為 AA 到 ZZ，
# 　　之后的列再用 3 個字母、4 個字母表示，
# 　　請問，第 2021 列的列名是什么？
dic = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q',
       'R','S','T','U','V','W','X','Y','Z']
a = []
for i in dic:
    for j in dic:           # 依次回圈迭代
        for v in dic:
            index = i + j + v
            a.append(index)
print(a[2021-702-1])        # 索引從0開始，所以要減一

答案：BYS

第六題

'''
問題描述
　　在書寫一個較大的整數時，為了方便看清數位，通常會在數位之間加上逗號來分割數位，具體的，從右向左，每三位分成一段，相鄰的段之間加一個逗號，
　　例如，1234567 寫成 1,234,567，
　　例如，17179869184 寫成 17,179,869,184，
　　給定一個整數，請將這個整數增加分割符后輸出，
輸入格式
　　輸入一行包含一個整數 v，
輸出格式
　　輸出增加分割符后的整數，
樣例輸入
1234567
樣例輸出
1,234,567
樣例輸入
17179869184
樣例輸出
17,179,869,184
資料規模和約定
　　對于 50% 的評測用例，0 <= v < 10^9 (10的9次方)，
　　對于所有評測用例，0 <= v < 10^18 (10的18次方)，
'''
v = int(input())
print('{:,}'.format(v))     # 逗號在這里表示千位分隔符
# 這是剛入門Python學的知識啊，考試的時候竟然沒想到

第七題

'''
問題描述
　　小藍正在寫一個網頁顯示一個新聞串列，他需要將總共 n 條新聞顯示，每頁最多可以顯示 p 條，請問小藍至少需要分多少頁顯示？
　　例如，如果要顯示2021條新聞，每頁最多顯示10條，則至少要分203頁顯示，
輸入格式
　　輸入的第一行包含一個整數 n，表示要顯示的新聞條數，
　　第二行包含一個整數 p，表示每頁最多可以顯示的條數，
輸出格式
　　輸出一個整數，表示答案，
樣例輸入
2021
10
樣例輸出
203
樣例輸入
2020
20
樣例輸出
101
資料規模和約定
　　對于所有評測用例，1 <= n <= 10000，1 <= p <= 100，
'''
n = int(input())    # 新聞條數
p = int(input())    # 顯示條數

if n%p == 0:
    count = n/p
else:
    count = n//p + 1
print(int(count))

第八題

'''
問題描述
　　雜貨鋪老板一共有N件物品，每件物品具有ABC三種屬性中的一種或多種，從雜貨鋪老板處購得一件物品需要支付相應的代價，
　　現在你需要計算出如何購買物品，可以使得ABC三種屬性中的每一種都在至少一件購買的物品中出現，并且支付的總代價最小，
輸入格式
　　輸入第一行包含一個整數N，
　　以下N行，每行包含一個整數C和一個只包含"ABC"的字串，代表購得該物品的代價和其具有的屬性，
輸出格式
　　輸出一個整數，代表最小的代價，如果無論如何湊不齊ABC三種屬性，輸出-1，
樣例輸入
5
10 A
9 BC
11 CA
4 A
5 B
樣例輸出
13
資料規模和約定
　　對于50%的評測用例，1 <= N <= 20
　　對于所有評測用例，1 <= N <= 1000， 1 <= C <= 100000
'''
n = int(input())
string = ['' for i in range(n)]
value = [0 for i in range(n)]

for i in range(n):
    temp = input().split()
    value[i] = int(temp[0])
    string[i] = temp[1]

def dfs(zifu,cost,index):
    min_cost = float('inf')
    if 'A' in zifu and 'B' in zifu and 'C' in zifu:
        return cost
    # if index>n:
    #     return float('inf')
    for i in range(index,n):
        print(''.join([zifu,string[i]]),cost+value[i],i+1)
        cost1 = dfs(''.join([zifu,string[i]]),cost+value[i],i+1)
        if cost1<min_cost:
            min_cost = cost1
    return min_cost

min_cost = dfs('',0,0)
print(min_cost)

第九題

'''
問題描述
　　給定一個矩陣 M，由 n 行 m 列組成，第 i 行第 j 列值為 M[i][j]，
　　定義矩陣 M 的重量為矩陣中所有元素的和，記為weight(M)
　　請找到矩陣左上角的一個子矩陣S（矩陣的前 r 行中的前 c 列組成），使得這個子矩陣的重量的兩倍最接近矩陣 M 重量，即 |2 weight(S)-weight(M)| 最小，
　　如果有多個子矩陣滿足條件，請找出面積 r * c 最小的一個，
　　如果仍然有多個子矩陣滿足條件，請找出其中 r 最小的一個，
輸入格式
　　輸入第一行包含兩個整數 n, m，表示矩陣的大小，
　　接下來 n 行，每行 m 個整數，表示給定的矩陣M，
輸出格式
　　輸出一行，包含兩個整數 r, c，表示子矩陣為矩陣 M 的前 r 行中的前 c 列，
樣例輸入
3 4
3 0 1 1
1 0 1 1
1 1 -2 4
樣例輸出
2 3
資料規模和約定
　　對于 30% 的評測用例，1 <= n, m <= 20, -10 <= M[i][j] <= 10，
　　對于 50% 的評測用例，1 <= n, m <= 100, -100 <= M[i][j] <= 100，
　　對于所有評測用例，1 <= n, m <= 1000, -1000 <= M[i][j] <= 1000，
'''
n,m = map(int,input().split())
dp = [[0]*m for i in range(n+1)]
value = []
weight = 0
for i in range(n):
    value.append(list(map(int,input().split())))
    weight += sum(value[i])
# print(dp)
# print(weight)
answer_value = float("inf")     # 初始化為無窮大
answer_area = float("inf")      # 初始化為正無窮
for r in range(1,n):
    for c in range(1,m):
        dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-1] + value[r][c]     # 二維前綴和
        differ = abs(2*dp[r][c] - weight)
        if (differ<answer_value and r*c<answer_area):
            answer = (r,c)
            answer_area = r*c
        else:
            answer = (r, c)
            answer_area = r * c

print(answer[0],answer[1])

第十題

n,k = map(int,input().split())
S = list(map(int,input().split()))
dp =[[0 for i in range(k+1)] for j in range(n+1)] #
for i in range(n):
    dp[i][1]  = 1   #將所有元素都有長度為1的遞增序列
for i in range(n):
    for j in range(i): 
        if(S[i]>S[j]):
            for l in range(2,k+1): #也就是在k的
                dp[i][l] = (dp[j][l-1]+dp[i][l]) % 1000007  #動規方程

maxvalue=0
for i in range(n):
    maxvalue = (maxvalue+dp[i][k])%1000007	#相加所有位
print(maxvalue)