По причине установки в серверной ИТМО новой пожарной сигнализации система может быть эпизодически недоступна 27-го мая в период с 09:00 до 18:00 (МСК). ×

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

Автор MikeMirzayanov, 3 года назад, По-русски,

Иногда на соревнованиях по программированию (в том числе и на 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/A

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

  • Ввод-вывод в интерактивных задачах работает значительно медленнее чем для обычных задач — старайтесь использовать 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/A

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

»
3 года назад, # |
  Проголосовать: нравится +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 ?

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

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

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

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

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

      А для систестов это тоже верно?

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

        Да. Если, конечно, иное не оговорено в условии задачи.

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

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

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

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

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

    You can take a solution from the blog above and run it on your computer. The program will ask you queries and you should print responses < and >=.

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

      oh I was looking for a faster automated method like ./a.out<input.txt>output.txt but that method is also ok.

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

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

J. Just Another Disney Problem

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

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

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

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

»
3 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +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

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится 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;
}
»
3 года назад, # |
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.

»
3 года назад, # |
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; }
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    if l+1==r then your code runs forever.

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

      If response were <= and > then mid=(l+r)/2 would work, right?

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

        It doesnt work beacuse of overflow. For instance if l=9 and r=10, (l+r)/2 will be 9 So mid doesnt change and l<r is true forever.

        This is why the above code does (l+r+1)/2

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

    mid = (l+r+1)>>1

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

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

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

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

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

    Read the task.

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

    Read the example code by Mike.

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

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

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

      Because it is very interesting and new for CF community

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          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.

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

            Oww.. thats interesting. sounds different. Thank you for explanation :)

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

          You should use flush for correct interactive work.

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

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

»
3 года назад, # |
  Проголосовать: нравится +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.

:)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.. :)

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

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

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

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

»
3 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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).

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

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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.)

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится 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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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

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

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

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

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

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

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

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

I guess Input and Output were mutually misplaced?

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

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

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

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

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

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

[Deleted]

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

Would it be possible to hack an interactive problem?

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

All the problems will be interactive?

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

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

»
3 года назад, # |
  Проголосовать: нравится 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;

}

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

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

»
3 года назад, # |
  Проголосовать: нравится 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.

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

    You have different loop condition, lol

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

      Oops, sorry :D

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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;

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

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

»
3 года назад, # |
  Проголосовать: нравится +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".

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.

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

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        3 года назад, # ^ |
        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.

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
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 .

»
3 года назад, # |
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.

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

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

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

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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?

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

        Yes, you need.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 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.

»
2 года назад, # |
  Проголосовать: нравится 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!

»
2 года назад, # |
  Проголосовать: нравится 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)

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

Any idea what this error means

wrong output format Unexpected end of file - token expected

submission

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

Even this works

cout.flush();

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

Can some one explain why this

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

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

»
11 месяцев назад, # |
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?

»
10 месяцев назад, # |
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.

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

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

»
5 месяцев назад, # |
  Проголосовать: нравится 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; }

// >=

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
5 месяцев назад, # |
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?

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

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

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

Who wants to add new Interactive problen tag?