Python解决codeforces ---- 5

第一题 13A

A. Numbers

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

Little Petya likes numbers a lot. He found that number 123 in base 16 consists of two digits: the first is 7 and the second is 11. So the sum of digits of 123 in base 16 is equal to 18.

Now he wonders what is an average value of sum of digits of the numberAwritten in all bases from2toA - 1.

Note that all computations should be done in base 10. You should find the result as an irreducible fraction, written in base 10.

Input

Input contains one integer numberA(3 ≤ A ≤ 1000).

Output

Output should contain required average value in format «X/Y», whereXis the numerator andYis the denominator.

Sample test(s)

input

5

output

7/3

input

3

output

2/1

Note

In the first sample number 5 written in all bases from 2 to 4 looks so: 101, 12, 11. Sums of digits are 2, 3 and 2, respectively.

题意：给定一个数n，求2~(n-1)进制的所有数的位数总和/n-2，输出的格式应该是最简

思路：直接暴力求解

代码：

#!/bin/python
n = int(raw_input())

# getAns
def gcd(a , b):
    if b == 0:
       return a
    return gcd(b , a%b)

sum = 0
i = 2
while i < n:
    tmp = n
    while tmp:
        sum += tmp%i
        tmp /= i
    i += 1
# output
print "%d/%d" % (sum/gcd(sum,n-2) , (n-2)/gcd(sum,n-2))

第二题 14A

A. Letter

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

A boy Bob likes to draw. Not long ago he bought a rectangular graph (checked) sheet withnrows andmcolumns. Bob shaded some of the squares on the sheet. Having seen his masterpiece, he decided to share it with his elder brother, who lives in Flatland. Now Bob has to send his picture by post, but because of the world economic crisis and high oil prices, he wants to send his creation, but to spend as little money as possible. For each sent square of paper (no matter whether it is shaded or not) Bob has to pay 3.14 burles. Please, help Bob cut out of his masterpiece a rectangle of the minimum cost, that will contain all the shaded squares. The rectangle's sides should be parallel to the sheet's sides.

Input

The first line of the input data contains numbersnandm(1 ≤ n, m ≤ 50),n— amount of lines, andm— amount of columns on Bob's sheet. The followingnlines containmcharacters each. Character «.» stands for a non-shaded square on the sheet, and «*» — for a shaded square. It is guaranteed that Bob has shaded at least one square.

Output

Output the required rectangle of the minimum cost. Study the output data in the sample tests to understand the output format better.

Sample test(s)

input

6 7
.......
..***..
..*....
..***..
..*....
..***..

output

***
*..
***
*..
***

input

3 3
***
*.*
***

output

***
*.*
***

题意：给定一个n*m的矩形，矩形的每一个元素是*或者.，由于这个矩形可能会有很多的没用的.，因此要求把这个矩形话到最简

思路：直接求出左上角和又上角，然后输出即可

代码：

#!/bin/python
# input
n,m = map(int , raw_input().split())
mat = []
for i in range(n):
    mat.append(raw_input())

# getx1
def getx1():
    for i in range(n):
        for j in range(m):
            if mat[i][j] == '*':
               return i
# gety1
def gety1():
    for i in range(m):
        for j in range(n):
            if mat[j][i] == '*':
               return i

# getx2
def getx2():
    i = n-1
    while i >= 0:
          j = m-1 
          while j >= 0:
                if mat[i][j] == '*':
                   return i
                j -= 1
          i -= 1
# gety2              
def gety2():
    j = m-1
    while j >= 0:
          i = n-1
          while i >= 0:
                if mat[i][j] == '*':
                   return j
                i -= 1
          j -= 1
# output
x1 = getx1()
x2 = getx2()
y1 = gety1()
y2 = gety2()
for i in range(x1,x2+1):
    print mat[i][y1:y2+1]
         

第三题 15A

A. Cottage Village

time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

A new cottage village called «Flatville» is being built in Flatland. By now they have already built in «Flatville»nsquare houses with the centres on theОx-axis. The houses' sides are parallel to the coordinate axes. It's known that no two houses overlap, but they can touch each other.

The architect bureau, where Peter works, was commissioned to build a new house in «Flatville». The customer wants his future house to be on theОx-axis, to be square in shape, have a sidet, and touch at least one of the already built houses. For sure, its sides should be parallel to the coordinate axes, its centre should be on theOx-axis and it shouldn't overlap any of the houses in the village.

Peter was given a list of all the houses in «Flatville». Would you help him find the amount of possible positions of the new house?

Input

The first line of the input data contains numbersnandt(1 ≤ n, t ≤ 1000). Then there follownlines, each of them contains two space-separated integer numbers:xiai, wherexi—x-coordinate of the centre of thei-th house, andai— length of its side ( - 1000 ≤ xi ≤ 1000,1 ≤ ai ≤ 1000).

Output

Output the amount of possible positions of the new house.

Sample test(s)

input

2 2
0 4
6 2

output

4

input

2 2
0 4
5 2

output

3

input

2 3
0 4
5 2

output

2

Note

It is possible for thex-coordinate of the new house to have non-integer value.

题意：有一个人想要建房子，这些房子都是建在x轴上面的，现在已经有n个房子是建好的。给定新建的房子的长为t，问总共能在几个位置建新房子

思路：利用字典保存n个已经建好的房子的位置，然后枚举一遍即可

代码：

# input
n,t = map(int , raw_input().split())
dict = {}
for i in range(n):
    x,a = map(int , raw_input().split())
    dict[x] = a

# getAns
ans = 2
list = dict.keys()
list.sort()
pre = -(1<<30)

for key in list:
    a = float(dict[key])/2
    if pre != -(1<<30):
       dis = abs((key-a)-pre)
       if dis > t:
          ans += 2
       elif dis == t:
          ans += 1
    pre = key+a

# output
print ans