首页 > 资讯 > Python > 正文

Python解决codeforces ---- 5

13-10-11 来源：[db:作者]

收藏我要投稿

第一题 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 number A written in all bases from 2 to A - 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 number A (3 ≤ A ≤ 1000).

Output

Output should contain required average value in format «X/Y», where X is the numerator and Y is the denominator.

Sample test(s)

input

output

7/3

input

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，输出的格式应该是最简

思路：直接暴力求解

代码：

[python]

#!/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 with n rows and m columns. 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 numbers n and m (1 ≤ n, m ≤ 50), n — amount of lines, and m — amount of columns on Bob's sheet. The following n lines contain m characters 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的矩形，矩形的每一个元素是*或者.，由于这个矩形可能会有很多的没用的.，因此要求把这个矩形话到最简

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

代码：

[python]

#!/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» n square 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 side t, 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 the Ox-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 numbers n and t (1 ≤ n, t ≤ 1000). Then there follow n lines, each of them contains two space-separated integer numbers: xi ai, where xi — x-coordinate of the centre of the i-th house, and ai — 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

input

2 2

0 4

5 2

output

input

2 3

0 4

5 2

output

Note

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

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

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

代码：

[python]

# 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

点击复制链接与好友分享!回本站首页