Python解决codeforces ---- 1
第一题 1A
题意:给一个n*m的矩形,和a*a的正方形。要用a*a的正方形去覆盖n*m的矩形,要求a*a的正方形不能切割开,但是两个a*a的正方形可以重叠,问最小需要几个这样的正方形
代码:
my_list = raw_input().split()
n = int(my_list[0])
m = int(my_list[1])
a = int(my_list[2])
print (n/a+(n%a>0))*(m/a+(m%a>0))
题意:有很多人在玩纸牌游戏,总共玩n轮。每一轮里面包括玩家的名字,和玩家这一轮的得分,现在问最后谁的得分最高(假设为m),如果有多个人得分最高,输出最先得到m分的玩家
思路:我们先利用n轮求出最后每个人的得分这样就可以求出最大的分数m,然后枚举这么多个人去找如果得分为m的人就去从头模拟一遍找到得分为m分的轮数,最后找到赢家
代码:
# define some variable
n = int(raw_input())
maxScore = {}
input = []
# n times input
while n > 0:
list = raw_input().split()
input.append(list)
name = list[0]
score = int(list[1])
if maxScore.has_key(name):
maxScore[name] += score
else:
maxScore[name] = score
n -= 1
# find maxScore = ans
ans = 0
for key in maxScore:
ans = max(ans , maxScore[key])
# def to find the time >= ans
def getTime(str):
sum = 0
cnt = 0
for list in input:
name = list[0]
score = int(list[1])
if name == str:
sum += score
if sum >= ans:
return cnt
cnt += 1
# one by one if score == ans
time = 2147483647
for key in maxScore:
if maxScore[key] == ans:
t = getTime(key)
if time > t:
time = t
ansName = key
# output
print ansName
第三题 3A
题意:给定一个8*8的地图,再给定两个点s和t,s是起点,t为终点,问s到t最少需要几步,规定每一步可以往当前格子的8个方向移动,最后打印出路径
思路:由于每一个点可以往周围的8个方向移动,那么我们很快的求出最少需要的步数为ans = max(abs(s.x-t.x) , abs(s.y-t.y)),我们求出了最少需要的几步之后我们直接去模拟,只要满足走这一步能够减少距离那么就是符合的走法
代码:
# Class for Point
class Point:
def __init__(self , x , y):
self.x = x
self.y = y
# input start and end Point
str = raw_input()
start = Point(8-int(str[1]) , ord(str[0])-97)
str = raw_input()
end = Point(8-int(str[1]) , ord(str[0])-97)
# solve this problem
dir = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
move = ["U","RU","R","RD","D","LD","L","LU"]
ans = max(abs(start.x-end.x) , abs(start.y-end.y))
# output
print ans
m = ans
x = start.x
y = start.y
# print "%d %d" % (start.x , start.y)
# print "%d %d" % (end.x , end.y)
while m > 0:
for i in range(8):
tmpx = x+dir[i][0]
tmpy = y+dir[i][1]
if (tmpx >= 0 and tmpx < 8 and tmpy >= 0 and tmpy < 8):
dis = max(abs(tmpx-end.x) , abs(tmpy-end.y))
if dis < m:
print move[i]
x = tmpx
y = tmpy
break
m -= 1