Какое самое наивное решение? Это перебор всех пар, однако ясно, что он вряд ли сработает. Тогда давайте оптимизируем этот перебор.
Давайте попробуем просимулировать перебор, пусть n = 6.
1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
В итоге мы сделаем O(n*n-(n*(n+1)/2)) запросов.
Давайте попробуем вместо того, чтобы делать полный перебор, рассматривать числа диапазонно. Заметим, что 1 5 может покрыть 5 1, однако для этого диапазон должен быть не менее 2, потому для самой 5 нужно еще покрыть пару 5 6. Или пара 2 4 может быть покрыта парой 4 2, однако длина должна быть не менее 4, потому что самой 4 нужно покрыть 5 и 6 и 1.
Главный смысл в том, что разбивая числа на диапазоны, мы гарантируем, что когда то все пары покроются, но для этого нужно определить минимальную длину диапазона.
Тут можно заметить, что эта длина равна половине отрезка, т.е n/2.
Пусть x*n>=(n*(n-1)/2). x>=(n*(n-1)/2) / n x>=(n-1)/2.
Возьмем n/2 для полной уверенности.
Теперь давайте докажем, что пары покроют друг друга.
Пусть ln = n/2. Тогда давайте определим для каждого числа диапазоны длины ln(6/2=3)
[1 2 1 3 1 4] [2 3 2 4 2 5] [3 4 3 5 3 6] [4 5 4 6 4 1(7%6=1)] [ 5 6 5 1 5 2] [6 1 6 2 6 3].
Как можем видеть всего пар = 18(может входить и не различные пары). Это более чем покроет все 15 пар.
Однако потратим мы N/2*N => N*N/2 операции/запросов в худшем случае, если адаптируем под нашу задачу это N*N/a приблизительно, как раз то, что ждала от нас задача.
Сложность O(n/2*n).
Code:#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
ll ask(ll a, ll b){
cout << a << " " << b << endl;
ll x; cin >> x;
return x;
}
void bruh(){
ll n; cin >> n;
vector<ll> a;
for (ll i = 1;i<=n;i++){
a.pb(i);
}
ll ans1 = -1; ll ans2 = -1;
bool opt = 0;
for (ll f = 1;f<=n/2;f++){
if(opt){
break;
}
for (ll i = 1;i<=n;i++){
ll bs = (i+f>n? (i+f)-n: i+f);
ll x = ask(i,bs);
if(x==1){
ans1 = i; ans2 = bs;
opt = 1;
break;
}
if(x==-1){
opt = 1;
break;
}
}
}
cout.flush();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cin >> t;
while (t--) {
bruh();
}
}
