#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <ctime>
 
int main(void)
{
  int max = 10000000;
  std::srand(static_cast<unsigned>(std::time(0)));
//  std::random_device rnd; // random_device not working properly under Windows MinGW
  std::vector<std::uint32_t> v(10);
//  std::generate(v.begin(), v.end(), std::ref(rnd));
  std::generate(std::begin(v), std::end(v), std::rand);
  auto seed = std::seed_seq(std::begin(v), std::end(v));
  auto rand = std::bind(std::uniform_int_distribution<>(1, max - 1), std::mt19937(seed));
  int ans = rand();
  int iter = 0, tmp = 0, dis = 0;
  std::string str = "", gt = "greater than ans", lt = "less than ans";
 
  while (true) {
    iter++;
    if (iter == 1) {
      tmp = max / 2;
      dis = tmp / 2;
      str = (tmp > ans) ? gt : lt;
    } else if (tmp > ans) {
      tmp -= dis;
      if (dis > 1)
        dis /= 2;
        str = gt;
      } else if (tmp < ans) {
        tmp += dis;
        if (dis > 1)
          dis /= 2;
        str = lt;
      }
      if (tmp == ans)
        str = "hit!";
      std::cout << "iter = " << iter << ", tmp = " << tmp << " " << str << std::endl;
      if (tmp == ans)
        break;
  }
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3N0ZGludD4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjdGltZT4KCmludCBtYWluKHZvaWQpCnsKICBpbnQgbWF4ID0gMTAwMDAwMDA7CiAgc3RkOjpzcmFuZChzdGF0aWNfY2FzdDx1bnNpZ25lZD4oc3RkOjp0aW1lKDApKSk7Ci8vICBzdGQ6OnJhbmRvbV9kZXZpY2Ugcm5kOyAvLyByYW5kb21fZGV2aWNlIG5vdCB3b3JraW5nIHByb3Blcmx5IHVuZGVyIFdpbmRvd3MgTWluR1cKICBzdGQ6OnZlY3RvcjxzdGQ6OnVpbnQzMl90PiB2KDEwKTsKLy8gIHN0ZDo6Z2VuZXJhdGUodi5iZWdpbigpLCB2LmVuZCgpLCBzdGQ6OnJlZihybmQpKTsKICBzdGQ6OmdlbmVyYXRlKHN0ZDo6YmVnaW4odiksIHN0ZDo6ZW5kKHYpLCBzdGQ6OnJhbmQpOwogIGF1dG8gc2VlZCA9IHN0ZDo6c2VlZF9zZXEoc3RkOjpiZWdpbih2KSwgc3RkOjplbmQodikpOwogIGF1dG8gcmFuZCA9IHN0ZDo6YmluZChzdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjw+KDEsIG1heCAtIDEpLCBzdGQ6Om10MTk5Mzcoc2VlZCkpOwogIGludCBhbnMgPSByYW5kKCk7CiAgaW50IGl0ZXIgPSAwLCB0bXAgPSAwLCBkaXMgPSAwOwogIHN0ZDo6c3RyaW5nIHN0ciA9ICIiLCBndCA9ICJncmVhdGVyIHRoYW4gYW5zIiwgbHQgPSAibGVzcyB0aGFuIGFucyI7CgogIHdoaWxlICh0cnVlKSB7CiAgICBpdGVyKys7CiAgICBpZiAoaXRlciA9PSAxKSB7CiAgICAgIHRtcCA9IG1heCAvIDI7CiAgICAgIGRpcyA9IHRtcCAvIDI7CiAgICAgIHN0ciA9ICh0bXAgPiBhbnMpID8gZ3QgOiBsdDsKICAgIH0gZWxzZSBpZiAodG1wID4gYW5zKSB7CiAgICAgIHRtcCAtPSBkaXM7CiAgICAgIGlmIChkaXMgPiAxKQogICAgICAgIGRpcyAvPSAyOwogICAgICAgIHN0ciA9IGd0OwogICAgICB9IGVsc2UgaWYgKHRtcCA8IGFucykgewogICAgICAgIHRtcCArPSBkaXM7CiAgICAgICAgaWYgKGRpcyA+IDEpCiAgICAgICAgICBkaXMgLz0gMjsKICAgICAgICBzdHIgPSBsdDsKICAgICAgfQogICAgICBpZiAodG1wID09IGFucykKICAgICAgICBzdHIgPSAiaGl0ISI7CiAgICAgIHN0ZDo6Y291dCA8PCAiaXRlciA9ICIgPDwgaXRlciA8PCAiLCB0bXAgPSAiIDw8IHRtcCA8PCAiICIgPDwgc3RyIDw8IHN0ZDo6ZW5kbDsKICAgICAgaWYgKHRtcCA9PSBhbnMpCiAgICAgICAgYnJlYWs7CiAgfQp9Cg==