C. Constructing Tests | Educational Codeforces #38

f(n, m)
:= nxnのときの配置可能な最大の1の数とする。
ただし、1<=m<=n
任意のnについて
f(n, 1) = 0
よって x = 0 のときは例外として処理する。
以下、m>=2、x>=1とする。
nxnのm-free行列について1が最大となる置き方の一つは
mxmの部分行列ごとに、右下に1個0の配置。
例えばn=5, m=2とすると
11111
10101
11111
よって
f(n, m) = n^2 - ⌊n/m⌋^2
2<=m<=nだから
n^2 - ⌊n/2⌋^2 <= f(n, m) <= n^2 - 1
これより
n^2 - ⌊n/2⌋ <= x <= n^2 - 1
であるようなすべてのnについて
1<m<=nの範囲で
f(n, m) >= xとなるような最小のmを二分探索で求める。(これをyとおく)
f(n, y) = x ならば(n, y)が解
条件を満たすすべてのnについて、そのようなyが存在しないならば-1