Задача №112446. Бороться и искать, найти и не сдаваться!
Не превращай людей в героев, Джон, героев нет.
А даже будь они — я из другой оперы
Шерлок
Джим Мориарти решил сыграть с Шерлоком Холмсом в небольшую игру. Накануне он похитил миссис Хадсон и заточил её в одной из лабораторий военной базы «Баскервиль», на которой проводят сверхсекретные эксперименты.
Все лаборатории «Баскервиля» пронумерованы числами от \(1\) до \(N\), причём в каждой лаборатории, номер которой меньше, чем номер лаборатории, в которой заключена миссис Хадсон, злодей-консультант оставил записку, в которой написано «Green beard» («Зелёная борода»). А в каждой лаборатории, номер которой больше, чем номер лаборатории, в которой заключена миссис Хадсон, он оставил записку, в которой написано «A woman» («Та женщина»).
К сожалению, дедукция, внутренняя интуиция и даже везение покинули Шерлока Холмса после совершённого им преступления, поэтому он обратился к вам за помощью. Он просит вас отыскать миссис Хадсон как можно быстрее. Помогите ему, проверив не более 60-ти лабораторий, иначе Лестрейд прибудет на базу «Баскервиль» раньше, чем Шерлок спасёт миссис Хадсон.
При запуске решения на вход подаётся единственное целое число \(N\) — количество лабораторий на военной базе «Баскервиль» \((1 \leq N \leq 10^{18})\).
Для проверки очередной лаборатории выведите единственно число — номер лаборатории, которую вы хотите проверить. Если в этой лаборатории лежит записка, вам будет введён её текст.
Иначе вам удалось найти миссис Хадсон, и вам будет введена строка «Mrs. Hudson is here». После этого ваша программа должна завершиться.
1 Mrs. Hudson is here
1
100 A woman Green beard A woman Mrs. Hudson is here
100 1 99 2
В точности соблюдайте формат выходных данных. Вывод каждой строки должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Pascal, fflush(stdout) в С/C++ или cout.flush() в C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.