【思特奇杯·云上蓝桥-算法集训营】“思特奇杯”编程之星初赛

【思特奇杯·云上蓝桥-算法集训营】“思特奇杯”编程之星初赛

试题A：门牌制作

答案：624

count = 0
for i in range(1, 2021):
    n = i
    while n != 0:
        m = n % 10
        n = n // 10
        if m == 2:
            count += 1
print(count)

试题B：寻找2020

答案：2481215

def check(s):
    return s == '2020'
matrix = []
s = input()
while '1' not in s:
    matrix.append(list(s))
    s = input()
n,m = len(matrix),len(matrix[0])
ans = 0
for i in range(n):
    for j in range(m):
        if i + 3 < n and check(matri[i][j] + matrix[i+1][j] + matrix[i+2][j] + matrix[i+3][j]):
            ans += 1
        if j + 3 < m and check(matrix[i][j:j+4]):
            ans += 1
        if i + 3 < n and j + 3 < m and check(matri[i][j] + matrix[i+1][j+1] + matrix[i+2][j+2] + matrix[i+3][j+3]):
            ans += 1
print(ans)

试题C：跑步锻炼

答案：8879

import datetime
distances = 0
start_time = datetime.datetime(year=2000, month=1, day=1)  # 2000年1月1日00：00 周六
dela = datetime.timedelta(days=1)
end_time = datetime.datetime(year=2020, month=10, day=1)  # 到2020年10月2日00：00 这样包括10月1号 周四
time = end_time - start_time  # time为一个timedelta对象
# start_time.weekday() 返回数字0-6，0代表星期一，依次类推  5 代表星期六
while start_time <= end_time:
    if start_time.day == 1 or start_time.weekday()  == 0:
        # 月初或周一
        distances += 2
    else:
        distances += 1
    start_time += dela
print(distances)

试题D：蛇形填数

答案：761

i = 0
j = 0
num = 0
while True:
    num += 1
    if i == 19 and j == 19:
        break
    if (i+j)&1:
        i += 1
        if j > 0:
            j -= 1
    else:
        j += 1
        if i > 0:
            i -= 1
print(num)
    

试题E：排序

答案：100

def bubble_sort(arr):
    num = 0
    for i in range(len(arr)-1,0,-1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                num += 1
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return num
print(bubble_sort(list('jonmlkihgfedcba')))

试题F：成绩统计

n = int(input())
num1 = 0
num2 = 0
for _ in range(n):
    score = int(input())
    if score >= 60:
        num1 += 1
    if score >= 85:
        num2 += 1
print(str(round(num1*100/n))+'%')
print(str(round(num2*100/n))+'%')

试题G：单词分析

cnt = [0]*26
s = input()
for alpha in s:
    cnt[ord(alpha) - ord('a')] += 1
k = 0
for i in range(26):
    if cnt[i] > cnt[k]:
        k = i
print(chr(k+ord('a')))
print(cnt[k])

试题H：数字三角形

n = int(input())
matrix = [[0]*( _ + 1 ) for _ in range(n)]
for i in range(n):
    tmp = [int(a) for a in input().split(' ')]
    matrix[i] = tmp
dp = matrix[:]
for i in range(1,n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] += dp[i-1][j]
        elif j == i:
            dp[i][j] += dp[i-1][j-1]
        else:
            dp[i][j] += max(dp[i-1][j],dp[i-1][j-1])
if n&1:
    print(dp[n-1][n//2])
else:
    print(max(dp[n-1][n//2-1],dp[n-1][n//2]))

试题I：平面切分

n = int(input())
line = []
for _ in range(n):
    tmp = [int(a) for a in input().split(' ')]
    line.append(tuple(tmp))
line = list(set(line)) 
n = len(line)
judge = lambda pos1,pos2 : abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) < 1e-12 
ans = 2
for i in range(1,n):
    k1,b1 = line[i]
    sec = []
    for j in range(i):
        k2,b2 = line[j]
        if k2 == k1: continue
        pos_x = (b2-b1)/(k1-k2); pos_y = k1*pos_x + b1  
        sec.append((pos_x,pos_y))
    m = len(sec)
    tmpans = m+1
    if m < 2:
        ans += tmpans
        continue
    sec = sorted(sec,key=lambda x:x[0]) 
    for i in range(1,m):
        if judge(sec[i-1],sec[i]):
            tmpans -= 1  
    ans += tmpans
print(ans)
    
        

试题J：装饰珠

def eliminate(bead, max_dic):  
    for i in bead:
        if i[1] > max_dic[i[0]]:
            for _ in range(i[1] - max_dic[i[0]]):
                i.pop()
                i[1] -= 1
    if len(bead[-1]) == 2:  
        res = bead.pop()[0]
        del dic[res]
        del max_dic[res]
    # print(bead)


N = []
for i in range(6):
    N.append(list(map(int, input().split())))
dic = {}  
max_dic = {}  
for i in N:
    for j in i[1:]:
        if j in dic:
            dic[j] += 1
            max_dic[j] += 1
        else:
            dic[j] = 1
            max_dic[j] = 1
# print(dic)

for i in range(max(dic) - 1, 0, -1):
    if i not in max_dic:
        max_dic[i] = max_dic[i + 1]
    max_dic[i] += max_dic[i + 1]
# print(max_dic)

M = int(input())
bead = []
for i in range(M):
    bead.append(list(map(int, input().split())))
eliminate(bead, max_dic)  

count = 0
while count != max_dic[1] + 2 * len(bead):
    te = None
    tmp = 0
    for i in range(len(bead) - 1, -1, -1): 
        if len(bead[i]) == 3:
            if tmp < bead[i][-1]:  
                te = i
                tmp = bead[i][-1]
                continue
        if tmp < bead[i][-1] - bead[i][-2]:  
            te = i
            tmp = bead[i][-1] - bead[i][-2]
    # print(dic)
    # print(max_dic)
    if max_dic[bead[te][0]] > dic[bead[te][0]] and bead[te][0] != max(dic):
        max_dic[bead[te][0] + 1] -= max_dic[bead[te][0]] - dic[bead[te][0]]
        for i in range(max_dic[bead[te][0]] - dic[bead[te][0]]):
            bead[bead[te][0]].pop()
    if len(bead[-1]) == 2: 
        res = bead.pop()[0]
        del dic[res]
        del max_dic[res]
    # print(bead)
    Sum = 0
    for i in bead[::-1]:
        if Sum + i[1] <= max_dic[i[0]]:
            Sum += i[1]
        else:
            Sum += i[1]
            for j in range(Sum - max_dic[i[0]]):
                Sum -= 1
                i.pop()
                i[1] -= 1
    count = 0
    for i in range(len(bead)):
        count += len(bead[i])
    if count < max_dic[1] + 2 * len(bead):
        break

Num = 0
for i in bead:
    Num += i[-1]
print(Num)