ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1682. Чокнутый профессор

Ideas for #41
Послано bstu_student 7 авг 2018 10:59
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
Послано die_young 7 авг 2018 13:50
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.
Re: Ideas for #41
Послано bstu_student 7 авг 2018 14:16
Great thanks!)