Google Kick-start Round-C 2019

下次用pypy2编译，py3属实不行。

Q1:Problem Banny has just bought a new programmable robot. Eager to test his coding skills, he has placed the robot in a grid of squares with R rows (numbered 1 to R from north to south) and C columns (numbered 1 to C from west to east). The square in row r and column c is denoted (r, c). Initially the robot starts in the square (SR, SC). Banny will give the robot N instructions. Each instruction is one of N, S, E or W, instructing the robot to move one square north, south, east or west respectively. If the robot moves into a square that it has been in before, the robot will continue moving in the same direction until it reaches a square that it has not been in before. Banny will never give the robot an instruction that will cause it to move out of the grid. Can you help Banny determine which square the robot will finish in, after following the N instructions?

思路

实际就是新建一个dic,负责存储查询

Code

python

Ntest=int(input()) for i in range(Ntest): N,R,C,Sr,Sc=map(int,input().split()) instr=input() Sr-=1 Sc-=1 dic={} dic[(Sr,Sc)]=1 for char in instr: if char=="E": while ((Sr,Sc) in dic): Sc+=1 dic[(Sr,Sc)]=1 continue if char=="N": while ((Sr,Sc) in dic): Sr-=1 dic[(Sr,Sc)]=1 continue if char=="S": while ((Sr,Sc) in dic): Sr+=1 dic[(Sr,Sc)]=1 continue if char=="W": while ((Sr,Sc) in dic): Sc-=1 dic[(Sr,Sc)]=1 print("Case #{}: {} {}".format(i+1, Sr+1, Sc+1))

Q2:Problem Arsh recently found an old rectangular circuit board that he would like to recycle. The circuit board has R rows and C columns of squares. Each square of the circuit board has a thickness, measured in millimetres. The square in the r-th row and c-th column has thickness Vr,c. A circuit board is good if in each row, the difference between the thickest square and the least thick square is no greater than K. Since the original circuit board might not be good, Arsh would like to find a good subcircuit board. A subcircuit board can be obtained by choosing an axis-aligned subrectangle from the original board and taking the squares in that subrectangle. Arsh would like your help in finding the number of squares in the largest good subrectangle of his original board.

思路

实际上使用预处理数组。效果其实很好，就是Py在比赛中实在太慢了

Code

python

nTest = int(input()) for i in range(nTest): R, C, K = map(int, input().split()) Vij = [[int(j) for j in input().split()] for _ in range(R)] Matrix = [[0] * C for _ in range(R)] for tmpr in range(R): for tmpj in range(C): ind = tmpj mintmp, maxtmp = Vij[tmpr][tmpj], Vij[tmpr][tmpj] while ind < C and (maxtmp - mintmp) <= K: ind += 1 if ind < C: maxtmp = max(maxtmp, Vij[tmpr][ind]) mintmp = min(mintmp, Vij[tmpr][ind]) Matrix[tmpr][tmpj] = ind - tmpj ResLi = [] for tmpj in range(C): mimi = 0 for startr in range(R): commonmin=Matrix[startr][tmpj] endr=startr while endr<R: commonmin=min(commonmin,Matrix[endr][tmpj]) mimi = max(mimi, commonmin*(endr-startr+1)) endr+=1 ResLi.append(mimi) print("Case #{}: {}".format(i + 1, max(ResLi)))