-2
\$\begingroup\$
#include <stdio.h>

int main() {
    int k, t, N, B, max, num_tests;
    scanf("%d", &num_tests);
    while (num_tests--) {
        scanf("%d %d", &N, &B);
        for (k=N/B,max=0; k>0; k--) {
            t = (N-k*B) * k;
            if (t > max) max = t;
        }
        printf("%d\n", max);
    }
    return 0;
}

the code seems to take a little more than one second but the constraint is to execute within one second, how can we increase the speed of this sort of code without using multithreads (I don't know how to use them).
the original question is - "Initially, each screen shows the number zero. Pressing the first button increments the number on the first screen by 1, and each click of the first button consumes 1 unit of energy.Pressing the second button increases the number on the second screen by the number which is currently appearing on the first screen. Each click of the second button consumes B units of energy.Initially the calculator has N units of energy. what is the max num on second calculator" here N and B are taken as inputs fromuser

\$\endgroup\$

closed as unclear what you're asking by Mast, alecxe, t3chb0t, Edward, Vogel612 Jul 13 '17 at 20:49

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    \$\begingroup\$ Please include a description of what the code does in the title, everyone here wants to "increase the speed efficiency of the code" \$\endgroup\$ – ratchet freak Jul 13 '17 at 12:14
  • \$\begingroup\$ How big is N? how big is B? \$\endgroup\$ – juvian Jul 13 '17 at 15:22
1
\$\begingroup\$

After searching the original problem on codechef, it becomes clear that B can be 1 and N be 1,000,000,000. In that case, your code will iterate all values and it will take long, as its O(n). This can be reduced to O(1).

You need to see this problem as a function, and once you find the correct function, you want to maximize it. In the first example, N is 10 and B is 2, so we can do at most 5 clicks on second button. If we decide to click first button, we will always need to click it 2 times, because if we leave 1 energy remaining we can´t use it for second button. Another important observation is that you always need to click the first button X times, and then spend the rest on second button. I leave that for you to think why.

So in this case, you can do the following: 0 * 5 (click 5 times second button and 0 the first) 2 * 4 (click 4 times second button and 2 the first) 4 * 3 (click 3 times second button and 4 the first) 6 * 2 (click 2 times second button and 6 the first) 8 * 1 (click 1 times second button and 8 the first)

It is clear that our function in this case is f(n) = n * (10 - 2n), with n being the amount of clicks on first button. Expanding, we get -2n^2 + 10n. Deriving that, we get -4n + 10. If we consider the maximum to be at 0 (which it is), n = 2.5 would archieve that maximum. If we replace on the ecuation, 2.5 * (10 - 2*2.5) = 2.5 * 5 = 12.5

However we can´t actually make 2.5 clicks on first button, so we need to consider either 2 clicks or 3, and take the best one. In this case, both cases will give us the answer : 12.

In cases where N is not a multiple of B, your first steps will always be clicking first button until remaining energy is a multiple of B and then you have the same problem as before.

More generally, f(n) = N % B + n * ((N - N % B) - B*n) and the n that maximizes the function is the solution of 2Bn = (N - N % B), so n = (N - N % B) / 2B. Be careful that n can be decimal, so you should consider using floor.

This way you can compute the answer in O(1) and remove your loop.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.