Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 5 лет назад, По-русски

Иногда на соревнованиях по программированию (в том числе и на Codeforces) вы можете встретить интерактивные задачи.

При тестировании вашего решения по интерактивной задаче тот ввод, что будет подаваться в ваше решение (то есть те данные, что ваше решение читает) не являются заранее заготовленными, а строятся непосредственно в процессе тестирования вашей программы. Для этого жюри пишет специальную программу интерактор, вывод которой отправляется в ваше решение, а вывод вашего решения отправляется в интерактор. Иными словами, ваше решение и интерактор работают в паре и как ваше решение, так и интерактор могут принимать решение о том, что в данный момент вывести на основании "истории общения".

При написании решения для интерактивной задачи важно помнить, что если вы что-то вывели, то без специального указания в программе эти данные могут на самом деле попасть во внутренний буфер и не быть выведенными немедленно. Это может привести к ситуации, что интерактор "не увидел" ваш вывод. Для того, чтобы быть уверенным, что порция данных была передана в интерактор надо использовать операцию flush, которая наверняка есть в стандартной библиотеке вашего языка. Например, при программировании на C++ надо использовать fflush(stdout) или cout << flush (в зависимости от того вы выводите с помощью scanf/printf или cout). В Java надо использовать метод flush у потока вывода, например, System.out.flush(). В языке Python можно использовать stdout.flush(). В языке Pascal можно применять flush(output).

Рассмотрим следующую интерактивную задачу. Её вы можете попробовать решить самостоятельно по ссылке http://codeforces.com/gym/101021/problem/1

Есть несколько особенностей характерных для интерактивных задач:

  • Ввод-вывод в интерактивных задачах работает значительно медленнее чем для обычных задач — старайтесь использовать scanf/printf вместо cin/cout в С++, BufferedReader/PrintWriter в Java и так далее.
  • Ручное тестирование решений для интерактивных задач обычно значительно сложнее, так как участнику самому нужно исполнять роль интерактора во время тестирования.
  • Вкладка "Запуск" ничего не знает об интеракторе для задачи, поэтому ее не получится использовать для полноценного тестирования решения.
  • На раундах Codeforces иногда будут использоваться интерактивные задачи, в этом случае в условии задачи будет описан формат тестов для взломов.
  • Вывод endl в cout в C++ автоматически делает операцию flush.

Задача

Условие

Напишите программу, которой предстоит в интерактивном режиме угадать число x, загаданное системой. Про загаданное число известно, что оно целое и лежит в границах от 1 до 106 включительно.

Вы можете делать запросы к тестирующей системе, каждый запрос — это вывод одного целого числа от 1 до 106. Есть два варианта ответа тестирующей системы на запрос:

  • строка <, если загаданное число меньше числа из запроса;
  • строка >=, если загаданное число больше либо равно числу из запроса.

В случае, если ваша программа считает, что определила загаданное число, выведите строку вида ! x, где x — это ответ, и завершите работу своей программы.

Вашей программе разрешается сделать не более 25 запросов (не считая вывода ответа).

Входные данные

Для чтения ответов на запросы программа должна использовать стандартный ввод.

Входные данные будут содержать ответы на запросы, то есть строки вида < и >=. i-я из этих строк является ответом системы на i-й запрос. После того, как ваша программа угадала число, выведите ! x (без кавычек), где x — это ответ, и завершите работу своей программы.

Тестирующая система даст вашей программе прочитать ответ на запрос из входных данных только после того, как ваша программа вывела соответствующий запрос системе и выполнила операцию flush.

Выходные данные

Для осуществления запросов программа должна использовать стандартный вывод.

Ваша программа должна выводить запросы — целые числа xi (1 ≤ xi ≤ 106) по одному в строке. После вывода каждой строки программа должна выполнить операцию flush.

Каждое из значений xi обозначает очередной запрос к системе. Ответ на запрос программа сможет прочесть из стандартного ввода. В случае, если ваша программа угадала число, выведите строку вида ! x (без кавычек), где x — ответ, и завершите работу программы.

Решение

Конечно, эту задачу следует решать бинарным поиском по ответу. Вот пример решения на C++:

#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    int l = 1, r = 1000000;
    while (l != r) {
        int mid = (l + r + 1) / 2;
        printf("%d\n", mid);
        fflush(stdout);

        char response[3];
        scanf("%s", response);
        if (strcmp(response, "<") == 0)
            r = mid - 1;
        else
            l = mid;
    }

    printf("! %d\n", l);
    fflush(stdout);
}

Желаем полных решений. Еще раз напоминаем, что ознакомиться с интерактивной задачей можно по ссылке http://codeforces.com/gym/101021/problem/1

 
 
 
 
  • Проголосовать: нравится
  • +293
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

can i use "ios::sync_with_stdio(false)" with cin/cout instead of scanf/printf in c++ or it's Better to Use scanf/printf ?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

А как в интерактивной задаче работают взломы?
UPD: нашел в тексте поста. Описывается в условии задачи.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    Интерактор детерменирован изначальным вводом.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Известно под каким номером будет интерактивная задача?

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

how would you test these kinds of problems on your local computer?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here is another interactive problem to try from (2012-2013 ACM-ICPC, NEERC, Moscow Subregional Contest):

J. Just Another Disney Problem

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You don't need "return 0;" for interactive problems?

»
5 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

Наконец-то, а несколько лет назад почему-то говорили, что нельзя, что это плохо, что никто не поймет, что непонятно как взломы делать, и т.д.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In hacks, how would the "output" of model/participant solution be shown?

For some problem like this or this it seems we can see the whole process (look at some submissions), but the example problem from this post just shows the hidden number and the number of queries.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    In the problem above (from this blog) the input for hacking would be the hidden number. In the round today, the information about hacking will be in the statement.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

It is very funny :D using binary search (the exact code of blog) with L = 1, R = 1e6+6 got wrong answer on test 6, but L = 1, R = 1e6 got Accepted!

L = 1, R = 1e6+6: submission L = 1, R = 1e6: submission

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's another interactive problem. https://www.codechef.com/MAY16/problems/CHBLLS Anyone interested may take a look. My first interactive problem. I enjoyed the solution but didn't like that flushing part somehow :v Even if someone understands the logic, he has the chance to get a wrong verdict for the syntax.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello,
why such code could get TLE on test 2 while if I just change the reckoning of mid to be the same as in the blog it gets AC .
any help would be highly appreciated

int main() {
    int l = 1, r = 1e6+10;
    while(l < r){
        int mid = (l+r)>>1;
        printf("%d\n",mid); fflush(stdout);
        char s[10]; scanf("%s",s);
        if(s[0]=='<') r = mid-1;
        else l = mid;
    }
    printf("! %d\n",l); fflush(stdout);
    return 0;
}
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My solution gets Idleness Limit Exceeded, even though I flush the buffer. Where do you think the problem is?

18300219

UPD: I've found the error! I should've printed one query per line.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

hello,
any one could tell me why this code gets TLE on test 2 whilst the same code in the blog gets AC which just differs in reckoning of mid, while I make r equals to 1e6+1 to evade that .
any help would be highly appreciated


int main() { int l = 1, r = 1e6+1; while(l < r){ int mid = (l+r)>>1; printf("%d\n",mid); fflush(stdout); char s[10]; scanf("%s",s); if(s[0]=='<') r = mid-1; else l = mid; } printf("! %d\n",l); fflush(stdout); return 0; }
»
5 лет назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

why in this round ? you could use it in the educational first

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Getting Idleness limit exceeded on test 1 in the first given problem. Here is my code. How can I fix it?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Read the task.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Read the example code by Mike.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ohh... I missed the example code. I am not used to this system. why this???

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Because it is very interesting and new for CF community

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        please clear me 2 things.

        1. the given output is my input

        2. I need to use flash after every output.

        right? anything else?

        I have not idea about it. so please clear me.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          Your program must send requests(input) to interactor,and interactor answers for request(output). If you test your code local, you should answer for request by using input.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          You should use flush for correct interactive work.

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

An Educational Round on this type of Problems would be better to understand the Submit / Hacking System .

»
5 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Mike don't get me wrong it sounds like this contest is gonna be brilliant but couldn't you post this earlier like a day or two earlier.

or you could have tried it with educational rounds first like Deathly_Hallows said.

Nevertheless I wish happy coding for everyone and high ratings good luck.

:)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    hi.. actually users facing interacting problems for the first time may experience significant drop in ratings.. so please make the announcements a bit before or we can have a testing round or educational for such purposes.. its nice that codeforces comes up with newer challenges.. thanks.. :)

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

В каком дивизионе будет интерактивная задача?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

what will be the verdict for making more than 25 queries???!!

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The example section looks a bit misleading: why ">=" / "<" are output instead of input? And I think it'd be better to arrange them chronologically, like this.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    TL;DR — you are right, but it isn't important, right?

    You are right that it's misleading and should be other way around. It's my mistake. It will be displayed correctly in the round (with ">=" as input in this case).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    So, what do you think about the format we used? There were tables in the Notes section. Any better solution?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It looks perfect. (The only issue may be that we can't copy-paste since it is a picture, but for that specific problem it is ok.)

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Huh. I've just realized that it's impossible to copy-paste. Strange — because it's not a picture, it's an HTML table.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why's that "r = mid - 1" and "l = mid" gets AC and "r = mid - 1" and "l = mid + 1" gets WA? Can someone explain it?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for mid if response is < then hidden number is less than mid so r = mid - 1 if response is >= then hidden number is mid or greater than mid so l = mid

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    because on doing l==mid+1 , you are ignoring the current mid value which is giving boolean value 1 for objective function.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can do l = mid + 1 and ans = mid. And print ans in the end.

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I recommend not to penalize errors on 1 test for the interactive problem as many people might get confused initially.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I guess Input and Output were mutually misplaced?

I need to Input '<=' and '>' and let computer to guess and Output the number?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Input and Output are displayed swapped in this problem, sorry. It will be displayed correctly during the round.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All the problems will be "Interactive"? All 5 from today's contest?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

[Deleted]

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Would it be possible to hack an interactive problem?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All the problems will be interactive?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My first ever solved interactive problem on any oj codechef: MAY16 "Chef and Balls"

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If you have a question

{

for (int i = 0; i < 100; i++)

{

    reread the blog;

    reread all comments;

    if you have found the answer

        goodbye;

}

ask your question in comments;

goodbye;

}

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Люди, я решил задачу, но говорит, что зависла на первом претесте. Что это означает? В смысле где я не правильно написал.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Doesn’t std::endl flush the output buffer in C++ and doesn’t std::cin flush it as well? I’m pretty much surprised that 18314320 fails while 18315037 gets accepted.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    You have different loop condition, lol

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oops, sorry :D

      That’s what happens when one doesn’t write contests for a long time!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks, but I made mistake in the understanding of the task.

    I should to go on a new line after flush.

    I mean: cout<<flush<<Something<<endl;

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Actually, flush before Something just flushes an empty buffer, so it can be omitted.

»
5 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

It's very important to specify whether the system actually "hides" a fixed integer before interaction starts or the interactor can change the number (or any other information, in general) during testing in a way consistent with previous answers. In the former case, some probabilistic solutions to some problems can pass. In the latter, they won't.

As far as I can see, the only place in the example problem which mentions it is "it's fine to guess — if you guess correctly".

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The second sample clearly shows it. But yes, I agree that it should also be written in the statement. We adjusted this problem in hurry and it isn't perfect (we decided to show the guide in the day of the contest).

    Also, in some problems the system may be smarter/malicious and answer to more likely fail a participant. But we didn't want it in "prime 100" problem.

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Maybe there should be another status for protocol failure (e.g. query limit exceeded)? Even Runtime Error would be much better than WA.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I don't see a reason. In standard problems there shouldn't be "WA because your answer is too small" or "WA because an edge you printed doesn't exist". So, why should we get extra info here?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      But there is in fact presentation error if you violate output protocol (e.g. give less integers than needed)

      I'd really like to see query limit as PE than as WA, because you're actually violating protocol by printing more queries than it was possible.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Are you sure about PE? I thought that there is no PE in CF rounds — source.

        And I don't think it's possible to create some exact rules what is PE and what is WA. For example, a participant should print the number of vertices satisfying something — then what if he/she prints  - 1 or n + 1? Should it be WA or PE? It's only an example.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можете исправить ошибку в решении на паскаль? Или хотя бы подсказать где она

uses dos;
var l,r,n:longint;
 c:char;
 begin
   l:=1;
   r:=1000000000;
   while l<r do
   begin
   writeln((r-l)div 2+l);   
    flush(output);
    readln(c);
    if c='<' then r:=(r-l)div 2+l else l:=l+(r-l)div 2;
    if r-l=1 then begin 
                    write('! ',l); 
                    flush(output);
                    break;
                  end;
  end;
end.

  • »
    »
    18 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    может ошибка в том что вы вводите 1 символ хотя в вводе может быть >=

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Please Help Me Out ..

I am trying to solve the Interactive Problem given in the above Link as there may be an Interactive Problem in today's Round . I have submitted a Code for practice several times. But Its showing WA at Test 1 . Don't know why .

Problem: http://codeforces.com/gym/101021/problem/A

Here is My code: http://pastebin.ubuntu.com/23172422/

It'd be very helpful if you please point me out the erroneous point of my Code .

Thanks in Advance .

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

in the name of allah, most mercifull

hi

my question about question A that exist in blog and my logic is true

i don't know why this code doesn't work.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is writing fflush(stdout); at the end of main() necessary or redundant?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You need to use 'flush' operation only after every print.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      I meant, what about the last print. eg: in the code given in the blog,

      printf("! %d\n", l); fflush(stdout);

      is fflush(stdout) needed here?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -11 Проголосовать: не нравится

        Yes, you need.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Actually not. At the shutdown of the program stdout is automatically flushed. Though it is a good practise in an interactive problem to flush after any print because it doesn't make anything worse but prevents you from forgetting about some important flush.

          More details.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't understand the interactive process clearly. Can someone explain who gives the input, who gives output, who writes the code....it seems confusing to me. Thanks!

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    IN               OUT         IN              OUT
        ______________            _______________
       |	          |          |		     |
     ->|   Interactor | ------>  |   My solution | -------
    |  |	          |          |		     |        |
    |   --------------	      ---------------	      |
    |_____________________________________________________|
    

    Figure explaining how Interactive problem works.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Python 3, print() is a function and it has an optional parameter "flush" with a default value false. So you can just set it to true when needed to flush the output stream. print("blah blah", flush = True)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any idea what this error means

wrong output format Unexpected end of file - token expected

submission

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Even this works

cout.flush();

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Can some one explain why this

int mid = (r+1+l)/2;  (work)
int mid = l+(r-l)/2;  (not work)
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    It isn't equivalent. One rounds up, the other rounds down. Consider what happens when l + 1 = r.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Input have t tests with structure : - n - a1 a2 ... an For each test, user write on output x1,x2,...,xn, then judge write y1,y2,...,yn (this must be read by user) How can do this?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In the just concluded contest, I couldn't accept the input in python 2.

Problem: https://codeforces.com/contest/1011/problem/D

My simple solution:

n, m = map(int, raw_input().split())
print 1
raw_input()

The verdict: Idleness limit exceeded.

Any help is appreciated.

»
3 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

What are the changes if conditions are "<=" and ">" instead of "<" and ">=" ?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is this solution wrong?

/* _______ _______ _______ _______ _______ _______ ( ____ ( ____ ( )( ____ )( ____ ( ____ ) | ( \/| ( \/| () () || ( )|| ( \/| ( )| | (_____ | (__ | || || || (____)|| (__ | (____)| (_____ )| ) | |(_)| || _____)| ) | __) ) || ( | | | || ( | ( | (\ (
/_
) || (
__/| ) ( || ) | (____/| ) \ __ _______)(_______/|/ ||/ (_______/|/ __/

_______ _________ ______ _______ _ _________ _______ ( ____ __ /( __ \ ( ____ ( \ __ /( ____ \ | ( \/ ) ( | ( \ )| ( \/| ( ) ( | ( \/ | ( | | | | ) || ( | | | | | (_____ | ) | | | | | || ) | | | | (_ ) | ( | | | | ) || ( | | | | ) | | ) ) (| (__/ )| (____/| (____/___) (___/____) | |/ _______/(______/ (_______/(_______/_______/_______)

*/

include <bits/stdc++.h>

using namespace std;

define ll long long

define N 100005

define ld long double

define M 1000000007

define dd double

define rep(i,a,n) for(int i = a; i < n; i++)

define sep(i,n,b) for(int i=n-1;i>=b;i--)

define pb push_back

define mp make_pair

define Mll map<ll,ll>

define clr(x) x.clear()

define sz(x) ((int)(x).size())

define F first

define S second

int main() { int repeat=25; string tans; int start=0; int end=1000000; int mid=(start+end)/2; cout << mid << "\n"; cin >> tans; map<int,int> v; while(repeat--){ if(tans=="<"){ v[mid]=10; if(v[mid]==10 && v[mid+1]==11){ cout << "! " << mid+1 << endl; fflush(stdout); return 0; } start=mid; mid=(start+end)/2; cout << mid << "\n"; fflush(stdout); cin >> tans; } else if(tans==">="){ v[mid]=11; if(v[mid]==11 && v[mid-1]==10){ cout << "! " << mid << endl; fflush(stdout); return 0; } end=mid; mid=(start+end)/2; cout << mid << "\n"; fflush(stdout); cin >> tans; } } return 0; }

// >=

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
2 года назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Can someone explain why "L" is printed and not MID? And also when to print L , MID and R in binary search problems?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i use c language ,will it work in it too ;

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who wants to add new Interactive problen tag?

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is the meaning of "output is buffered"?

how does it work?

why output is buffered?

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

At last, I'm not afraid of interactive problems. Thanks!

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can I use "system("cls");" instead of "fflush(stdout);" in C++?

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think interactive problems should be removed from the contest.

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the solution, you have taken

char response[3];

It is showing compilation error when we take "string response" as input. Why is this happening?

»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

80301018 I am getting WA on test 6. I don't know why. can anyone help?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you tell me what's the meaning of "Hacks" in interactive problems?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If i solved one of them would it be worth for rating?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why do I still get the Idleness error despite of using flush after output (I have tried both flush after each output and just after the last output).

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

what is the difference between Wrong answer and TLE in interactive problems?

»
4 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Why does my code give Time limit exceeded in Testcase no 4? I am not able to figure out where is my code breaking!

Link to my code

In addition enabling the cin.tie, sync_wih_stdio etc. part causes idleness limit exceeded. Someone please help me!

Link to my code

If anyone can send a link to their solution it would be helpful in that way also. I am unable to open the submissions of other people.

Update: Problem solved! Please ignore this post!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When i run the above code in my compiler, i get ..expected';' before numeric constant. What does it mean?

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can any one provide example for python3 code ?

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

if we use endl then we need not flush anything (C++/C), right?