Solving an equation with integer division without enumeration
Recently, a question has been asked on the Toaster , which touched me in earnest. It goes back to the problem, which I will give here in a slightly different interpretation:
I came to the equation, which in the abstract form looks like (1):
, but the fields of the book are too narrow ;)
')
Without illusions about the primacy in this matter, I just want to share the pleasure received in the process. If anyone knows an alternative method or name for it, enlighten me; I appeal to people like me for discussion, and I invite those who are impatient to discuss it under cat.
Consider the resulting equation in this form (2):
Then I considered equation (1) in the form of two functions and . Under which argument they intersect, this will be the solution. For example, I chose small parameter values in such a way as to display the picture as best I can. So, let a = 3, b = 7, c = 9.
Due to the stepped nature of the second function, the graphs y1 and y2 intersect at two points: for x1 = 12 and x2 = 15, but according to the condition, we are interested in the first value, as the smaller one. So, in order to determine the intersection area without searching, I introduced the third function - it is just a straight line that limits the function y2 from below and has the equation .
It now remains to find the intersection point of the two lines ( y1 and y3 ) and correct the answer from the constraint on the desired x . Indeed, based on the condition, it can take only those values under which the condition of the multiplicity of the numerator is observed in the denominator in equation (2), i.e. where n is a kind of natural factor. To do this, we solve a simple equation and if the obtained root does not meet our requirements, we will shift it to the nearest suitable one. Since the auxiliary function y3 has a positive slope, and all values of y2 are above it, the root adjustment should always be done in a larger direction. So, in our case, straight lines intersect at x = 11.25 (black dot on the graph), and the nearest large value that satisfies the condition will be 12 (red dot), which is the answer.
Since the Python tag was in question on the Toaster, I’ll give a script below to solve this problem using a function to find the budget for the current day based on the budget for the next day. We use the function as many times as necessary and, voila, we get the answer!
Instead of concluding:
The task in this example was determined as the parameter values. so the equation itself ; The proposed approach with minor changes is applicable in other similar cases - the purpose of the publication was only a description of the principle itself without deriving a universal solution for the general case - so do not judge strictly (including Python code) and enjoyable Friday everyone!
The programmers somehow passed the project on time and received awards. To celebrate, they kicked off right in PN and bought beer for all the money. On the same day, they all drank, and at VT decided to continue, but there was no more money left. Then they handed over the bottles, added yesterday's surrender, and re-stocked everything, just like yesterday. The same was done on Wed and Thu. And in PT money was exactly one bottle. We thought about it - we remembered the price of one bottle, how much they took the container (the prices were without kopecks), and nobody could give the amount of money initially. The project was large-scale, the awards are big - so it’s not worth the search. What was the minimum budget in PN, so that the events would be formed in this way?Arguing over it as follows
spoiler
since the guys bought as much beer every day as the current budget allowed (B, budget) - the budget of the next day (NB, next_day_budget) was formed from the revenue from returning the container and yesterday's delivery. Two variables are more complicated than one, because I switched to accounting for daily budget reductions (BL, budget_loss). And where P, price is the cost of one bottle of beer; R, return is the price of tare upon return, and N is the number of bottles purchased per day, such that . Then, we can conclude the following:
I came to the equation, which in the abstract form looks like (1):
Trying to find a non-brute force approach to solving such equations, I spent more than one hour, but in the end I found a truly wonderful solution
')
Without illusions about the primacy in this matter, I just want to share the pleasure received in the process. If anyone knows an alternative method or name for it, enlighten me; I appeal to people like me for discussion, and I invite those who are impatient to discuss it under cat.
Consider the resulting equation in this form (2):
since the right-hand side can take only integer values, the whole expression makes sense only when the numerator in the left-hand side is a multiple of the denominator. From this it is obvious that x could have values starting from a value of c and farther with a step a .
Then I considered equation (1) in the form of two functions and . Under which argument they intersect, this will be the solution. For example, I chose small parameter values in such a way as to display the picture as best I can. So, let a = 3, b = 7, c = 9.
Due to the stepped nature of the second function, the graphs y1 and y2 intersect at two points: for x1 = 12 and x2 = 15, but according to the condition, we are interested in the first value, as the smaller one. So, in order to determine the intersection area without searching, I introduced the third function - it is just a straight line that limits the function y2 from below and has the equation .
It now remains to find the intersection point of the two lines ( y1 and y3 ) and correct the answer from the constraint on the desired x . Indeed, based on the condition, it can take only those values under which the condition of the multiplicity of the numerator is observed in the denominator in equation (2), i.e. where n is a kind of natural factor. To do this, we solve a simple equation and if the obtained root does not meet our requirements, we will shift it to the nearest suitable one. Since the auxiliary function y3 has a positive slope, and all values of y2 are above it, the root adjustment should always be done in a larger direction. So, in our case, straight lines intersect at x = 11.25 (black dot on the graph), and the nearest large value that satisfies the condition will be 12 (red dot), which is the answer.
Since the Python tag was in question on the Toaster, I’ll give a script below to solve this problem using a function to find the budget for the current day based on the budget for the next day. We use the function as many times as necessary and, voila, we get the answer!
def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget) Instead of concluding:
The task in this example was determined as the parameter values. so the equation itself ; The proposed approach with minor changes is applicable in other similar cases - the purpose of the publication was only a description of the principle itself without deriving a universal solution for the general case - so do not judge strictly (including Python code) and enjoyable Friday everyone!
Source: https://habr.com/ru/post/427609/
All Articles