1. With score
Problem description
100 can be expressed as a fractional form: 100 = 3 + 69258 / 714.
It can also be expressed as: 100 = 82 + 3546 / 197.
Note: in the band fraction, the numbers 1 ~ 9 appear respectively and only once (excluding 0).
Like this band fraction, 100 has 11 representations.
Input format
Read a positive integer n (n < 1000 * 1000) from the standard input
Output format
The program outputs the number, and the numbers 1 ~ 9 are used to form all kinds of numbers represented by fractions without repetition or omission.
Note: it is not required to output each representation, only the number of representations is counted!
Sample input 1
100
Sample output 1
11
Sample input 2
105
Sample output 2
6
Answer submission:
a = input('')
a_num = int(a)
count = 0
# print(int('9'*(5-len(a)))+int('9'*(6-len(a))))
for i in range(int('9'*(5-len(a))), int('9'*(6-len(a)))):
# print(i)
for n in range(1, a_num):
stra = str(n) + str((a_num - n)*i) + str(i)
# print(n, (a_num - n)*i, i)
for j in range(9):
if str(j+1) not in stra:
j = 7
break
if j == 8 and len(stra) == 9:
# print(stra)
# print(n, (a_num - n)*i, i)
count += 1
# print(stra)
print(count)
2. Li Bai makes wine
Title Description
It is said that Li Bai, a great poet, likes drinking all his life. Luckily he never drives.
One day, he came out of the house with a wine pot. There were two buckets of wine in the wine pot. He sang as he walked:
Walk down the street and fetch a pot of wine.
Double every shop and drink a bucket of flowers.
Along the way, he met the store 5 times and flowers 10 times. It is known that the last time he met flowers, he just drank up the wine.
Please calculate the order in which Li Bai meets the shop and flowers. You can record the shop as a and the flower as b. Then: babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbab. How many answers are there like this? Please calculate the number of all possible schemes (including those given in the title).
Answer submission:
def dfs(a, b, c):
if a > 0:
dfs(a - 1, b, c * 2)
if b > 0:
dfs(a, b - 1, c - 1)
if a == 0 and b == 0 and c == 1:
res.append(1)
return res
res = []
print(len(dfs(5, 9, 2)))
Result: 14
3. 39th step
Title Description:
Xiao Ming just finished watching the movie "the 39th step". When he left the cinema, he counted the steps in front of the auditorium. It happened to be 39 steps!
Standing in front of the steps, he suddenly thought of another question:
If I can only take one or two steps at a time. Take the left foot first, then turn left and right. The last step is to take the right foot, that is, take an even number of steps. So, how many different methods are there after 39 steps?
Output format:
Output an integer
Answer submission:
lis = [[-1] * 39 for _ in range(39)]
def walk(num, step):
if num > 39:
return 0
elif num == 39:
return 1 if step % 2 == 0 else 0
if lis[num][step] != -1:
return lis[num][step]
else:
ans = walk(num + 1, step + 1) + walk(num + 2, step + 1)
lis[num][step] = ans
return ans
print(walk(0, 0))
Result: 51167078
4. Crossing minefields
Title Description
The known map is A square matrix, on which areas A and B are marked with letters, and other areas are marked with positive or negative signs to represent positive and negative energy radiation areas respectively.
For example:
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
Tanks can only move horizontally or vertically to adjacent areas.
Data format requirements:
The first input line is an integer n, indicating the size of the square matrix, 4 < = n < 100
Next, there are n rows. Each row has n data, which may be one of A, B, +, - separated by spaces.
A. B only appears once.
It is required to output an integer indicating the minimum moving steps of the tank from area A to area B.
If there is no scheme, output - 1
For example:
User input:
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
The program should output:
10
Resource agreement:
Peak memory consumption < 512M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print like "please input..." Superfluous content.
All code is placed in the same source file. After debugging, the copy is submitted to the source code.
Note: the main function needs to return 0
Note: only use ANSI C/ANSI C + + standards, and do not call special functions that depend on the compilation environment or operating system.
Note: all dependent functions must be explicitly included in the source file #include < XXX >, and cannot pass the project
Answer submission:
n = int(input())
m = [input().split(' ') for _ in range(n)]
visit = [[False] * n for _ in range(n)]
step = [(0, -1), (0, 1), (-1, 0), (1, 0)]
queue = [(0, 0, 0)]
while queue:
y, x, t = queue.pop(0)
if m[y][x] == 'B':
print(t)
break
for dy, dx in step:
ny = y + dy
nx = x + dx
if -1 < nx < n and -1 < ny < n:
if not visit[ny][nx] and m[y][x] != m[ny][nx]:
queue.append((ny, nx, t+1))
visit[y][x] = True
if not queue:
print(-1)
5. Maze
Title Description
The following figure shows the plan of a maze, where the one marked with 1 is an obstacle and the one marked with 0 is an accessible place.
010000
000100
001001
110000
The entrance of the maze is the upper left corner and the exit is the lower right corner. In the maze, you can only walk from one position to one of its upper, lower, left and right directions. For the above maze, start from the entrance and pass through the maze in the order of DRRURRDDDR, a total of 10 steps. Where D, u, L and R respectively represent going down, up, left and right. For the following more complex maze (30 rows and 50 columns), please find a way to pass through the maze, which uses the least steps. On the premise of the least steps, please find the one with the smallest dictionary order as the answer. Please note that in the dictionary order, d < L < R < U. (if you copy the following text into a text file, be sure to check whether the copied content is consistent with that in the document. There is a file maze.txt in the test question directory, and the content is the same as the following text)
Answer submission
This is a question to fill in the blanks. You just need to calculate the results and submit them. The result of this question is a string containing four letters D, U, L and R. when submitting the answer, only fill in this string, and you will not be able to score if you fill in the redundant content
data = '''01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000'''
data_array = []
data_array.append([1]*52)
for i in data.split():
data_array.append([])
data_array[-1].append(1)
for j in i:
data_array[-1].append(int(j))
data_array[-1].append(1)
data_array.append([1]*52)
visited = []
queue = [[(1, 1)]]
start = (1, 1)
end = (30, 50)
visited.append(start)
def bfs(lst, queue, end):
if end in queue[-1]:
return queue
alist = []
for now in queue[-1]:
row, col = now
if lst[row+1][col] == 0 and ((row+1, col) not in visited):
alist.append((row+1, col))
visited.append((row+1, col))
if lst[row][col+1] == 0 and ((row, col+1) not in visited):
alist.append((row, col+1))
visited.append((row, col+1))
if lst[row-1][col] == 0 and ((row-1, col) not in visited):
alist.append((row-1, col))
visited.append((row-1, col))
if lst[row][col-1] == 0 and ((row, col-1) not in visited):
alist.append((row, col-1))
visited.append((row, col-1))
queue.append(alist)
return bfs(lst, queue, end)
queue = bfs(data_array, queue, end)
Stack = []
Stack.append(start)
visited_1 = [start]
while Stack[-1] != end:
now = Stack[-1]
row, col = now
i = queue[len((Stack))]
if (row+1, col) in i and (row+1, col) not in visited_1:
Stack.append((row+1, col))
visited_1.append((row+1, col))
continue
elif (row, col-1) in i and (row, col-1) not in visited_1:
Stack.append((row, col-1))
visited_1.append((row, col-1))
continue
elif (row, col+1) in i and (row, col+1) not in visited_1:
Stack.append((row, col+1))
visited_1.append((row, col+1))
continue
elif (row-1, col) in i and (row-1, col) not in visited_1:
Stack.append((row-1, col))
visited_1.append((row-1, col))
continue
else:
Stack.pop()
length_1 = len(Stack)
strstep = ""
for i in range(1,length_1):
if Stack[i][0] > Stack[i-1][0]:
strstep += "D"
elif Stack[i][0] < Stack[i-1][0]:
strstep += "U"
elif Stack[i][1] > Stack[i-1][1]:
strstep += "R"
else:
strstep += "L"
print(strstep)
6. Vault
Problem Description:
The half board of Chinese chess is shown in Figure 1. The horse jumps from the lower left corner (0,0) to the upper right corner (m, n). It is stipulated that you can only jump to the right, not to the left. For example, figure 1 shows a skip route and prints the total number of routes.
Input format:
There is only one line: two numbers n, m
Output format:
There is only one number: total number of schemes.
Answer submission:
a, b, c, d = map(int, input().split(' '))
step = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
visit = [[False]*8 for _ in range(8)]
queue = [(a, b, 0)]
while queue:
y, x, t = queue.pop(0)
if y == c and x == d:
print(t)
break
for dy, dx in step:
ny = y + dy
nx = x + dx
if -1 < ny < 8 and -1 < nx < 8 and not visit[ny][nx]:
queue.append((ny, nx, t+1))
visit[ny][nx] = True
if not queue:
print(-1)
Result: 37
7. The mystery of the path
Xiao Ming pretends to be the knight of Planet X and enters a strange castle.
There was nothing in the castle, only the ground made of square stones.
Suppose the castle ground is n x n squares. [as shown in Figure 1.png].
According to custom, knights walk from the northwest corner to the southeast corner.
It can move horizontally or vertically, but it can't walk obliquely or jump.
Every time you come to a new square, you have to shoot an arrow to the north and West.
(there are n targets in the west wall and N targets in the north wall of the castle)
The same square can only pass once. But you don't have to finish all the squares.
If you only give the number of arrows on the target, can you infer the knight's route?
Sometimes it is possible, such as Figure 1 Png example.
The requirement of this question is to know the target number and find the knight's walking path (the test data ensure that the path is unique)
Input:
The first line is an integer n (0 < n < 20), indicating that there are N x N squares on the ground
The second line contains N integers, separated by spaces, indicating the number on the North target (from west to East)
The third line contains N integers, separated by spaces, indicating the number on the target in the West (from north to South)
Output:
Several integers on a line represent the knight path.
For convenience, we agree that each small grid is represented by a number, starting from the northwest corner: 0,1,2,3
For example, figure 1 The block number in PNG is:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Example:
User input:
4
2 4 3 4
4 3 3 3
The program should output:
0 4 5 1 2 3 7 11 10 9 13 14 15
Resource agreement:
Peak memory consumption < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print like "please input..." Superfluous content.
All code is placed in the same source file. After debugging, the copy is submitted to the source code.
Note: do not use package statements. Do not use jdk1 7 and above.
Note: the name of the Main class must be: Main, otherwise it will be treated as an invalid code.
Answer submission:
path = [0 for _ in range(401)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cntx = [0 for _ in range(21)]
cnty = [0 for _ in range(21)]
maps = [[False for _ in range(21)]for _ in range(21)]
sun = False
tot = 0
def check():
for i in range(0, n):
if cntx[i] != 0 or cnty[i] != 0:
return False
return True
def dfs(x, y, num):
global sun
path[num] = y *n + x
maps[x][y] = True
cntx[x] -= 1
cnty[y] -= 1
if x == n and y == n and check():
sun = True
return
for i in range(4):
x1 = x + dx[i]
y1 = y + dy[i]
if not sun and not maps[x1][y1] and 0 <= x1 < n and 0 <= y1 < n:
if cntx[x1] > 0 and cnty[y1] > 0:
dfs(x1, y1, num+1)
maps[x1][y1] = False
cntx[x1] += 1
cnty[y1] += 1
n = int(input())
for i in range(0, n):
cntx[i] = int(input())
tot += cntx[i]
for i in range(0, n):
cnty[i] = int(input())
tot += cnty[i]
dfs(0, 0, 0)
print(path[:tot//2])8. Troubles by Weiming Lake
Problem description
Every winter, Weiming Lake in Peking University is a good place for skating. The sports team of Peking University has prepared many skates, but there are too many people. After work every afternoon, there is often no pair of skates left.
Every morning, there will be a long queue at the shoe rental window. Suppose there are m who return shoes and n who need to rent shoes. The question now is how many arrangements these people have to avoid the embarrassing situation that the sports group has no skates to rent. (two people with the same needs (for example, both rent shoes or return shoes) exchange positions in the same arrangement)
Input format
Two integers representing m and n
Output format
An integer representing the number of schemes for the arrangement of the team.
sample input
3 2
sample output
5
Data scale and agreement
m,n∈［0,18］
Answer submission:
def Lakefannao(m,n):
if m<n:return 0
res=[]
def back(lend,use,temp):
if len(temp)==n+m:
res.append(temp)
return
if lend<m:
back(lend+1,use,temp+'+')
if lend>use and use<n:
back(lend,use+1,temp+'-')
back(0,0,'')
#print(res)
return len(res)
if __name__=='__main__':
m,n=map(int,input().split())
print(Lakefannao(m,n))9. Travel of Ministers
Problem description
Long ago, the kingdom of T prospered unprecedentedly. In order to better manage the country, the Kingdom has built a large number of expressways to connect the capital and the major cities in the kingdom.
In order to save money, the ministers of T country have formulated an excellent construction scheme after thinking, so that any big city can reach directly from the capital or indirectly through other big cities. At the same time, if you do not repeat passing through big cities, the scheme from the capital to each big city is unique.
J is an important Minister of state T. he patrols among major cities and observes the people's conditions. Therefore, from one city to another has become J's most common thing. He has a money bag for the transportation between cities.
Smart J found that if he didn't stop to repair in a city, in the process of continuous travel, the toll he spent was related to the distance he had traveled. In the kilometer from kilometer x to kilometer x+1 (x is an integer), the toll he spent was so much as x+10. In other words, it costs 11 to walk 1 km and 23 to walk 2 km.
Minister J wants to know: what is the maximum cost of all possible travel expenses when he starts from one city and doesn't rest in the middle to another city?
Input format
The first line of input contains an integer n, which represents the number of cities in T kingdom including the capital
Cities are numbered from 1, and city 1 is the capital.
Next, line n-1 describes the expressway in country T (the expressway in country T must be n-1)
Three integers Pi, Qi and Di in each line indicate that there is a highway between city Pi and city Qi, with a length of Di km.
Output format
An integer is output to indicate the maximum travel cost of minister J.
Sample input 1
5
1 2 2
1 3 1
2 4 5
2 5 4
Sample output 1
135
Output format
Minister J costs 135 to travel from city 4 to city 5.
Answer submission:
n = int(input())
lis = [list(map(int, input().split(' '))) for _ in range(n-1)]
m = {i: [] for i in range(1, n+1)}
for i in lis:
m[i[0]].append(i[1:])
m[i[1]].append((i[0], i[2]))
visit = [False] * (n+1)
node = max_length = 0
def dfs(x, length):
global max_length
if length > max_length:
global node
max_length, node = length, x
for nx, l in m[x]:
if not visit[nx]:
visit[nx] = True
dfs(nx, length+l)
visit[nx] = False
dfs(1, 0)
visit = [False] * (n+1)
visit[node] = True
dfs(node, 0)
print(max_length * 11 + max_length*(max_length-1)//2)
10.2n queen problem
Description
Given an n*n chessboard, there are some positions in the chessboard that cannot put queens. Now put n black queens into the chessboard
And n white queens so that any two black queens are not on the same row, column or diagonal
The white queens are not in the same row, column or diagonal. How many kinds of playing methods are there in total? n is less than or equal to 8.
Input
The first line of input is an integer n, which represents the size of the chessboard.
In the next N lines, each line has n integers of 0 or 1. If an integer is 1, it means that the corresponding position can be placed,
If an integer is 0, it means that the corresponding position cannot be placed.
Output
Output an integer indicating the total number of playback methods.
Sample Input
No.1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
No.2
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Sample Output
No.1
2
No.2
0
Answer submission:
def chick_W(nums_W, row):
if list1[row][nums_W[row]]==1:
for i in range(row):
if abs(nums_W[i] - nums_W[row])==abs(i - row) or nums_W[i]==nums_W[row]:
return False
return True
return False
def chick_B(nums_B, row):
if list1[row][nums_B[row]]==1 and nums_W[row]!=nums_B[row]:
for i in range(row):
if abs(nums_B[i] - nums_B[row])==abs(i - row) or nums_B[i]==nums_B[row]:
return False
return True
return False
def dfs_W(nums_W, row):
if row==n:
dfs_B(nums_B,0)
return
for i in range(n):
nums_W[row]=i
if chick_W(nums_W, row):
dfs_W(nums_W, row + 1)
def dfs_B(nums_B, row):
global count
if row==n:
count+=1
return
for i in range(n):
nums_B[row]=i
if chick_B(nums_B, row):
dfs_B(nums_B, row + 1)
n=int(input())
list1=[]
for i in range(n):
list1.append(list(map(eval,input().split())))
list2=[]
nums_W=[0 for i in range(n)]
nums_B=[0 for i in range(n)]
count=0
dfs_W(nums_W, 0)
print(count)