この問題の原案はキーエンス社の社員により提供されました

「\(S\)が与えられる。面積が \(S\) になるような \(a,b\) が存在するか？」という問題を \(N\) 回解けばよいです。\(a,b\) を全探索することを考えましょう。

\(a>S\) または \(b>S\) のときには、面積 \(4ab+3a+3b\) は明らかに \(S\) より大きくなります。よって、\(a\le S\) かつ \(b\leq S\) の範囲を全探索すればよいです。

計算量は \(O(N \max(S_i)^2)\) となります。

実装例(C)
実装例(Python)

• Bonus 1：\(N\leq 10^6\)、\(S_i\leq 10^3\) で解いてみましょう (300点相当？)
• Bonus 2：\(N\leq 10^6\)、\(S_i\leq 10^5\) で解いてみましょう (400点相当？)
• Bonus 3：\(N\leq 10^3\)、\(S_i\leq 10^8\) で解いてみましょう (400点相当？)