Python解决codeforces ---- 1

第一题 1A

A. Theatre Square

time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

Theatre Square in the capital city of Berland has a rectangular shape with the sizen × mmeters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the sizea × a.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

Input

The input contains three positive integer numbers in the first line:n,  manda(1 ≤  n, m, a ≤ 109).

Output

Write the needed number of flagstones.

Sample test(s)

input

6 6 4

output

4

题意：给一个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))

第二题 2A

A. Winner

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

The winner of the card game popular in Berland "Berlogging" is determined according to the following rules. If at the end of the game there is only one player with the maximum number of points, he is the winner. The situation becomes more difficult if the number of such players is more than one. During each round a player gains or loses a particular number of points. In the course of the game the number of points is registered in the line "name score", wherenameis a player's name, andscoreis the number of points gained in this round, which is an integer number. If score is negative, this means that the player has lost in the round. So, if two or more players have the maximum number of points (say, it equals tom) at the end of the game, than wins the oneof themwho scored at leastmpoints first. Initially each player has 0 points. It's guaranteed that at the end of the game at least one player has a positive number of points.

Input

The first line contains an integer numbern(1  ≤  n  ≤  1000),nis the number of rounds played. Then follownlines, containing the information about the rounds in "name score" format in chronological order, wherenameis a string of lower-case Latin letters with the length from 1 to 32, andscoreis an integer number between -1000 and 1000, inclusive.

Output

Print the name of the winner.

Sample test(s)

input

3
mike 3
andrew 5
mike 2

output

andrew

input

3
andrew 3
andrew 2
mike 5

output

andrew

题意：有很多人在玩纸牌游戏，总共玩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

A. Shortest path of the king

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, because he has business of national importance. For example, he has to pay an official visit to squaret. As the king is not in habit of wasting his time, he wants to get from his current positionsto squaretin the least number of moves. Help him to do this.

In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).

Input

The first line contains the chessboard coordinates of squares, the second line — of squaret.

Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (fromatoh), the second one is a digit from1to8.

Output

In the first line printn— minimum number of the king's moves. Then innlines print the moves themselves. Each move is described with one of the 8:L,R,U,D,LU,LD,RUorRD.

L,R,U,Dstand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.

Sample test(s)

input

a8
h1

output

7
RD
RD
RD
RD
RD
RD
RD

题意：给定一个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