#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int vez;
int HC(int n)
{
srand(time(0));
if (n == 1) return 1;
int ini = 1, fim = n;
int ant = 0, lado = 0;
while (ini < fim)
{
if (fim-ini == 1)
{
if (lado == 0 || lado != ant)
{
Guess(ini);
int g = Guess(fim);
return (g == -1 ? ini : fim);
}
if (lado == 1) return (Guess(fim) == -1 ? ini : fim);
else return (Guess(ini) == -1 ? fim : ini);
}
int g;
if (lado == 0 || lado != ant)
{
int toss = rand()%2;
if (toss == 0)
{
Guess(ini);
g = Guess(fim);
ant = 2;
}
else
{
Guess(fim);
g = Guess(ini);
ant = 1;
}
}
else if (lado == 1)
{
g = Guess(fim);
ant = 2;
}
else
{
g = Guess(ini);
ant = 1;
}
if (g == 0) return (ini+fim)/2;
if (g == 1)
{
if (ant == 2) ini = (ini+fim)/2 + 1, lado = 2;
else
{
int pre = fim;
fim = (ini+fim)/2;
if ((ini+pre)%2 == 0) fim--;
lado = 1;
}
}
else
{
if (ant == 1) ini = (ini+fim)/2 + 1, lado = 2;
else
{
int pre = fim;
fim = (ini+fim)/2;
if ((ini+pre)%2 == 0) fim--;
lado = 1;
}
}
}
return ini;
}
