Ideas for #41

Does anyon know, what is the longest test? I check a couple of numbers,with k= 99998 execution was the longest, but i'm not sure.

UPD: I check (write k=99998 instead a reading number), and if WA#1 said truth, i reach the answere in 0,71. But this decision is still have TLE#41 :(

Maybe, there is a harder 'k' for this task?

*Edited by author 07.08.2018 11:17*

*Edited by author 07.08.2018 11:17*

Re: Ideas for #41

You can try to binary search the test case.

Put somewhere in your program the following

if (clock() >= 0.9 * CLOCK_PER_SEC) {

assert(K <= BINARY_SEARCH_MIDDLE);

}

You need to include <cassert> and <ctime> for these to work.

Now (double)clock() / CLOCK_PER_SEC gives you program execution time in seconds.

clock() >= 0.9 * CLOCK_PER_SEC checks that your program runs more than 0.9 seconds, in other words, approaching TL of 1s. This 'if' allows to execute code that will probably work only on 41th test case.

assert( boolean expression ); exits with non-zero value if condition is not met.

You could also do

if (K <= BINARY_SEARCH_MIDDLE) {

exit(your favourite non-zero number);

}

So, you can start with assert(K <= 100000 / 2) and so on. If you program fails on 41th test with RE instead of TL you change the bin search value.