1031. Hello World for U (20)

Given any string of N (>=5) characters, you are asked to form the characters into the shape of U. For example, “helloworld” can be printed as:

h d
e l
l r
lowo
That is, the characters must be printed in the original order, starting top-down from the left vertical line with n1 characters, then left to right along the bottom line with n2 characters, and finally bottom-up along the vertical line with n3 characters. And more, we would like U to be as squared as possible – that is, it must be satisfied that n1 = n3 = max { k| k <= n2 for all 3 <= n2 <= N } with n1 + n2 + n3 - 2 = N.
Input Specification:

Each input file contains one test case. Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.

Output Specification:

For each test case, print the input string in the shape of U as specified in the description.

Sample Input:
helloworld!
Sample Output:
h !
e d
l l
lowor

代碼：

line1 = input() N = len(line1) n1 = (N + 2) // 3 n2 = N + 2 - n1 * 2 str1 = line1[: (n1 - 1)] str2 = line1[(n1 - 1): (n1 + n2 - 1)] str3 = line1[(n1 + n2 - 1): N] for i in range(n1 - 1):print(str1[i] + ' ' * (n2 - 2) + str3[-(i + 1)]) print(str2)

1032. Sharing (25)

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, “loading” and “being” are stored as showed in Figure 1.

Figure 1
You are supposed to find the starting position of the common suffix (e.g. the position of “i” in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (<= 105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output “-1” instead.

Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1

代碼：

# -*- coding: utf-8 -*- ''' 最后一個點超時，想從next遍歷，因為超時的點可能是前面很長，但共同后綴很短 ''' line1 = input().split() begin1 = line1[0] begin2 = line1[1] N = int(line1[2]) address = [] # data = [] # nextAddress = [] addressDict = {} # count = 0 for i in range(N):temp = input().split()# address.append(temp[0])# data.append(temp[1])# nextAddress.append(temp[2])# if temp[2] == '-1': #and temp[0] not in addressDict.keys():# count += 1addressDict[temp[0]] = [temp[1], temp[2]] # if count > 1: # print(-1) # exit() word1 = '' word2 = '' point1 = begin1 point2 = begin2 # print(addressDict) while point1 != '-1':word1 += addressDict[point1][0]address.append(point1)point1 = addressDict[point1][1] while point2 != '-1':word2 += addressDict[point2][0]point2 = addressDict[point2][1] # print(word1, word2) if len(word1) == 0 or len(word2) == 0 or word1[-1] != word2[-1]: ## word可能為空print(-1) else:temp = -1while abs(temp) <= len(word1) and abs(temp) <= len(word2) and word1[temp] == word2[temp]:temp -= 1print(address[temp + 1])

1033. To Fill or Not to Fill (25)

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
Sample Output 1:
749.17
Sample Input 2:
50 1300 12 2
7.10 0
7.00 600
Sample Output 2:
The maximum travel distance = 1200.00

代碼：

# -*- coding:utf-8 -*- line1 = [int(i) for i in input().split()] tankCap = line1[0] totalDis = line1[1] disPerGas = line1[2] stationNum = line1[3] staDic = [] for i in range(stationNum):staDic.append([float(i) for i in input().split()]) staDic.sort(key = lambda x: x[1]) staDic.append([float('inf'), totalDis]) print(staDic) disFullTank = tankCap * disPerGas price = 0 # maxDis = 0 if staDic[0][1] != 0:print('The maximum travel distance = 0.00')exit() i = 0 restGasInDis = 0 while i < stationNum:maxDis = staDic[i][1] + disFullTankprint(i, maxDis, restGasInDis)print('price', price)j = i + 1temp = []while staDic[j][1] <= maxDis: ## 有等號哦，不然樣例2都是錯的if staDic[j][0] <= staDic[i][0]:price += staDic[i][0] * (staDic[j][1] - staDic[i][1] - restGasInDis) / disPerGas# restGasInDis = 0 ## 反正一定是零=。=i = jbreakif staDic[j][1] == totalDis:price += staDic[i][0] * (totalDis - staDic[i][1] - restGasInDis) / disPerGas ## 要減去剩余油量哦，但是沒有檢測點print('%.02f'%price)exit()temp.append(staDic[j])j += 1if i == j:# print('equal')continueif len(temp) == 0:print('The maximum travel distance = ' + '%.02f'%maxDis)exit()print(temp)cheapest = min(temp, key = lambda x: x[0])price += (disFullTank - restGasInDis) / disPerGas * staDic[i][0]restGasInDis = disFullTank - (cheapest[1] - staDic[i][1])print(restGasInDis)i = staDic.index(cheapest) print('%.02f'%price)# 50 1300 12 8 # 8.00 1250 # 7.00 600 # 7.00 150 # 7.10 0 # 7.20 200 # 7.50 400 # 7.30 1000 # 6.85 300 #### 754.58########### 翻車現場 ############# '''if staDic[i + 1][0] < staDic[i][0]:price += staDic[i][0] * (staDic[i+1][1] - staDic[i][1]) / disPerGaselse:for j in range(i + 2, stationNum):if staDic[j][0] < staDic[i][0]:if staDic[j][1] - staDic[i][1] <= disFullTank:price += staDic[i][0] * (staDic[j][1] - staDic[i][1]) / disPerGaselse:disToCheaper = staDic[j][1] - staDic[i][1]maxDis = staDic[i][1] + disFullTankprice += staDic[i][0] * tankCap# s = i + 1 ## 看這里：這時候發現后面的情況很麻煩，那不妨用現在這個maxDis的條件作為總的大條件，重新做 while maxDis < disToCheaper:temp = []for s in range(i + 1, j + 1):temp.append(staDic[s])if staDic[s][1] > maxDis:breakcheapest = min(temp, key = lambda x: x[0])if cheapest[0] < staDic[s][0]price += cheapest[0] * (cheapest[1] - staDic[i][1]) / disPerGasmaxDis = cheapest[1] + disFullTankelse:price += '''

1034. Head of a Gang (30)

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 1:
2
AAA 3
GGG 3
Sample Input 2:
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 2:
0

代碼：

# -*- coding:utf-8 -*- ## 提交時候就不要加這個coding說明了，會占時間 from collections import defaultdict line1 = input().split() n = int(line1[0]) threshold = int(line1[1]) personWeight = {} calls = [] for i in range(n):calls.append(input().split())personWeight[calls[i][0]] = personWeight.get(calls[i][0], 0) + int(calls[i][2])personWeight[calls[i][1]] = personWeight.get(calls[i][1], 0) + int(calls[i][2]) person = list(personWeight.keys()) personNum = len(person) ide = [i for i in range(len(person))] sz = [1] * personNum def find(node):global idewhile node != ide[node]:ide[node] = ide[ide[node]]node = ide[node]return nodedef union(node1, node2, time):global sz, ide, memberroot1 = find(node1)root2 = find(node2)# print(member)# print(root1, root2)if root1 == root2:member[root1][0] += timereturnif sz[root1] >= sz[root2]:ide[root2] = root1sz[root1] += sz[root2]if root2 in member.keys(): ## 這里要考慮小節點已經有子節點的情況，不能簡單地append小節點了member[root1][0] += time + member[root2][0]member[root2].append(root2)member[root2].pop(0)member[root1].extend(member[root2])member.pop(root2)else:member[root1][0] += timemember[root1].append(root2)else:ide[root1] = root2sz[root2] += sz[root1]if root1 in member.keys():member[root2][0] += time + member[root1][0]member[root1].append(root1)member[root1].pop(0)member[root2].extend(member[root1])member.pop(root1)else:member[root2][0] += timemember[root2].append(root1) ## 這種復制的一定要檢查，要不就別復制了，復制幾次錯幾次== # member[root2].append(root1) ## 'builtin_function_or_method' object is not subscriptable 寫成了append(root1)return member = defaultdict(lambda: [0]) for i in range(n):union(person.index(calls[i][0]), person.index(calls[i][1]), int(calls[i][2])) # print(person) # print(member) gangNum = 0 res = [] for key, value in member.items():value.append(key)if len(value) > 3 and value[0] > threshold:gangNum += 1value.pop(0)res.append([person[max(value, key = lambda x: personWeight[person[x]])], str(len(value))])# 這里value.append等操作會改變member # print(threshold) print(gangNum) # print(member) # print(personWeight) if gangNum > 0:res = sorted(res, key = lambda x: x[0])for i in res:print(' '.join(i))# 4 10 # AAA BBB 10 # CCC DDD 10 # DDD EEE 5 # AAA CCC 20

總結

以上是生活随笔為你收集整理的1031-1034的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。