原案：Mitsubachi

まず、 \(N\geq 21\) の場合は必ず解が存在します。

証明：

\(A\) の要素に重複が存在する場合は明らかに解が存在します。以降は \(A\) の要素に重複が存在しない場合を考えます。

\(M=11\) の場合を考えます。このとき \(\displaystyle s_X,s_Y \le \sum_{k=1}^{11} \frac1k<3.02\) が成り立ちます。一方、 \(N\) 個の中から \(11\) 個選ぶ方法は \(\displaystyle \binom{N}{11}\) 通りでり、特に \(N \geq 21\) の場合は選ぶ方法は \(\displaystyle \binom{N}{11} \geq \binom{21}{11}>3.5\times 10^5\) 通り存在します。このことから鳩の巣原理より \(N\geq 21\) では必ず解が存在することが分かります。

さらに、解が存在する場合には \(\displaystyle M=\left\lfloor \frac{N}2\right\rfloor\) に解が必ず存在します。

証明：

解を一つ取り、それを \(X,Y\) とします。\(X\cap Y\) が空でない場合はそれらを \(X,Y\) 両方から取り除くことで \(X\cap Y\) を空集合にすることができます。このとき \(\displaystyle |X|=|Y|\le \frac N2\) が成り立ち、 \(X,Y\) 両方に同じ適当な要素を追加することで \(\displaystyle M=\left\lfloor \frac{N}2\right\rfloor\) にすることができます。

実装では \(N \leftarrow \min(N,21)\) とし、\(\displaystyle M=\left\lfloor \frac{N}2\right\rfloor\) して答えが存在するか探索すれば良いです。

浮動小数点数型を用いる場合は誤差に注意してください。誤差の関係で注意しても正解できない可能性もあります。