We have a calculator with 2 screens and 2 buttons. Each screen shows number zero initially. Pressing the first button increments the number on the first screen by 1, and each press of this button consumes 1 unit of energy. Pressing the second button increases the number on the second screen by the number appearing on the first screen. Each click of this button consumes B units of energy. Given B,N what’s the maximum possible number that may show on the second screen without consuming more than N units of energy?
EXPLANATION:
First of all, it’s obvious that it’s not optimal to press the first button after pressing the second. We must press the first button for number of times, after that we should spend the remaining energy on pressing the second button.
Let’s define a function f(x) where f(x) represents the maximum number displayed on the second screen if we pressed the second button exactly x times.
f(x) = (N-x*B) * x
f(x) = -x^2 * B + Nx
We can notice that the graph of this function is a parabola. Our best answer would be f(k) = h
where the point (k,h) is the vertex of the parabola. It’s well known that
k = \frac{-b}{2a}
for any parabola following the form f(x) = ax^2 + bx + c
So here : k = \frac{N}{2*B}
We can also deduce that from the derivative and find the local extrema of the function.
Since we can press the second button only integer number of presses so we must try, k1 = \lfloor \frac{N}{2*B}\rfloorANDk2 = \lceil \frac{N}{2*B}\rceil and pick the better choice.
Ternary search is another possible solution for this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: Will be found here TESTER’s solution: Will be found here EDITORIALIST’s solution: Will be found here
Very nice!!
What I did was used ternary search because the results after pressing some 1 and some 2 first increase and then decrease as we go on increasing number of times we pressed 1.
Though this was simple to think better one is this one (admin).
Very nice!!
What I did was used ternary search because the results after pressing some 1 and some 2 first increase and then decrease as we go on increasing number of times we pressed 1.
Though this was simple to think better one is this one (admin).
Can someone prove the optimality clause made by the poster of this editorial ? I mean seriously, I did get the rationale behind the question, and it became pretty straightforward once I assumed that the solution will be optimal this way. A mathematical proof would be great! Thanks in advance !
Instead of checking how many times the second button was pressed I was checking what was the maximum answer we could get if I press the first button x times which gave me the quadratic equation for the score as ((N-x)/B )*x ,now this gives maxima at n/2 so I was checking numbers around n/2 which was giving me WA ,can anybody please point out what is wrong? Also I was keeping in mind the fact that (N-x)>B for x=n/2 ,if it was then my maximum would be around n/2 or else my maximum would be at x=N-B.
Someone please point out my mistake
I never thought that it would require parabola or derivatives, I just took some examples, found out what common technique worked for them, and the solution worked.
Too many of the solutions above have strange tests and conditionals. These are not really necessary, and the required effect can be handled in the division sum.
If x is the number of times button 2 is pressed, then the final score S is given by
S = x(N-Bx)
Using simple manipulation to complete-the-square gives
S = x(N-Bx)
= Nx-Bx^2
= B \left(\frac N {2B}\right)^2 - B \left(\frac N {2B} - x\right) ^2
To maximize S, we make \left| \frac N {2B} -x \right| as small as possible. The number of button presses x has to be an integer, so we seek the nearest integer to \frac N {2B}. Using the integer arithmetic of C, we set
x = \left\lfloor\frac {N+B} {2B}\right\rfloor
.
Hence a solution:
#include <bits/stdc++.h>
using namespace std;
int main( int argc, char ** argv )
{
uint32_t T,N,B;
cin >> T;
while (T--) {
cin >> N >> B;
uint64_t x = (N+B)/(B+B);
cout << x*(N-x*B) << endl;
}
return 0;
}