CALC - Editorial

editorial
, , , , ,
21

Button A has cost 1. Button B has cost B.x is number of times button B is pressed. So points left for button A = N-x*B. So number of times A is pressed = (N-x*B)/1=N-x*b

22

I just did this and it worked…

mod=N%B;
 div=N/B;
 if(mod>0)
 {
     div++;
     mod=B-mod;
     N=B*div;
 }
 k=div/2;
 e=(long)Math.ceil(div/2)*B;
 if(N<=B)
 System.out.println(0);
 else
 System.out.println((long)((N-e-mod)*k));

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.

23

TYSM vijju123! got it now :slight_smile:

24

@deadwing7 . The links for contest and practice are swapped.

25

The issue is corrected now. Thanks for pointing out ^^

1 Like
26

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int t;
cin>>t;
ll n,b;
while(t–)
{
cin>>n>>b;
ll val = n/b;
if(val%2==1)
val+=1;
ll mid = val/2;
ll answer = mid (n - (midb));
cout<<answer<<endl;
}
}

–possibly the simplest solutions you can get

1 Like
27

https://www.codechef.com/viewsolution/14459681

the simplest one thank me later.

28

Your solution will become twice more appealing if you give a short summary of your thinking/what you did here. :smiley:

29

@soheb17 that was a good observation. @vijju123 Actually In this question you will always get a maximum solution when you do half times 1 and remaining half do the other. You can notice this by custom inputs. What i mean to say is that in this question quadratic equation having roots first (no on the first) and second(no on the second) are equal.
In other words equal values has given extrema in this quadratic equation and so you know that how much to press on first and on second and you get the answer in O(1).

30

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;
}