这次学习的是Google Kick Start的2020回G轮题目，虽然我终于成功地在考试的时候做了这个，但是结果。。才得了39分，可能我注定没有办法进去Google了呢w。

点击这里→传送门 可以返回到这个系列的List哦

Round G 2020

Problem
Ksenia is very fond of reading so she kicks off each day by reading a fragment from her favourite book before starting with the rest of her morning routine. A fragment is simply a substring of the text. Ksenia is somewhat superstitious and believes that her day will be lucky if the fragment she reads starts with the string KICK, then goes on with 0 or more characters, and eventually ends with the string START, even if the overall fragment makes little sense.

Given the text of the book, count the number of different lucky fragments that Ksenia can read before the book gets old and she needs to buy another one. Two fragments are considered to be different if they start or end at different positions in the text, even if the fragments read the same. Also note that different lucky fragments may overlap.

Input
The first line of the input gives the number of test cases T. T lines follow, each containing a single string S consisting of upper case English letters only.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of different lucky fragments in the text of this test case.

Limits
Memory limit: 1 GB.
1 ≤ T ≤ 100.
S consists of upper-case English letters only.

Test Set 1
Time limit: 20 seconds.
1 ≤ |S| ≤ 1000.

Test Set 2
Time limit: 40 seconds.
1 ≤ |S| ≤ 105.

Sample

Input

Output

3
AKICKSTARTPROBLEMNAMEDKICKSTART
STARTUNLUCKYKICK
KICKXKICKXSTARTXKICKXSTART

Case #1: 3
Case #2: 0
Case #3: 5

There are three lucky fragments in the first test case, namely, KICKSTARTPROBLEMNAMEDKICKSTART and two occurrences of KICKSTART. The text in the second test case has no lucky fragments at all.

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def Calc():
    readStr = input()
    len_readStr=len(readStr)
    result = []
    for i in range(len_readStr):
        # if(readStr[i]=='K' and i+4<=len_readStr):
        if(readStr.find("KICK",i)==i):
            result.append(0)
            i+=4
        # elif(readStr[i]=='S' and i+5<=len_readStr):
        elif(readStr.find("START",i)==i):
            result.append(1)
            i+=5

    total_1 = 0
    for i in range(len(result)):
        if(result[i]==0):
            for j in range(i+1,len(result)):
                if(result[j]==1):
                    total_1+=1
    # print(result)
    return total_1
            


def main():
    totalNumber=int(input())
    for i in range(totalNumber):
        print("Case #"+str(i+1)+": "+str(Calc()))

if __name__=="__main__":
    main()

Problem
Mike has a square matrix with N rows and N columns. Cell (i,j) denotes the cell present at row i and column j. Cell (1,1) denotes the top left corner of the matrix. Each cell has some amount of coins associated with it and Mike can collect them only if he visits that cell. Ci,j represents the number of coins in cell with row i and column j. From a cell (i,j), Mike can decide to go to cell (i+1,j+1) or cell (i-1,j-1), as long as the cell lies within the boundaries of the matrix and has not been visited yet. He can choose to start the journey from any cell and choose to stop at any point. Mike wants to maximize the number of coins he can collect. Please help him determine the maximum number of coins he can collect.

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The next N lines contain N integers each. The j-th integer in the i-th line represents the number of coins Ci,j in cell (i,j).

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of coins Mike can collect.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ Ci,j ≤ 107.

Test Set 1
1 ≤ N ≤ 100.

Test Set 2
1 ≤ N ≤ 103 in at most 10 cases.
1 ≤ N ≤ 100 in all other cases.

Sample

Input

Output

2
3
1 2 5
3 6 1
12 2 7
5
0 0 0 0 0
1 1 1 1 0
2 2 2 8 0
1 1 1 0 0
0 0 0 0 0

Case #1: 14
Case #2: 9

In Sample Case #1, the maximum number of coins collected can be 14, if Mike follows this path: (1,1) -> (2,2) -> (3,3)

In Sample Case #2, the maximum number of coins collected can be 9, if Mike follows this path: (2,3) -> (3,4).

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def Calc():
    dimension = int(input())
    list_three = [list(map(int, input().split())) for i in range(dimension)]
    large = 0
    sumTmp = 0
    for j in range(dimension):
        sumTmp=0
        for i in range(dimension-j):
            sumTmp+=list_three[i][i + j]
        if(sumTmp>large):large=sumTmp
    for i in range(dimension):
        sumTmp=0
        for j in range(dimension-i):
            sumTmp+=list_three[i + j][j]
        if(sumTmp>large):large=sumTmp
    return large

def main():
    totalNumber=int(input())
    for i in range(totalNumber):
        print("Case #"+str(i+1)+": "+str(Calc()))

if __name__=="__main__":
    main()

Problem
A combination lock has W wheels, each of which has the integer values 1 through N on it, in ascending order.

At any moment, each wheel shows a specific value on it. Xi is the initial value shown on the i-th wheel.

You can use a single move to change a wheel from showing the value X to showing either X+1 or X-1, wrapping around between 1 and N. For example, if a wheel currently shows the value 1, in one move you can change its value to 2 or N.

Given all wheels’ initial values, what is the minimum number of moves to get all wheels to show the same value?

Input
The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case contains the two integers W and N.

The second line contains W integers. The i-th integer is Xi.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of moves to get all wheels to show the same value.

Limits
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Xi ≤ N.

Test Set 1
1 ≤ W ≤ 1000.
2 ≤ N ≤ 1000.

Test Set 2
1 ≤ W ≤ 1000.
2 ≤ N ≤ 109.

Test Set 3
1 ≤ W ≤ 105.
2 ≤ N ≤ 109.

Sample

Input

Output

2
3 5
2 3 4
4 10
2 9 3 8

Case #1: 2
Case #2: 8

In Sample Case #1, the best solution is to get all wheels to show value 3, which would take a total of 2 moves: the first wheel would move once (from value 2 to value 3), the second wheel would not move (it already shows value 3), and the third wheel would move once (from value 4 to value 3).

For reference, it would take 5 moves to get all wheels to show value 1, 3 moves to get all wheels to show value 2, 3 moves to get all wheels to show value 4, and 5 moves to get all wheels to show value 5.

In Sample Case #2, the best solutions are to get all wheels to show either value 1, 2, 9 or 10, which would take a total of 8 moves.

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def Calc():
    wheel_Total=list(map(int, input().split()))
    wheelValue=list(map(int, input().split()))

    minNum = wheel_Total[1]
    small = -1
    sumTmp = 0

    for i in range(wheel_Total[0]):
        sumTmp=0
        for j in range(wheel_Total[0]):
            if(j==i):continue
            else:
                absNum = abs(wheelValue[j]-wheelValue[i])
                sumTmp += min(absNum,minNum - absNum)
        if(small>sumTmp or small == -1):small = sumTmp

    return small

def main():
    totalNumber=int(input())
    for i in range(totalNumber):
        print("Case #"+str(i+1)+": "+str(Calc()))

if __name__=="__main__":
    main()