Idea: thanhchauns2
We made sure that almost every $$$2^{n - 1}$$$ solutions cannot pass.
Did you use the $$$0$$$ query?
$$$\frac{2^{n + 1}}{3} = 2^n \cdot \frac{2}{3}$$$, what is the conclusion?
1xxxD - Tournament Coundown
There is a way to erase $$$3$$$ participants in every $$$2$$$ queries. Since there are $$$2^n - 1$$$ participants to be removed, the number of queries will be $$$\left \lceil (2^n - 1) \cdot \frac{2}{3} \right \rceil = \left \lfloor \frac{2^{n + 1}}{3} \right \rfloor$$$. Suppose there are only $$$4$$$ participants. In the first query we will ask the judge to compare the $$$1^{st}$$$ and the $$$3^{rd}$$$ participants. There are three cases:
The $$$1^{st}$$$ participant wins more game than the $$$3^{rd}$$$ one: the $$$2^{nd}$$$ and $$$3^{rd}$$$ cannot be the winner.
The $$$3^{rd}$$$ participant wins more game than the $$$1^{st}$$$ one: the $$$1^{st}$$$ and $$$4^{th}$$$ cannot be the winner.
The $$$1^{st}$$$ and $$$3^{rd}$$$ participants' numbers of winning games are equal: both the $$$1^{st}$$$ and $$$3^{rd}$$$ cannot be the winner.
Ask the remaining two participants, find the winner between them.
If there are more than $$$4$$$ participants, we can continuously divide the number by $$$4$$$ again and again, until there are at most $$$2$$$ participants left. Now we can get the winner in one final query.
#include <bits/stdc++.h>
using namespace std;
int ask(vector<int> &k)
{
cout << "? " << k[0] << ' ' << k[2] << endl;
int x;
cin >> x;
if (x == 1)
{
cout << "? " << k[0] << ' ' << k[3] << endl;
cin >> x;
if (x == 1) return k[0];
return k[3];
}
else if (x == 2)
{
cout << "? " << k[1] << ' ' << k[2] << endl;
cin >> x;
if (x == 1) return k[1];
return k[2];
}
else
{
cout << "? " << k[1] << ' ' << k[3] << endl;
cin >> x;
if (x == 1) return k[1];
return k[3];
}
}
void solve()
{
int n;
cin >> n;
vector<int> a, b;
for (int i = 1; i <= (1LL << n); i++)
{
a.push_back(i);
}
while (a.size() > 2)
{
while (!a.empty())
{
vector<int> k(4);
k[0] = a.back();
a.pop_back();
k[1] = a.back();
a.pop_back();
k[2] = a.back();
a.pop_back();
k[3] = a.back();
a.pop_back();
int win = ask(k);
b.push_back(win);
}
a = b;
b.clear();
}
if (a.size() == 2)
{
cout << "? " << a[0] << ' ' << a[1] << endl;
int x;
cin >> x;
if (x == 2) a[0] = a[1];
}
cout << "! " << a[0] << endl;
}
int main(int argc, char ** argv)
{
int tests;
cin >> tests;
while(tests--) solve();
}