第一题 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
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 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的矩形，矩形的每一个元素是*或者.，由于这个矩形可能会有很多的没用的.，因此要求把这个矩形话到最简
思路：直接求出左上角和又上角，然后输出即可
代码：
#!/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
4
input
2 2 0 4 5 2
output
3
input
2 3 0 4 5 2
output
2
Note
It is possible for the x-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