Solving an equation with integer division without enumeration
Recently on Toaster there was a question that touched me in earnest. It goes back to the problem, which I will give here in a slightly different interpretation: 3r-3214.
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 turned out to be 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 a brute force. What was the minimum budget in the Mon, so that events would develop in this way?
Arguing over it as follows r3r3214.
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 3r33232.
where P, price is the cost of one bottle of beer; R, return is the price of tare when returning, and N is the number of bottles purchased per day, such that 3r-3219.
. Then, we can conclude the following:
I came to the equation, which in the abstract form looks like (1):
Trying to find an approach without going over to solving such kind of equations, I spent more than one hour, but in the end, 3r-3210. found a truly miraculous solution [/b] 3r350. but the margins of the book are too narrow 3r3351. ;) 3r3144.
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 3r3173. could have values starting with a value of from 3r3173. and further with step a 3r3173. .
Then I considered equation (1) in the form of two functions
. Under which argument they intersect, this will be the solution. For example, I chose small values of parameters in such a way as to display the picture as best I can. So let a 3r3173. = ? 3r3172. b 3r3173. = ? 3r? 3210. 3r3172. c [/b] = 9.
By virtue of the stepped nature of the second function of the graphics 3r3172. y1 and 3r3172. y2 intersect at two points: at 3r3172. x1 = 12 and 3r3172. x2 [/i] = 1? but according to the condition, we are interested in exactly the first value, as the smaller one. So, in order to determine the intersection area without searching, I introduced the third function - this is just a straight line, which limits the function to 3r-3210. 3r3172. y2 [/i] [/b] below and has the equation
It now remains to find the point of intersection of the two straight lines (3r33232. Y1 [/b] And 3r3-33210. Y3 3r3173. [/b] ) And correct the answer from the constraint on the desired 3r?332. 3r3172. x [/b] . After all, based on the condition, it can take only those values under which the condition of multiplicity of the numerator is observed in the denominator in equation (2), i.e.
where 3r3172. n [/i] - a kind of natural multiplier. To do this, we solve the simple equation
and if the received root does not meet our requirements, we will shift it to the nearest suitable one. Since the auxiliary function 3r3172. y3 [/i] has a positive slope, and all values are 3r3172. y2 [/i] are above it, the root adjustment should always be done in a big way. So, in our case, straight lines intersect at 3r33210. 3r3172. x [/i] [/b] = ??? (black dot on the graph), and the nearest large value satisfying 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 the function to find the current day’s budget based on the next day’s budget. We use the function the necessary number of times and, voila, we get the answer!
3r3183. 3r3184. 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 = ((x-c) //a + 1) * a + c
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
current_budget = this_day_budget (current_budget)
print ('first day budget was% d'% current_budget)
Instead of a conclusion:
The task in this example was determined as the values of the parameters
, and the equation itself
; The proposed approach with minor changes is applicable in other similar cases - the purpose of the publication was only to describe the principle itself without deriving a universal solution for the general case - so do not judge strictly (including Python code) and enjoyable Friday everyone!
It may be interesting