Как выбрать начальное число (задача по бинарному поиску)?

Question

[dalbio]

Всем привет, у меня есть задача
https://codeforces.com/problemset/problem/1386/A
Скрин условия:

Я понимаю что там надо выполнить бинарный поиск по разнице ну т.е от 1...n, но я не могу выбрать начальное число.
Соревнование уже закончилось:

Имеющийся код:

#include <bits/stdc++.h>
using namespace std;
int main() {
	//IOS;
	int t;
	cin >> t;
	while (t--) {
		long long n;
		cin >> n;
		long long l = 0;// гарантировано не подходит
		long long r = n+1;// гарантировано не подходит
		long long last= //начальное число которое надо найти (придумать как-нибудь)
		long long ans = n;
		cout << "? " << last << endl;
		int a;
		cin >> a;
		while (r > l + 1) {
			long long m = (l + r) / 2;
			if (last + m <= n) {
				last += m;
			}
			else {
				if (last > m) {
					last -= m;
				}
			}
			cout << "? " << last << endl;
			int a;
			cin >> a;
			if (a) {
				r = m;
				ans = m;
			}
			else l = m;
		}
		cout << "= " << ans << endl;
	}
}

Заранее, спасибо, за помощь.

Comments

[Wataru]

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.

[dalbio]

wataru, Ну получается, что так

[dalbio]

Вопрос можно удалять (напиши твой комментарий как ответ)

Answer 1

[Wataru]

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.