この問題の重要な点は、「本物の硬貨が、偽物の硬貨に比べて (圧倒的に) 数が多い」です。

ここで、次の事柄が成り立ちます。

偽物の硬貨は \(10\) 枚なので、 \(11\) 枚以上の同種の硬貨は必ず本物である。

この観察があればいくつか異なる解法が成立しますが、今回はそのうちひとつを紹介します。

\(1000\) 枚の硬貨を \(11\) 枚ずつに分けることを考えます。このとき、 \(11\) 枚組が \(90\) 個と \(10\) 枚の余りが出ます。
この \(11\) 枚組のうち偽物を含むものは高々 \(10\) 個なので、同種 \(11\) 枚の組を最低 \(80\) 個得られることになります。
また、 \(11\) 枚の硬貨を \(2\) 種類に分ける(どちらが本物かは不詳)ためには \(10\) 回の鑑定が必要です。

ここから、以下の解法が成立します。

• まず、鑑定を \(900\) 回使って全ての \(11\) 枚組を (高々) \(2\) 種類に分ける。
• 次に、本物だと判明した ( \(11\) 枚が全て同種であった) 硬貨は排除する。さらに、本物だと判明した硬貨の番号 \(x\) をひとつ記録しておく (そのような硬貨は必ず存在する)。
• この時点で、同種だと判明している硬貨のグループが最大 \(20\) 個と、 \(11\) 枚組から溢れた硬貨が \(10\) 枚残っている。それら全てに対して 、追加で最大 \(30\) 回の鑑定を用いて \(x\) と同種かを判別すると偽物の硬貨を全て特定できる。

この解法は、最大 \(930\) 回で偽物の硬貨を全て特定できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int ask(int x,int y){
  cout << "? " << x << " " << y << "\n";
  fflush(stdout);
  int res;
  cin >> res;
  return res;
}

void ans(vector<int> &a){
  cout << "!";
  for(auto &nx : a){
    cout << " " << nx;
  }cout << "\n";
  fflush(stdout);
}

int main(){
  int n,m,q;
  cin >> n >> m >> q; // dummy input
  int ok;
  vector<vector<int>> unknown;
  for(int i=0;i<90;i++){
    int up=i*11+1;
    vector<int> g1={up},g2={};
    for(int j=i*11+2;j<=i*11+11;j++){
      if(ask(up,j)==0){g1.push_back(j);}
      else{g2.push_back(j);}
    }
    if(g2.empty()){
      ok=up;
    }
    else{
      unknown.push_back(g1);
      unknown.push_back(g2);
    }
  }
  for(int i=991;i<=1000;i++){
    unknown.push_back({i});
  }
  vector<int> res;
  for(auto &nx : unknown){
    if(ask(nx[0],ok)==1){
      for(auto &ny : nx){
        res.push_back(ny);
      }
    }
  }
  ans(res);
  return 0;
}