Blue Bridge Cup python Group I 2021 the

The first question is The main idea of the topic

Xiaolan has a lot of digital cards , There are numbers on every card 0 To 9.

Xiao Lan is going to use these cards to spell some numbers , He wants to start with 1 Start spelling positive integers , Each one , Just keep it , Cards can't be used to spell other numbers .

Xiao Lan wants to know that she can learn from 1 How much do you spell .

for example , When little blue has 30 Cards , among 0 To 9 various 3 Zhang , Then Xiaolan can spell 1 To 10, But it's hard to 11 Time cards 1 There's only one left , It's not enough to spell 11.

Now Xiaolan has 0 To 9 All the cards are 2021 Zhang , common 20210 Zhang , May I ask Xiao Lan if she can 1 How much do you spell ？

General idea

According to the simple example in the title , We can clearly know , It's nothing more than counting every number （num） in 0-9 Number of occurrences , however 0-9 Each number has an upper limit , What is the maximum number of statistics .

Train of thought analysis

From the above ideas , We want to keep taking numbers in single digits （ Remainder 、 Rounding cycle ）, Indicates that a number is used , So let's go to the upper limit -1, When 0-9 Any one of them is reduced to 0 when , Is the maximum number that can be obtained . Let's analyze the code

list = [2021 for i in range(10)]
# Specify the upper limit of each number 
print(list) # Checklist 
# Construct a function 
def check(num):
# Pass in a parameter num
while num>0:
x = num % 10 # Get the single digit of the parameter 
if list[x]>0: # The number of bits is in the corresponding list -1, Means to use one of the numbers 
list[x] -= 1
else:
return False
num = num // 10 # integer , Discard the used single digits , Take the penultimate place again 
return True
num = 1
while check(num):
num += 1
print(num-1)

Train of thought two analysis

The second method is somewhat ingenious , utilize python Some built-in functions in , By counting each number 0-9 Number of occurrences , To judge .

The code is as follows , Analyze ：

list = [0 for i in range(10)]
# Build a list , To hold 0-9 The number when the upper limit value is reached respectively 
for j in range(10):
for i in range(1,10000): # For the time being, let's define a range 
num = str(i).count(str(j)) # Statistics from 1-10000 pass the civil examinations j The number of times it appears 
list[j] += num
if list[j]>2021: # When the number is greater than 2021 When to return to 
break
list[j] = i-1 # Save the obtained value into list In the list 
print(" The output is ：",min(list))
# The output is ： 3181