黒板に書かれている整数を \(1\) つにすればよく, そのためにはちょうど \(N-1\) 回の足し算をしてもらう必要があります.

黒板に \(2\) 個以上の整数が残っているとき, どの \(2\) 個をまず足し算してもらうべきでしょうか. 実は, 最大値と最小値の足し算をしてもらうことにすればよいです. その和の絶対値が \(R\) を超えないのは次のようにしてわかります.

黒板に書き込まれている整数の多重集合を \(X\) とし, \(X\) の要素の最大値を \(M\), 最小値を \(m\) とします. 特に \(X\) のすべての要素について絶対値は \(R\) 以下であり, 総和についても \(\displaystyle\left|\sum_{x\in X}x\right|\leq R\) が成り立ちます.

• \(m\geq 0\) のとき, 黒板に書き込まれている整数はすべて \(0\) 以上です. したがって, \(0\leq m+M\leq \sum_{x\in X}x\leq R\) が成り立ちます. よって \(|m+M|\leq R\) です.
• \(M\leq 0\) のとき, 黒板に書き込まれている整数はすべて \(0\) 以下です. したがって, \(0\geq m+M\geq \sum_{x\in X}x\geq -R\) が成り立ちます. よって \(|m+M|\leq R\) です.
• \(m\leq 0\) かつ \(M\geq 0\) のとき, \(-R\leq m\leq m+M\leq M\leq R\) が成り立つので, \(|m+M|\leq R\) です.

以上ですべての場合が尽くされています. したがって, 最大値と最小値の足し算をしてもらえばよいことがわかりました.

マージソートなどを用いて, 大小比較のやり取りを通して黒板に書かれている値を昇順にソートします. その後, 足し算のやり取りで最小値と最大値の足し算をしてもらいます. ソート済みの列から先頭と末尾を取り除き, 新たに最小値と最大値の和を挿入することになります. 挿入位置の検索には二分探索を用いればよく, これも大小比較のやり取りを通して実現することができます.

やり取りの回数を見積りましょう. 長さ \(2^n\) の列のマージソートで高々 \(a_n\) 回の大小比較を行うと評価できるとします. 明らかに \(a_0=0\) としてよいです. \(n\geq 1\) について, 長さ \(2^n\) の列のマージソートの際には, まず前半 \(2^{n-1}\) 項と後半 \(2^{n-1}\) 項に分け, それぞれをマージソートで再帰的にソートします. ここまでの大小比較の回数は最大で \(2a_{n-1}\) 回です. 次に \(2\) つのソート済みの長さ \(2^{n-1}\) の列を先頭同士の大小比較と先頭を取り除く操作の繰り返しでマージしていきます. マージの際には高々 \(2^n\) 回の大小比較を行うことになります. したがって

\[a_n=2a_{n-1}+2^n\]

としてよいです. \(b_n=a_n/2^n\) とおけば, \(b_0=0,b_n=b_{n-1}+1\) より \(b_n=n\) となり, \(a_n=n2^n\) が得られました. したがって, 長さ \(2^n\) の列のマージソートでは高々 \(n2^n\) 回の大小比較を行えば良いことが分かりました. \(N\leq 1000\leq 2^{10}\) の制約下では, 高々 \(a_{10}=10240\) 回の大小比較を行うことになります.

次に, 和の挿入位置の検索に必要な大小比較の回数を見積ります. 長さ \(2^n-1\) のソート済みの列への挿入位置の検索は, 二分探索を用いることで \(n\) 回の大小比較で実現することができます. \(N-1\) 回の和の挿入で列は短くなっていきますが, 簡単のため, 挿入されるソート済みの列の長さを大きく見積もって \(2^{10}-1=1023\) とすれば, 合わせて高々 \(10\times (N-1)\leq 9990\) 回の大小比較で行うことができます.

大小比較のやりとりは高々 \(10240+9990=20230\) 回行えばよく, 足し算のやりとりを高々 \(N-1\leq 999\) 回行うことと合わせても, \(25000\) 回の制限には余裕を持って間に合います.