# 1. Running training

## Problem Description:

Xiao Ming wants to do a running training. At the beginning, Xiao Ming is full of physical strength, and the physical strength value is 10000.

If Xiao Ming runs, he will lose 600 physical strength per minute.

If Xiao Ming has a rest, he will increase his physical strength by 300 per minute.

The loss and increase of physical strength vary evenly.

Xiao Ming plans to run for one minute, rest for one minute, run for another minute, rest for another minute... This cycle.

If Xiaoming's physical strength reaches 0 at a certain time, he will stop exercising. How long will Xiaoming stop exercising.

In order to make the answer an integer, please output the answer in seconds. Only the number, not the unit, is filled in the answer.

## Answer submission:

This is a result filling question. You just need to calculate the result and submit it.

The result of this question is an integer. When submitting the answer, only fill in this integer. If you fill in the redundant content, you will not be able to score.

## Solution:

### Idea:

1. End condition: physical strength = 0.

2. Time accumulation. Physical strength is calculated according to state.

3. Since the result is in seconds, remember to convert.

### code:

Although this is a result filling question, since it is an assignment, we might as well solve it with code

# encoding:utf-8 # @Author : fyl time = 0 power = 10000 while power > 0: time += 1 if time % 2 == 0:# Judge the status in the past 1 minute power += 300 else: power -= 600 if power == 0: time = time*60 else: #The last minute must be running, which may cause the power to be less than 0 time = (time-1)*60 + ((power+600)/600)*60 #Make up the last minute. power is converted into seconds in proportion. time = int(time) #Because the result of this problem only writes this integer, type conversion is carried out print(time)

Operation result: 3880

## Summary:

There is a small trap in this question: after the last minute of running, power is negative, that is, power cannot be reduced to 0 after a whole minute of exercise. We'll calculate the last minute separately.

# 2. Factorial divisor

## Problem Description:

Define factorial n= one × two × three × ··· × n.

Excuse me 100! (factorial of 100) how many divisors are there.

## 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 an integer. When submitting the answer, only fill in this integer. If you fill in the redundant content, you will not be able to score.

## Solution:

### Idea:

100! It's a huge number. Violent solution must not work. We can decompose 1 ~ 100 factors respectively, and multiply these factors to get 100! Factorization of.

Approximate number:

Any positive integer n greater than 1 can be decomposed into prime factors: p1a1p2a2... pkak

Where pi is two different prime numbers and ai is the corresponding index, then the number of divisors of n is (a1+1)(a2+1)... (ak+1)

### code:

# encoding:utf-8 # @Author : fyl dic={} for i in range(2,101): #Dictionary dic is used to count the number of factors of these 100 numbers. The initialization value is 0 dic[i] = 0 for i in range(2,101): #Cycle 2 ~ 100 to find their quality factor and count the quantity n=i while n!=1: for p in range(2,n+1): if n % p == 0: dic[p]+=1 n = n//p break res = 1 for k in arr.keys(): #The number of divisors is (a ~ 1 ~ + 1) * (a ~ 2 ~ + 1) ** (a~k~+1) res *= dic[k]+1 print(res)

Operation result: 39001250856960000

## Summary:

This question involves counting the quantity, which needs to be counted with a dictionary. Also have some mathematical knowledge of divisor.

# 3. Stack order

## Problem Description:

Planet X pays special attention to order. All roads are one-way streets.

A fleet of 16 beetles started successively according to the number, caught in other traffic flows and moved forward slowly.

There is a dead end on the roadside, which can only allow one car to pass. It is a temporary checkpoint, as shown in the figure.

Planet X is so rigid that every passing car is required to enter the checkpoint, or it may be released without inspection, or it may be carefully inspected.

If the order of vehicles entering and leaving the checkpoint can be staggered arbitrarily.

So, how many possible orders will the team take when it gets on the road again?

For convenience, it is assumed that the checkpoint can accommodate any number of cars.

Obviously, if the fleet has only one vehicle, there may be one order; 2 possible sequences of 2 vehicles; There are 5 possible sequences for 3 vehicles.

There are 16 cars now, pro! You need to calculate the number of possible orders.

## Answer submission:

This is an integer. Please submit the answer through the browser and do not fill in any redundant content (such as explanatory text).

## Solution:

### Idea:

Recursion is adopted, and recursion is considered in three cases

1. When there are no cars on the left side of the lane, there is only one order regardless of whether there are cars in the checkpoint. This is the baseline condition return 1.

2. When there are cars on the left and there are no cars in the checkpoint, according to the requirements of the topic, each car must enter the checkpoint, so the number of cars on the left - 1, the number of cars in the checkpoint + 1 return f (n-1,1).

3. If there are cars in the checkpoint, the number of schemes in this case is the sum of two recursions. The two recursions correspond to: another car on the left enters the checkpoint and another car out of the checkpoint return f (n - 1,m + 1) + f (n,m - 1).

### code:

# encoding:utf-8 def fun(n,m):#n is the number of vehicles on the left, and m is the number of vehicles in the checkpoint if n == 0:#If there's no car on the left return 1 if m == 0:#If there is no car at the checkpoint, enter the checkpoint return fun(n-1,1) if m > 0:#If there is a car at the checkpoint #There are two cases: 1 Another car on the left comes in 2 A car went out of the checkpoint return fun(n-1,m+1) + fun(n,m-1) print(fun(16,0))

Reference link: https://blog.csdn.net/qq_45281807/article/details/104221946

Another solution idea: the number of stack order is Cartland number, which satisfies a recursive formula: h1=1; hn=hn-1(4n-2)/(n+1). Where n represents the number of numbers.

# encoding:utf-8 ans = 1 for x in range(1, 17): ans = ans*(4*x-2)/(x+1) print(ans)

Reference link: https://blog.csdn.net/milk_paramecium/article/details/113893758

Operation result: 357670

## Summary:

When using recursive methods, you must find the baseline conditions and recursive conditions.

# 4. Goldbach decomposition

## Problem Description:

## Solution:

### Idea:

Each even number is decomposed into two prime numbers, as long as the smallest one, and then find the largest one in this range. The even number range of this question is within 10000.

### code:

# encoding:utf-8 x = [] def Split_even(n):#Defines a function that decomposes even numbers def IsPrime(num): #Determine whether num is a prime number if num == 2: return True for i in range(2,num): if num % i == 0: return False return True for j in range(2, n // 2 + 1): if IsPrime(j) and IsPrime(n - j):#Judge whether these two numbers are prime numbers return [j,n-j]# If both are, the two prime numbers are returned for i in range(4,10001,2): x.append(min(Split_even(i)))#Add the smallest of the decomposed two prime numbers to the x list print(max(x))#Print the largest element in the list

Operation result: 173

# 5. Book arrangement

## Problem Description:

10 books numbered 1 ~ 10 shall be placed on the bookshelf, and the books with adjacent numbers shall not be placed in adjacent positions.

Please calculate how many different permutations there are.

## Answer submission:

What needs to be submitted is an integer. Do not fill in any redundant content.

## Solution:

### Idea:

1. Find out all possible permutations (full permutations).

There are n elements in the list. Fix the first element and fully arrange the remaining n - 1 elements.

Exchange the first element with other elements, and fully arrange the remaining n-1 elements after each exchange.

The remaining n - 1 elements are arranged completely, as above. After fixing, arrange n - 2.

Until the number of arrays is 1, the full permutation is itself, completing one permutation.

2. Then judge whether these permutations comply with "the books with adjacent numbers are not in the adjacent position", and count the permutations that comply.

### code:

# encoding:utf-8 res = 0 def check(book):#Check whether the "book with adjacent number is not in adjacent position" is met and count for i in range(9): if abs(book[i]-book[i+1]) == 1: return False return True def Full_Perm(book, begin, end): global res#The variables inside the function and outside the function should be declared with global if begin == end:#Recursive end condition. When the last element is exchanged, there is no need to exchange again. This arrangement is completed. if check(book): res += 1 return else: j = begin for i in range(begin, end):#Full Permutation from begin to end book[i],book[j] = book[j],book[i]#exchange Full_Perm(book, begin+1, end)# After the exchange, the remaining arrays are fully arranged. [begin + 1, end] book[i],book[j] = book[j],book[i] #Restore to the state before the exchange for the next exchange book = [i for i in range(1, 11)] Full_Perm(book, 0, len(book)) print(res)

Operation result: 479306

## Summary:

The key point of this problem is to write a recursive function to realize full permutation.

Python itertools library has functions to implement full permutation.

# encoding:utf-8 import itertools s = ['a','b','c'] for i in itertools.permutations(s): print(i)

# 6. Monkeys divide bananas

## Problem Description:

## Solution:

### Idea:

### code:

# encoding:utf-8 n=6#Set the initial value of the number of bananas the first monkey sees when waking up to at least 6 a=b=c=d=0 while True: if(n%5==1):#Meet the condition that the first monkey has one banana left a=(n-1)/5*4#The number of bananas the second monkey saw when he woke up if(a%5==2): b=(a-2)/5*4#The number of bananas the third monkey saw when he woke up if(b%5==3): c=(b-3)/5*4#The number of bananas the fourth monkey saw when he woke up if(c%5==4): d=(c-4)/5*4#The number of bananas the fifth monkey saw when he woke up if(d%5==0 and d!=0):#Judge whether it meets the condition that the fifth monkey divides bananas equally and just finished print(n) break n+=1

Reference link: https://blog.csdn.net/qq_40871196/article/details/86690969

## Summary:

Didn't figure out how to solve it recursively. It doesn't seem to use recursion,

# 7. Slightly smaller score

## Problem Description:

Back to primary school----

True fraction: fraction whose numerator is less than denominator

Reduced fraction: the coprime of numerator and denominator, that is, the maximum common divisor is 1

The entrance verification method of Planet x math city is:

A true score is displayed on the screen. You need to quickly find a reduced score smaller than it. The larger the score, the better.

At the same time, limit the denominator of your score to no more than 100.

## Solution:

### Idea:

### code:

# encoding:utf-8 def gcd(a,b): if b==0: return a return gcd(b,a%b) #This is the score a/b displayed on the screen a = 7 b = 13 max_a = 0 max_b = 1 for n in range(100,1,-1): for m in range(n-1,0,-1): if (m*b<a*n) and (gcd(m,n) == 1): if max_a*n < max_b*m: max_a = m max_b = n break print("%d/%d"%(max_a, max_b))

## Summary:

This question is a blank filling question in the original question of Blue Bridge Cup. Since the input format is not specified in the assignment, the input cannot be controlled, and the original question is copied directly.

# 8.excel address

## Problem Description:

Time limit: 1.0s memory limit: 256.0MB

Problem Description:

The address representation of Excel cells is very interesting. It uses letters to represent column numbers.

For example,

A stands for column 1,

B represents column 2,

Z represents column 26,

AA means column 27,

AB stands for column 28,

BA stands for column 53,

...

Of course, the maximum column number of Excel is limited, so it is not difficult to convert.

If we want to generalize this representation, can we convert large numbers into long letter sequences?

This topic is to output the corresponding Excel address representation of the input number.

sample input

26

sample output

Z

sample input

2054

sample output

BZZ

Data scale and agreement

We agree that the input integer range [12147483647]

Peak memory consumption (including virtual machine) < 256M

CPU consumption < 1000ms

Please output in strict accordance with the requirements, and do not print superfluous contents such as "please input...".

be careful:

The main function needs to return 0;

Only ANSI C/ANSI C + + standards are used;

Do not call special functions that depend on the compilation environment or operating system.

All dependent functions must be explicitly #include in the source file

Common header files cannot be omitted through project settings.

When submitting programs, pay attention to selecting the desired language type and compiler type.

## Solution:

### Idea:

The problem is similar to the conversion from hexadecimal to hexadecimal, but it is only similar. We can solve it by recycling surplus.

### code:

# encoding:utf-8 n = int(input()) ans = [] while n!= 0: if n % 26 == 0: ans.append(26) n = n // 26 - 1 # here - 1 is required else: ans.append(n%26) n = n // 26 for i in range(len(ans)): #Add 64 to convert numbers into characters and print forward from the end of the list print(chr(ans[len(ans)-i-1]+64), end='')

Reference link: https://blog.csdn.net/qq_43604482/article/details/105825981

## Summary:

Note that it is not really binary 26. For example, it is Z and AZ at points 26 and 52. It is not carried like the real hexadecimal, but needs to add 1 to complete the carry. Therefore, a carry is subtracted from the multiple node of 26.

# 9. Date issue

## Problem Description:

Xiao Ming is sorting out a batch of historical documents. Many dates appear in these historical documents. Xiao Ming knows that these dates are from January 1, 1960 to December 31, 2059. What bothers Xiao Ming is that the formats of these dates are very different, including year / month / day, month / day / year and day / month / year. What is more troublesome is that the first two digits of the year are omitted, so that there are many possible dates corresponding to a date in the literature.

For example, 02 / 03 / 04 may be March 4, 2002, February 3, 2004 or March 2, 2004.

Given a date in the literature, can you help Xiao Ming judge which possible dates correspond to it?

input

A date in the format "AA/BB/CC". (0 <= A, B, C <= 9)

output

Output several different dates, one line for each date, in the format of "yyyy MM DD". Multiple dates are arranged from morning to night.

sample input

02/03/04

sample output

2002-03-04

2004-02-03

2004-03-02

Resource agreement:

Peak memory consumption (including virtual machine) < 256M

CPU consumption < 1000ms

## Solution:

### Idea:

Consider the unsatisfied situation comprehensively, and finally sort and de duplicate.

### code:

# encoding:utf-8 data = list(map(int, input().split("/"))) res = [] def isLeapYear(year): if (year % 4 == 0 and year % 100 != 0) or year % 400 == 0: return True else: return False def fun(x, y, z): # Default date if 0<=x<=59: #Year of discussion x += 2000 elif 60<=x<=99: x += 1900 if y <= 0 or y > 12:#Discussion month return False if z <= 0 or z > 31:#Discussion day return False if isLeapYear(x) and y == 2 and z > 29: return False if isLeapYear(x) == False and y == 2 and z > 28: return False if y in [4,6,9,11] and z > 30: return False else: if y < 10: y = str(0) + str(y) if z < 10: z = str(0) + str(z) res.append(str(x) + "-" + str(y) + '-' + str(z)) return fun(data[0], data[1], data[2])#a[0] is the year, a[1] is the month, and a[2] is the day fun(data[2], data[0], data[1])#a[0] is the month, a[1] is the day, and a[2] is the year fun(data[2], data[1], data[0])#a[0] is the day, a[1] is the month, and a[2] is the year for i in sorted(list(set(res))): print(i)

Reference link: https://blog.csdn.net/bianxia123456/article/details/106816421

## Summary:

# 10. Integer division

## Problem Description:

The division of a positive integer n is the expression that turns n into the sum of a series of positive integers. Note that the partition has nothing to do with the order, for example, 6 = 5 + 1 It is the same partition as 6 = 1 + 5. In addition, the integer itself is also a partition.

For example, for a positive integer n=5, it can be divided into:

1+1+1+1+1

1+1+1+2

1+1+3

1+2+2

2+3

1+4

5

Enter description

Enter a positive integer n

Output description

Output the total number of n integer partitions k

sample input

5

sample output

7

## Solution:

### Idea:

Each of the above numbers is defined as the division factor of 6. It can be seen that 6 has 6 division factors, and each of them may form 6. You can then use a for loop to traverse the partition factors in turn. For example, starting from 1, 1 is the first number to form 6, then rest = 6-1 Then do the same analysis for rest, that is, recursion. The recursive termination condition is that when rest = 0, 6 is divided and output. At this time, a data structure is needed to store the appropriate partition factor and traverse the output from here. Finally, in order to remove duplication, an if judgment is added during backtracking after recursion. It is specified that the partition factor stored in the data structure can be stored only when it is judged that the partition factor is not less than the previous bit (subscript-1) before storing a new partition factor.

### code:

# Use the python dictionary data structure to store the partition factor, starting from 1 and occupying the bit with 0 dividing_number = {0: 0} # Number accumulation variable times = 0 def int_divide(number, index): global times # Traverse all partition factors of the integer starting from 1 for i in range(1, number+1): # Compared with the previous division factor, the weight can be removed. If there are 24 and 42 first, it will not work if i >= dividing_number[index-1]: dividing_number[index] = i # Current number - the number remaining after dividing the factor, such as 6-1 and 5 number_rest = number - i # The integer is divided if number_rest == 0: # Output partition factor for j in range(1, index): print(str(dividing_number[j])+'+', end='') print(str(dividing_number[index])) times = times + 1 # Not divided, continue, dividing_Number division digit + 1 else: int_divide(number_rest, index+1) else: pass n = int(input("Please enter an integer\n")) int_divide(n, 1) print("Therefore, the partition number of this integer is:%d" % times)

Reference link: https://blog.csdn.net/qq_42980666/article/details/105037553

## Summary:

The problem is solved skillfully by recursion, which not only completes the division of factors, but also avoids repeated ideas. It's good to learn.

# 11. One step away

## Problem Description:

Waking up from a coma, Xiao Ming finds himself locked up in a waste mine truck on Planet X.

The mine car stopped on a flat abandoned track.

In front of him were two buttons, which read "F" and "B".

Xiao Ming suddenly remembered that these two buttons can control the mine car to move forward and backward on the track.

Press F to advance 97 meters. Pressing B will move back 127 meters.

Through the dim light, Xiao Ming sees a monitoring probe 1 meter in front of him.

He had to try to stop the harvester right under the camera before he had a chance to get help from his companions.

Perhaps it can be done by multiple operations F and B.

The power on the mine car is not enough, and the yellow warning light is flashing silently

Each F or B operation will consume a certain amount of energy.

Xiao Ming quickly calculated how many operations it would take to park the mine car exactly one meter ahead.

Please fill in the minimum number of operations required to achieve the goal.

Note that what needs to be submitted is an integer. Do not fill in any irrelevant content (such as explanation, etc.)

## Solution:

### Idea:

According to the meaning of the question, the equation can be listed: 97x - 127y = 1. The answer can be found through violent enumeration

### code:

# encoding:utf-8 for x in range(0,1000): for y in range(0,1000): if 97 * x - 127 * y == 1: print(x + y) break else: continue break

## Summary:

The scope of enumeration can be written larger, and the for else statement can be used to jump out of the double-layer loop. You can also set a global variable flag to jump out of multi-layer loops, such as:

# encoding:utf-8 flag = False for x in range(0,1000): for y in range(0,1000): if 97 * x - 127 * y == 1: print(x + y) flag = True break if flag: break

# 12. Robot tower

## Problem Description:

The robot show cheerleaders on Planet X have two kinds of clothes, A and B.

Their performance this time is to build a robot tower.

similar:

A

B B

A B A

A A B B

B B B A B

A B A B B A

The tower rules in the team are:

A can only stand on the shoulders of AA or BB.

B can only stand on the shoulders of AB or BA.

Your task is to help cheerleaders calculate how many kinds of towers can be formed when given the number of A and B.

Enter two integers M and N in one line, with spaces separated (0 < M, n < 500), representing the number of people in A and B respectively, so as to ensure the rationality of the number of people.

It is required to output an integer indicating the number of patterns that can be generated.

For example:

User input:

1 2

The program should output:

3

Another example:

User input:

3 3

The program should output:

4

Resource agreement:

Peak memory consumption < 256M

CPU consumption < 1000ms

## Solution:

### Idea:

cnt = num*(num+1)/2 = M+N, so num = sqrt((M + N) * 2)

The next step is to find the bottom layer, and then check whether it can be expanded upward and whether the number of A and B is enough.

Here, we iterate through all the options in the first row, using A recursive method, with 1 for A and 2 for B.

Then set A check code and calculate the number of all A, B and N from the line. If it is the same as m and N at the top level, it indicates that it is feasible.

### code:

# encoding:utf-8 import math def check():# Judge whether it can expand upward a = 0 b = 0 tmp = row while tmp >0: for i in range(1, tmp+1): if cnt[i] == 1: a +=1 else: b += 1 for i in range(2, tmp+1): if cnt[i-1]==cnt[i]: cnt[i-1] = 1 else: cnt[i-1] = 2 tmp -=1 if a == m and b == n: return True else: return False def dfs(k):# Traverse all underlying global res if k > row: if check(): res +=1 return cnt[k] = 1 dfs(k+1) cnt[k] = 2 dfs(k+1) if __name__ == "__main__": m = int(input()) n = int(input()) res = 0 cnt = [0 for _ in range(100010)] row = int(math.sqrt(2*(m+n))) dfs(1) print(res)

Reference link: https://blog.csdn.net/zznnniuu/article/details/122352199

# 13. Fill in the blanks with seven stars

## Problem Description:

As shown in the figure below. Fill in the number 1 ~ 14 on the 14 nodes of the seven pointed star without repetition or omission. The sum of the four numbers on each line must be equal.

Picture description

Three numbers have been given in the figure. Please calculate the number to be filled in other places. The answer is unique.

After filling in, please output 4 numbers of the green node (from left to right, separated by spaces).

## Solution:

### Idea:

Use python full permutation function to traverse all. Write the subscript on the graph and use the if statement to judge the seven lines.

### code:

# encoding:utf-8 import itertools for i in itertools.permutations([1,2,3,4,5,7,8,9,10,12,13]): num=i[0]+i[1]+i[2]+i[3] if num==i[3]+i[5]+i[7]+i[10]: if num==i[10]+i[9]+i[6]+14: if num==14+i[4]+i[1]+6: if num==6+i[2]+i[5]+11: if num==11+i[7]+i[9]+i[8]: if num==i[8]+i[6]+i[4]+i[0]: print(i[0],i[1],i[2],i[3]) break

Operation result: 10 3 9 8